A kombinatorika szeminarium kovetkezo

november 3 (pentek), 10:30 + (esetleges MÁV késés), Riesz terem
eloadasa:

Tardos Gábor (Rényi Intézet): Extremális gráfelmélet rendezett gráfokra

A Turán-féle extremális gráfelmélet azt kérdezi, hogy egy n csúcsú egyszerű gráfnak maximum hány éle lehet, ha nem tartalmaz egy rögzített P gráfot részgráfként.

Rendezett gráf = egyszerű gráf + lineáris rendezés a csúcsokon. Ezekre is ugyanezt kérdezzük, de most a rögzített P részgráf is rendezett, azaz csak egy fix sorrendben tiltjuk, hogy a P gráf részgráfként megjelenjen.

Az előadás során bemutatom, hogy a Turán-féle (rendezetlen) elméletből milyen eredmények öröklődnek át, milyen új problémák vizsgálhatóak, stb. Kedvencem ez a két nyitott probléma:

1. Milyen P rendezett gráf extremális függvénye lesz majdnem lineáris, azaz n^{1+o(1)}? Sejtés: Ha P körmentes és rendezett páros (azaz páros, ahol az egyik szĂ­nosztály megelőzi a másikat). Ezek szükséges feltételek, és tudunk is jó felső becslést sok ilyen rendezett gráf extremális függvényére, de még több esetben meg nem tudunk semmit.

2. Mennyivel lehet nagyobb egy rendezett páros gráf extremális függvénye a megfelelő (rendezetlen) gráfénál? Tudunk olyan gráfokat, ahol az arány n^{1/3-\epsilon}, de semmi sem zárja ki, hogy akár n^{1-\epsilon} legyen az arány (azaz rendezetten közel kvadratikus, anélkül közel lineáris az extremális függvény).

Minden érdeklődőt szeretettel várunk, Péter