A kombinatorika szeminarium kovetkezo
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