A következő kombinatorika szeminárium (november 25., péntek)

10:35 körüli kezdéssel (a pesti vonat érkezéséhez igazítva)

a Riesz teremben lesz. Az előadás:

Tardos Gábor (Rényi Intézet): Az Erdős-Szekeres konvex ponthalmaz probléma, Andrew Suk remek új eredménye és egy jobb hibatag

Jelöljük f(n)-nel a legnagyobb egészt, ahány konvex helyzetű pontot mindig lehet találni n általános helyzetű pont közt a síkon. Erdős és Szekeres 1935-ben bizonyítottak egy log(n)/2+O(loglog n) alakú alsó becslést és 1960-ban felső becslésként log n+2 -t. (A logaritmus bináris.)

Az alsó becslést több lépésben számos szerző javította, de csak 1-gyel vagy 2-vel, és a kettes faktor az alsó és felső becslés között megmaradt Andrew Suk idei eredmenyéig. Ő belátta, hogy f(n) = log n - O(log^{2/3} n loglog n). Bizonyítása nagyon egyszerű, amit tovább egyszerűsítve és még kisebb hibataggal (O((log n loglog n)^{1/2})) adok elő.

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

Péter