Expandergrafer Spektral grafteori och felr¨attande koder

Typ
Examensarbete för kandidatexamen
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
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material