Expandergrafer Spektral grafteori och felr¨attande koder

Examensarbete för kandidatexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/256864
Download file(s):
File Description SizeFormat 
256864.pdfFulltext629.32 kBAdobe PDFView/Open
Type: Examensarbete för kandidatexamen
Bachelor Thesis
Title: Expandergrafer Spektral grafteori och felr¨attande koder
Authors: Areback, Stefan
Al-Maleh, Christian
Dahlberg, Andreas
Gustafsson, Johan
Pousette, Tomas
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.
Keywords: Matematik;Mathematics
Issue Date: 2019
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/256864
Collection:Examensarbeten för kandidatexamen // Bachelor Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.