A széna, a kazal és a tű – újabb nyertes ERC-pályázat a Rényi Intézetből

A véletlen módszer nagyon régóta rendkívül fontos szerepet játszik a kombinatorikában. A múltban legtöbbször arra használták ezt az eljárást, hogy bizonyos struktúrák létezését akkor is bizonyítani tudják, ha ténylegesen megtalálni nagyon nehéz őket. A véletlen módszer gyökerei a múlt század harmincas éveiig nyúlnak vissza, Erdős Pál meghatározó szerepet játszott a fejlődésében. A módszer alapja, hogy gyakran egy keresett struktúrát megkonstruálni sokkal nehezebb, mint azt belátni, hogy egy jól megválasztott valószínűségi mezőben egy véletlen struktúra nagy eséllyel teljesíti a feltételeket. Ezzel a módszerrel látták be először az expander vagy nagyító gráfok létezését. Ezek olyan gráfok, amelyek kevés éllel rendelkeznek, egy véletlen séta egy tetszőleges fix csúcsból mégis hamar közel egyenlő eséllyel jut el bármely másik csúcshoz. E gráfokat is nehéz megkonstruálni, de ha az összes, mondjuk, három reguláris gráf közül véletlenszerűen kiválasztunk egyet, az jó eséllyel expander gráf lesz.

Lovász lokális lemmájának lehetőségei

Tardos Gábor Fotó: wikimedia commons

A Lovász László nevéhez fűződő lokális lemma kifejlesztésével e tudományterület tovább fejlődött, és így már a véletlen módszer módosított változatának segítségével olyan jelenségeket is be lehetett bizonyítani, amely tulajdonságokkal a legtöbb struktúra nem rendelkezik. Ez a lemma nagyban kiszélesítette azon problémák körét, amelyekre a véletlen módszert alkalmazni lehet.

„Én alapvetően kombinatorikával, diszkrét matematikával foglalkozom, így kerültem kapcsolatba a véletlen módszerrel is. Ennek alkalmazását úgy is megfogalmazhatjuk, hogy szénát keresünk a szénakazalban. Van ugyanis egy nagy, rendetlen lehetőséghalmaz, és ebben kell megtalálnunk a feltételeink szempontjából jó lehetőségeket, amelyek általában sokkal gyakoribbak, mint a rosszak – mondja Tardos Gábor. – A lokális lemma alkalmazásával e módszer kiterjeszthetővé vált, és immár akkor is bevethető volt, ha tűt kerestünk a szénakazalban. Ekkor már csak nagyon kevés lehetőség jó számunkra, mégis a valószínűségi mező megfelelő tulajdonságainak kiválasztásával beláthatóvá vált, hogy annak valószínűsége, hogy a véletlen választás számunkra jó eredményt ad, ugyan nagyon kicsi, de nem nulla.”

Tardos és Moser: egy tűpontos módszer

Tardos Gábor és Robin Moser nagyjából tíz évvel ezelőtt újabb áttörést értek el a véletlen módszer alkalmazásában. Az eljárás konstruktív változatának megalkotásával már nemcsak a struktúra létezését lehetett bizonyítani, hanem egy viszonylag egyszerű eljárást is kidolgoztak a keresett struktúra megtalálására. Ha azok a feltételek teljesülnek, amelyek esetén a Lovász-féle lokális lemma működik, akkor Tardosék algoritmusa képes megtalálni a struktúrát. Erről az eljárásról az utóbbi tíz évben kiderült, hogy nagyon hatékony módszer, és az alkalmazási területei sokkal szélesebbek, mint ahogy azt eredetileg talán a szerzők is gondolhatták.

„Egy struktúra létezésének bizonyítására korábban két módszer állt rendelkezésre. Vagy sikerült megkonstruálni, vagy azt kellett bizonyítani, hogy véletlen választás esetén a siker valószínűsége nem nulla – folytatja Tardos Gábor. – Viszont az a módszer, amit Robin Moserrel kidolgoztunk, kombinálja ezt a két megközelítést. Egyrészt a Lovász-féle lokális lemmán alapszik, ami alapvetően véletlen módszer, másrészt olyan eljárást tartalmaz, amely megkonstruálja a keresett objektumot. Erről a módszerről sok esetben kiderült, hogy olyan problémák megoldására is jó, ami elsőre meglepő volt. Nemcsak a véletlen módszerrel már bizonyított létezésű struktúrákat lehetett a segítségével megkonstruálni, hanem olyan struktúrák létezését is sikerült vele bizonyítani, amelyekről ezt a véletlen módszer korábbi formáival nem sikerült.”

Egy eljárás rengeteg kapcsolattal

A matematikus szavai szerint ők „egy algoritmust adtak, de ez nem csupán algoritmikus szinten volt érdekes, hanem az elméleti jelentősége is nagy volt”. Az új eljárás sokoldalú alkalmazhatósága miatt a matematika számos területét összekötötte, ezért az ERC-pályázatot is úgy építették fel, hogy minél több probléma megjelenjen benne, amelyeket ez az eljárás köt össze. Tardos Gábor kiemeli, hogy ugyan ő a projekt vezető kutatója, de ez a kutatás is csak úgy lehet sikeres, hogy kutatók egész csapata dolgozik a kutatási terveken. Már a pályázat összeállításában is több kutatótársa segítette. Olyan témákat is bevettek, amelyekkel ő személyesen akar foglalkozni, és amelyeknek az érdekességéről meg kellett győznie a bírálókat, de a kutatási irányok között felvonultattak már jól ismert és híres sejtéseket is, amelyekkel kapcsolatban viszont arról kellett meggyőzni a bírálókat, hogy az új módszerrel ezek is jól támadhatóak.

Az elmúlt tíz évben kiderült, hogy a módszer rendkívül sokoldalú, és mára nagyjából látszik, hogy mely irányokban alkalmazható, így a pályázatban vállalt célok igen reálisnak látszanak. Egyik céljuk a lokális lemma mérhető változatának kidolgozása, aminek a mérhető csoportelméletben nagyon fontos következményei lennének. Egy másik alkalmazási terület az extremális gráfelmélettel lesz kapcsolatos. Ezen elmélet alapproblémája valahogy úgy hangzik, hogy hány éle lehet egy adott csúcsszámú gráfnak, ha nincs benne egy bizonyos „tiltott részgráf” (például háromszögmentes a gráf). Az extremális gráfelmélet fejlődésében alapvető szerepet játszott Turán Pál.

Rendezett gráfok, ígéretes sejtések

Ezeket az elméleteket számos más irányba (például az ún. hipergráfokra, irányított gráfokra és rendezett gráfokra) kiterjesztették. Tardos Gábor és munkatársai főleg a rendezett gráfok extremális elméletét fogják kutatni.

„Az általunk vizsgált problémák általános érvényű és rendkívül produktív kérdések, mert a kombinatorikában, illetve a matematika egyéb területein felmerülő struktúrákban gyakran a probléma természetéből adódóan sorrendbe lehet rendezni a gráfok csúcsait vagy éleit. A probléma természetéből gyakran adódik, hogy bizonyos részgráfok nem fordulhatnak elő a struktúrákban valamilyen sorrendben, így a rendezett gráfok extremális elméletét alkalmazva becsülni tudjuk az élszámot – érvel Tardos Gábor. – E területeken számos olyan, ma már jól megfogalmazott sejtés létezik, amelyet az eljárásunk segítségével meg szeretnénk oldani. Reméljük, hogy e megközelítés közelebb fog vinni minket a megoldáshoz.”