Eseménynaptár

Részletek

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. E 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, amely 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ésfé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ájában.

A rendezvényről kép- és hangfelvétel készül, részvételével egyben hozzájárul nyilvános publikálásukhoz. A felvétel megtekinthető lesz az MTA YouTube-csatornáján.