- Előadás helye: Déli Tömb 0.221, ideje: kedd 12:00-13:30
- Könyv (részben fedi az előadást): Lovász - Pelikán - Vesztergombi: Diszkrét Matematika
-
Hetenkénti téma
Szeptember 9.
Párosítások páros gráfokban, a Frobenius-König-Hall Tétel (ismétlés). Párosítások nem-páros gráfokban, Tutte tételének kimondása, Petersen tétele, König és Petersen tételek levezetése Tutte tételéből.Szeptember 16.
Tutte tételének bizonyítása. Minden csúcsban 2 fokú részgráf problémája és visszavezetése teljes párosítás létezésére. Hamilton kör, elégséges feltétel fokszámokkal (Dirac tétele), szükséges feltétel elvágó halmazokkal.Szeptember 23.
Extremális gráfelméleti problémák, Turán tétele.Szeptember 30.
Ramsey tétele gráfokra, alsó és felső becslés R(k)-ra. Ramsey tétele hipergráfokra. Síkbeli halmazok konvex részhalmazai, a "Happy End" probléma.Október 7.
Maximális csúcsszámú konvex sokszög kiválasztása véges síkbeli halmazból dinamikus programozással. Konvex burok meghatározása, amortizáció. Ramsey tétele több színre. Van der Waerden és Szemerédi tétele (csak említés).Október 14.
Extremális halmazrendszerek. Sperner tétele, LYM egyenlőtlenség. Láncfelbontások. Erdős-Ko-Rado tétel. Véges projektív síkok.Október 21.
Kromatikus szám, Brooks tétele.November 4.
Projektív sík GF(q) feletti 3 dimenziós vektortérből. Latin négyzetek: legfeljebb n-1 páronként merőleges n rendű adható meg, egyenlőség esetén van n rendű projektív sík és viszont. Uniform és nem-uniform Fischer egyenlőtlenség.November 11.
n nem-kollineáris pont a síkban legalább n egyenest határoz meg. Gallai-Sylvester Tétel. Erdős-de Bruijn tétel. Polaritás. A Gallai-Sylvester Tétel bizonyítása a síkgráfok élszámára vonatkozó becslés alapján. Bollobás tétele.November 18.
Bollobás-tétel polinomos bizonyítása. A polinom-módszer további alkalmazásai: 2 távolság, momentum-görbe.November 25.
Leszámlálások. A leképezések számának 16 változata. Stirling számok. A differencia-operátor.