Expandergrafer Spektral grafteori och felr¨attande koder
Ladda ner
Typ
Examensarbete för kandidatexamen
Bachelor Thesis
Bachelor Thesis
Program
Publicerad
2019
Författare
Areback, Stefan
Al-Maleh, Christian
Dahlberg, Andreas
Gustafsson, Johan
Pousette, Tomas
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Matematik , Mathematics