2021. 03. 04. 12:30 - 2021. 03. 04. 13:30
Zoom Meeting 6237505738
-
-
-
-
Esemény típusa:
szeminárium
Szervezés:
Intézeti
-
Szegedi Szemináriumok
Leírás
SZTE, TTIK, Bolyai Intézet, Kerékjártó szeminárium (online)
Absztrakt. Erdős és Hajnal belátták, hogy bármely rögzített $H$ gráfra, azokban az $n$-csúcsú gráfokban, melyek nem tartalmaznak $H$-val izomorf feszített részgráfot, sokkal nagyobb klikkek vagy független halmazok találhatóak, mint amekkorát Ramsey tételének kvantitatív változata garantál (ami kb. $\log n$). Nevezetes sejtésük szerint minden ilyen gráfban van egy legalább $n^c$-méretű klikk vagy független halmaz, ahol $c>0$ egy $H$-tól függő konstans.
Röviden áttekintjük ennek a sejtésnek a történetét, majd néhány új eredményt bizonyítunk.