A következő kombinatorika szeminárium ideje

december 6. (péntek), 10:00,

helye a szokásossá váló

Kalmár Intézet, Árpád tér, szemináriumi szoba (második emelet, a folyosó vége)

és előadása:

Rója Pál: Uniform, nem r-színezhető hipergráfok élszámáról

A legkisebb élszámot, ami egy n-uniform, nem r-színezhető hipergráfé, jelölje: m(n,r). Erdős és Lovász sejtése: m(n,2)=\theta(n 2^n). A legjobb, ismert alsó korlát, m(n,2)=\Omega(sqrt(n/log(n)) 2^n), Radhakrishnan és Srinivasan nevéhez kötődik 2000-ből. Az eredményük egy egyszerű bizonyítását fogom megmutatni. A bizonyítás alapja véletlen mohó színező algoritmus, amit Pluhár vizsgált 2009-ben. A bizonyítási módszer kiterjed az r-színezés esetére, és belátjuk hogy bármely rögzített r esetén: m(n,r)=\Omega((n/log(n))^(1-1/r) r^n), javítva Kostochka határát 2004-ből. Hasonló határokat származtathatunk olyan n-uniform hipergráfok élfokárának minimumára, amelyek nem r-színezhetők.

Minden érdeklődőt szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences