Enkeltfag Engelsk 5 ECTS

Algebraisk Grafteori

Overordnede kursusmål

Kurset vil give eleverne de matematiske værktøjer til at anvende algebraiske teknikker til at undersøge teoretiske problemstillinger. Hovedfokus vil være at anvende lineær algebraiske værktøjer til matricer knyttet til grafer for at opnå information om grafstruktur og grafparametre.

See course description in English

Forstå egenværdier/egenvektorer af grafer og deres rolle i spektralgrafteori, f.eks. ved at bevise grænser for grafparametre
Anvende spektraldekompositionssætningen til at bevise grafteoretiske resultater
Anvende semidefinit programmeringsteknikker til at bevise resultater om Lovasz’ theta-funktion, f.eks. at den er en øvre grænse for Shannon-kapaciteten
Bevise standardresultater om kohærent algebraer og associationsskemaer
Bevise og anvende Erdos-Ko-Rado-sætningen
Anvende lineær algebra og gruppeteori til at bevise resultater om grafhomomorfier
Anvende Weisfeiler-Leman-algoritmen
Forstå karakteriseringen af grafer med minimum egenværdi på mindst -2
Anvende resultater i fraktionel grafteori, f.eks. om fraktionel farvelægning og fraktionelle isomorfier

1. Egenværdier og egenvektorer for grafer
2. Grafhomomorfismer
3. Anvendelser af lineær og semibestemt programmering til grafteori
4. Erdos-Ko-Rado-sætning
5. Graf automorfismer
6. Fraktionel grafteori
7. Shannon-kapacitet og Lovasz theta-funktionen