MVEX01-15-10 Expandergrafer

Ett viktigt matematiskt problem (med många tillämpningar i "verkliga" livet) är att konstruera grafer med få kanter men som likväl är "väldigt" sammanhängande. Det är inte så svårt att kvantifiera dessa begrepp och visa att man inte kan göra bättre än ett visst "tröskelvärde". Det var länge okänt om detta tröskelvärde verkligen kunde antas, men sedan en tid tillbaka vet vi att sådana grafer faktiskt existerar, även om deras konstruktioner är rätt intrikata.

Detta projekt syftar till att studera hur man konstruera sådana extremala grafer (så kallade "expanders") med hjälp av lite gruppteori och grundläggande talteori, och är lämpligt för Chalmers och GU-studenter som har läst lite om algebraiska strukturer, även om detta inte är helt nödvändigt.

Obs! För GU-studenter räknas projektet som ett projekt i Matematik (MMG900/MMG910).
 
Projektkod MVEX01-15-09
Gruppstorlek 2-4
Speciella förkunskapskrav Grundkurser i matematik, gärna med extra inslag av algebra.
Handledare Michael Björklund, 031-7723554 , micbjo@chalmers.se
Examinator Maria Roginskaya
Institution Matematiska vetenskaper

Publicerad: må 27 okt 2014.