|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Csaba Béla: Hamilton-körök antidiszkrepanciája |
|
|||
|
|
||||
|
||||
| A kombinatorikus diszkrepancia alapkérdése (kissé pongyolán megfogalmazva) a következő: Egy véges X halmazon meg van adva egy S halmazrendszer. Az X halmaz elemeit két színnel színezzük - mekkora a maximális "színbeli kiegyensúlyozatlanság", amit nem tudunk elkerülni S élein, akárhogy is színezzük X elemeit? Nemcsak számos cikk, könyvek is születtek már diszkrepancia elméletből. A feladat antidiszkrepancia változata: keressünk olyan S élt, aminek a kiegyensúlyozatlansága kicsi, akármi is a színezés! Legyen most V egy n elemű halmaz, G egy egyszerű gráf V ponthalmazzal. A fenti X halmaz szerepét G élei játsszák, az S halmazrendszer élei pedig G Hamilton-körei. Tehát színezzük G éleit, és keresünk nagy/kicsi diszkrepanciájú Hamilton-kört. Az utóbbi években több diszkrepancia témájú cikk jelent meg ebben a kérdéskörben, hipergráfos változatokat is vizsgálnak már. A kérdés egy újabb változatában nem színezünk. Ehelyett a G gráf irányított, és olyan Hamilton-kört keresünk, amiben az élek többsége a kör egy körüljárásával megegyező irányú (diszkrepancia), illetve olyat, amiben közel ugyanannyi él található mind a két irányban (antidiszkrepancia). Friss eredmény (Freschi és Lo), hogy ha G (irányítatlan) minimális foka \ge n/2 + k (k>0 egész), akkor van olyan Hamilton-kör, amin legalább n/2+k él ugyanabba az irányba mutat. Tehát a diszkrepanciája \ge 2k. Ez az állítás éles. London András egy új eredménye: ha a fenti k=\Omega(n^{2/3}\sqrt{\log n}), akkor van legfeljebb O(n^{2/3}$-os antidiszkrepanciájú Hamilton-kör. Ennek az eredménynek egy javításáról lesz szó: ha k\ge 500 (500 garantáltan elég nagy itt), tehát G (irányítatlan) minimális foka legalább n/2+500, akkor van G-nek olyan Hamilton-köre, amiben legfeljebb 1000 az ellenkező irányba mutató élek számának különbsége, azaz az antidiszkrepancia. A tétel Ryan Martinnal közös munka eredménye. Fontos szegedi vonatkozás: a fenti gráfelméleti diszkrepancia vizsgálatok ötletadója, elindítója, többször szerzője kollégánk, Pluhár András. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013
