Expandergrafer Spektral grafteori och felr¨attande koder

Abstract

F¨orst bevisas existensen av expandergrafer med Margulis konstruktion och de spektrala egenskaperna hos Markovoperatorn. D¨arefter visas att egenrummen till Markovoperatorn definierad p˚a en Cayleygraf av SL(2,Fp) har stor dimension, vilket anv¨ands f¨or att bevisa Gowers sats f¨ or SL(2,Fp). Slutligen studeras bipartita expandergrafer i samband med felr¨attande koder, och de visas ge upphov till avkodningsalgoritmer med linj¨ar tidskomplexitet.