Description
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.