Description
MTA Székház Nagyterem
2026. január 13.
levezető: Páles Zsolt
13:00 – 14:00 Balogh József külső tag: Független halmazok leszámlálásai a konténer módszerrel
A kombinatorika, azaz a véges struktúrák matematikai elméletének fontossága megkérdőjelezhetetlen a számítógépek és az informatika korában.
Szinte minden extremális vagy optimalizálási kombinatorikai probléma átfogalmazható egy nagy gráf vagy hipergráf független halmazainak vizsgálatára.
Ezen független halmazok leszámlálásának, nagyságuk becslésének, struktúrájuk leírásának egy új módszerét ismertetjük. A 'konténer' módszer a klasszikus és a valószínűségi kombinatorikai módszerek egy nagyon hatékony ötvözete, ami számtalan leszámlálási probléma megoldását tette lehetővé, rendkívül pontos közelítéseket adva. A módszer nagyon technikai, és azon a felismerésen alapul, hogy 'tipikus' hipergráfnak kevés féle független halmaza lehet.
Több klasszikus problémát említünk, például hány éle lehet egy n csúcsú gráfnak, ha nem tartalmaz egy adott részkonfigurációt (Turán kérdése), vagy hány szám választható ki az 1,2,3,...,n számok közül úgy, hogy elkerüljék a k hosszú számtani sorozatokat (Szemerédi tétel).
A módszer más alkalmazásairól is szó lesz, többek között a Ramsey elmélet és a diszkrét, számítógépes geometria témákban.