Elkezdődött félév, kezdődik a kombinatorika szeminárium is.

A félév elsó kombinatorika szemináriumának ideje

helye

Az előadás

Gyárfás András vetette fel a következő geometriai Ramsey problémát: egy konvex 2n-szóg csúcsai közül n egymás mellettit alsó csúcsoknak, a többit felső csúcsoknak nevezzük. Az összes alsó-felső csúcspárt összekötjük egy egyenes szakasszal. A szakaszokat tetszőlegesen kiszínezzük piros/kék színnel. Mi a legnagyobb monokromatikus NEM-METSZŐ fa, amit minden színezésnél garantálhatunk?

Gyárfás egy 4/5 n-es kiinduló alsó becslést adott, majd diákjaival a konstans szorzóban egy \epsilon-nal javított egy technikás bizonyítással. Közben a probléma egy mátrixos átfogalmazása is megtörtént: Egy n x n-es 0-1 mátrix elemein sétálunk úgy hogy minden lépésünk egy elemből sorában jobbra (esetleg több pozicióval), vagy oszlopában lefelé történik. A séta során mindig ugyanolyan elemekre léphetünk rá. Az ilyen sétát "lépcsőnek" nevezzük. Mi a leghosszabb lépcső, amit minden mátrixnál garantálhatunk? A Gyárfás sejtés szerint az igaz válasz n-1. (n-1 mint felső becslés nem túl nehéz.)

Az előadásban megvizsgáljuk a nem szimmetrikus mátrixok esetét és egy sejtést fogalmazunk meg. Az erősített sejtés "felét" igazoljuk. A sejtés talán a leendó bizonyítónak is utat mutat.

Gyárfás felvetette, hogy a leghosszabb lépcsők vizsgálata helyett a leghosszabb 0-lépcső és 1-lepcső hosszának összegét is vizsgálhatnánk. Erre a prolémára vonatkozó sejtését megcáfoljuk és magadjuk az igazságot.

Végul egy átlatható, tetszetós bizonyítással \epsilon-nál jelentősebb előrelépést teszünk az alsó becslésnél.

Közös munka Csányi Jánossal és Nagy V. Gáborral

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

Péter U.i.: Az új szemináriumi tagoknak megjegyzem, hogy 10:00 azt jelenti "10:15-kor biztos elkezdjük".