02983 Algebraisk Grafteori

2024/2025

Kursusinformation
Algebraic Graph Theory
Engelsk
5
Ph.d., Fagligt fokuseret kursus
Kurset udbydes som enkeltfag
E4A (tirs 13-17)
Campus Lyngby
To timers forelæsning efterfulgt af to timers gruppearbejde øvelser.
13-uger
Aftales med underviser
Mundtlig eksamen
bestået/ikke bestået , intern bedømmelse
01227 , Matematisk modenhed
David Earl Roberson , Lyngby Campus, Bygning 322 , dero@dtu.dk
01 Institut for Matematik og Computer Science
I studieplanlæggeren

DTU PhD students must register for this course through the Study Planner.

PhD student from other universities must register as a guest student through:
https:/​​/​​www.dtu.dk/​​english/​​education/​​phd/​​intro/​​guest-phd/​​guest_courses/​​registration_form

Industry employees must register through Learn for Life: https:/​​/​​lifelonglearning.dtu.dk/​​en/​​biotech/​​
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.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
  • 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
Kursusindhold
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
Sidst opdateret
23. august, 2024