A következő kombinatorika szeminárium ideje

november 8. (péntek), 10:40 (modulo a pesti vonat késése),

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:

Tóth Géza (Rényi Intézet, Budapest): Az Erdős-Szekeres Tétel egyenesekre

Az Erdős-Szekeres Tétel (1935) szerint minden n-hez létezik olyan (legkisebb) f(n), hogy f(n) általános helyzetű pont között a síkon mindig található n amely konvex helyzetben van. A legjobb ismert korlátok f(n)-re a következők:

2^n-2+1 <₌ f(n) <₌ (^2n-5 _n-2)+1 \approx 4ⁿ/\sqrt{n} és a legtöbben azt sejtik, hogy az alsó korlát az igazság.

Ennek a problémának a ``duális'' változatát vizsgáljuk meg, a pontok helyett egyenesekre. Azt mondjuk, hogy n egyenes konvex helyzetben van, ha egy konvex n-szöget határolnak. Legyen f_l(n) a legkisebb szám azzal a tulajdonsággal, hogy ennyi általános helyzetű egyenes között a síkon mindig található n amely konvex helyzetben van. Az f_l(n) függvényre 4ⁿ/n illetve 4ⁿ/\sqrt{n} nagyságrendű alsó és felső korlátot adunk, vagyis az alsó korlát sokkal jobb, mint a pontokra ismert legjobb és pontosnak gondolt alsó korlát.

Az Erdős-Szekeres Tételnek nagyon sokféle általánosítása, módosítása ismert, ezek közül néhánynak megvizsgáljuk a fenti értelemben vett ``duális'' változatát.

Közös eredmények Bárány Imrével és Edgardo Roldán-Pensado-val.

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