A Regularitási Lemma alkalmazásai

A Regularitási Lemma az egyik leghatékonyabb eszköznek bizonyúlt különböző Ramsey, fedési és particinálási gráf és hipergráf problémák megoldásában. A V. Rödl által vezetett kutató csoport legújabb eredményei azt mutatják, hogy végre kidolgozták a Regularitási Lemma jól használható (ám bonyolult) hipergráfos verzióját. Az elmúlt évben a Regularitási Lemma-Blow-Up Lemma módszerrel megoldottunk néhány régi nyitott problémát. Az egyik ilyen például az utak pontos Ramsey számának a meghatározása három szín esetén, mely Faudree és Schelp egy sejtését oldja meg. Ebben a projektben folytatjuk ezt a kutatási irányt és reményeink szerint ki fogjuk tudni használni a Regularitási Lemma hipergráf verziójában rejlő lehetőségeket is.

Résztvevő Intézmények:

• MTA SZTAKI (Diszkrét Struktúrák csoport)
• Rutgers University
• Rényi Institute
• University of Memphis