Geometria Tanszék |
Bolyai Intézet, TTI Kar, Szegedi Tudományegyetem |
Az Erdős-Hajnal sejtésről
A Geometriai Tanszék örömmel teszi közzé, hogy
a Kerékjártó Szeminárium keretében előadást tart
címmel.
Az előadás helye és időpontja:
Az előadás kivonata:
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.
Tájékoztatás:
az eseményeken rendszerint kép- és hangfelvétel is készül tömegfelvételek formájában, egyben az esemény sajtónyilvános rendezvény is.
A Polgári Törvénykönyvről szóló 2013. évi V. törvény 2:48. § (2) bekezdése alapján a tömegfelvételek,
valamint a nyilvános közéleti szereplés esetén nincs szükség a résztvevők hozzájárulására sem a felvétel elkészítéséhez,
sem annak felhasználásához, de az érintetteket erről előzetesen tájékoztatni kell.
Kötelezettségünknek jelen szöveg megjelenítésével teszünk eleget azzal megtoldva, hogy jelezzük:
a felvételeket az esemény népszerűsítésére, marketing céllal, online és nyomtatott csatornáinkon keresztül használjuk fel.