Nesrovnalosti hypergrafů - Discrepancy of hypergraphs

Nesrovnalosti hypergrafů je oblast teorie nesrovnalostí.

Hypergrafické nesrovnalosti ve dvou barvách

V klasickém prostředí se snažíme rozdělit vrcholy a hypergraf ${displaystyle {mathcal {H}} = (V, {mathcal {E}})}$ do dvou tříd takovým způsobem, aby v ideálním případě každá hyperedge obsahovala stejný počet vrcholů v obou třídách. Oddíl do dvou tříd může být znázorněn zbarvením ${displaystyle chi colon Vightarrow {-1, + 1}}$. Voláme -1 a +1 barvy. Barevné třídy ${displaystyle chi ^ {- 1} (- 1)}$ a ${displaystyle chi ^ {- 1} (+ 1)}$ vytvořte odpovídající oddíl. Pro hyperedge ${displaystyle Ein {mathcal {E}}}$, nastavit

${displaystyle chi (E): = součet _ {vin E} chi (v).}$

The rozpor ${displaystyle {mathcal {H}}}$ s ohledem na ${displaystyle chi}$ a rozpor ${displaystyle {mathcal {H}}}$ jsou definovány

${displaystyle operatorname {disc} ({mathcal {H}}, chi): =; max _ {Ein {mathcal {E}}} | chi (E) |,}$

${displaystyle operatorname {disc} ({mathcal {H}}): = min _ {chi: Vightarrow {-1, + 1}} operatorname {disc} ({mathcal {H}}, chi).}$

Zdá se, že tyto pojmy a pojem „rozpor“ se poprvé objevily v článku Kývnutí.^[1] Dřívější výsledky tohoto problému zahrnují pověstnou spodní hranici nesrovnalostí Rithových aritmetických postupů^[2] a horní hranice tohoto problému a další výsledky do Erdős a Spencer^[3][4] a Sárközi (popsáno na str. 39).^[5] V té době se problémy s nesrovnalostmi nazývaly kvaziRamsey problémy.

Abychom pro tento koncept získali nějakou intuici, podívejme se na několik příkladů.

• Pokud jsou všechny hrany ${displaystyle {mathcal {H}}}$ protínají se triviálně, tj. ${displaystyle E_ {1} cap E_ {2} = varnothing}$ pro jakékoli dvě odlišné hrany ${displaystyle E_ {1}, E_ {2} v {mathcal {E}}}$, pak je odchylka nula, pokud mají všechny hrany sudou mohutnost, a jedna, pokud existuje lichá hrana mohutnosti.
• Druhý extrém je poznamenán kompletní hypergraf ${displaystyle (V, 2 ^ {V})}$. V tomto případě je rozdíl ${displaystyle lceil {frac {1} {2}} | V | ceil}$. Jakékoli 2-zbarvení bude mít třídu barev alespoň této velikosti a tato sada je také hranou. Na druhou stranu jakékoli zbarvení ${displaystyle chi}$ s barevnými třídami velikosti ${displaystyle lceil {frac {1} {2}} | V | ceil}$ a ${displaystyle lfloor {frac {1} {2}} | V | floor}$ dokazuje, že rozdíl není větší než ${displaystyle lceil {frac {1} {2}} | V | ceil}$. Zdá se, že tento rozpor odráží, jak chaotické jsou hyperedge ${displaystyle {mathcal {H}}}$ protínají. Věci však nejsou tak snadné, jak ukazuje následující příklad.
• Soubor ${displaystyle n = 4k}$, ${displaystyle kin {mathcal {N}}}$ a ${displaystyle {mathcal {H}} _ {n} = ([n], {Esubseteq [n] mid | Ecap [2k] | = | Esetminus [2k] |})}$. Nyní ${displaystyle {mathcal {H}} _ {n}}$ má mnoho (více než ${displaystyle {jiný {n / 2} {n / 4}} ^ {2} = Theta ({frac {1} {n}} 2 ^ {n})}$) složitě protínající hrany, ale nesrovnalost nulová.

Poslední příklad ukazuje, že nemůžeme očekávat, že určíme nesrovnalost pohledem na jeden parametr, jako je počet hyperedges. Přesto velikost hypergrafu poskytuje první horní hranice.

Věty

• ${displaystyle operatorname {disc} ({mathcal {H}}) leq {sqrt {2nln (2m)}}.}$

s n počet vrcholů am počet hran.

Důkazem je jednoduchá aplikace pravděpodobnostní metody: Let ${displaystyle chi: Vightarrow {-1,1}}$ být náhodné zbarvení, tj. máme

${displaystyle Pr (chi (v) = - 1) = Pr (chi (v) = 1) = {frac {1} {2}}}$

nezávisle pro všechny ${displaystyle vin V}$. Od té doby ${displaystyle chi (E) = součet _ {vin E} chi (v)}$ je součet nezávislých −1, 1 náhodných proměnných. Takže máme ${displaystyle Pr (| chi (E) |> lambda) <2exp (-lambda ^ {2} / (2n))}$ pro všechny ${displaystyle Esubseteq V}$ a ${displaystyle lambda geq 0}$. Dát ${displaystyle lambda = {sqrt {2nln (2m)}}}$ pro pohodlí. Pak

${displaystyle Pr (operatorname {disc} ({mathcal {H}}, chi)> lambda) leq sum _ {Ein {mathcal {E}}} Pr (| chi (E) |> lambda) <1.}$

Protože náhodné zbarvení s pozitivní pravděpodobností má nanejvýš nesrovnalosti ${displaystyle lambda}$zejména existují barviva, která mají maximálně nesrovnalosti ${displaystyle lambda}$. Proto ${displaystyle operatorname {disc} ({mathcal {H}}) leq lambda. Krabice }$

• Pro jakýkoli hypergraf ${displaystyle {mathcal {H}}}$ takhle ${displaystyle mgeq n}$ my máme ${displaystyle operatorname {disc} ({mathcal {H}}) = O ({sqrt {n}}).}$

Abychom to dokázali, byl nezbytný mnohem propracovanější přístup využívající entropickou funkci. To je samozřejmě zvlášť zajímavé ${displaystyle m = O (n)}$. V případě ${displaystyle m = n}$, ${displaystyle operatorname {disc} ({mathcal {H}}) leq 6 {sqrt {n}}}$ lze zobrazit pro dostatečně velké n. Proto se tomuto výsledku obvykle říká „Šest směrodatných odchylek“. Je považován za jeden z milníků teorie diskrepancí. Metoda entropie zaznamenala řadu dalších aplikací, např. v důkazu těsné horní hranice pro aritmetické posloupnosti Matoušek a Spencer^[6] nebo horní mez z hlediska funkce prvotního rozbití kvůli Matouškovi.^[7]

• Předpokládejme, že každý vrchol ${displaystyle {mathcal {H}}}$ je obsažen maximálně na okrajích. Pak

${displaystyle operatorname {disc} ({mathcal {H}}) <2t}$

Tento výsledek Beck – Fialova věta, je kvůli Beck a Fiala.^[8] Vyrovnali nesrovnalost maximálním stupněm ${displaystyle {mathcal {H}}}$Je slavným otevřeným problémem, zda lze tuto vazbu asymptoticky vylepšit (upravené verze původního důkazu dávají 2t-1 nebo dokonce 2t-3). Beck a Fiala si to mysleli ${displaystyle operatorname {disc} ({mathcal {H}}) = O ({sqrt {t}})}$, ale v tomto směru bylo dosud dosaženo malého pokroku. Bednarchak a Helm^[9] a Helm^[10] vylepšil Beck-Fiala vázaný malými kroky k ${displaystyle operatorname {disc} ({mathcal {H}}) leq 2t-3}$ (pro mírně omezenou situaci, tj. ${displaystyle tgeq 3}$). Bukh^[11] vylepšil to v roce 2016 na ${displaystyle 2t-log ^ {*} t}$,kde ${displaystyle log ^ {*} t}$ označuje iterovaný logaritmus Důsledek Beckova papíru^[1] - poprvé se výslovně objevil pojem nesrovnalosti - ukazuje ${displaystyle operatorname {disc} ({mathcal {H}}) leq C {sqrt {tlog m}} log n}$ pro nějakou konstantu C. Nejnovější vylepšení v tomto směru je způsobeno Banaszczykem:^[12] ${displaystyle operatorname {disc} ({mathcal {H}}) = O ({sqrt {tlog n}})}$.

Klasické věty

• Osy rovnoběžné obdélníky v rovině (Roth, Schmidt)
• Nesrovnalosti polorovin (Alexander, Matoušek)
• Aritmetické průběhy (Roth, Sárközy, Kývnutí, Matoušek & Spencer )
• Beck – Fialova věta
• Šest směrodatných odchylek (Spencer)

Hlavní otevřené problémy

• Osy paralelní obdélníky v rozměrech tři a vyšších (Folklór)
• Komlos dohad

Aplikace

• Numerická integrace: Metody Monte Carlo ve vysokých rozměrech.
• Výpočetní geometrie: Rozdělte a dobijte algoritmy.
• Zpracování obrazu: Polotónování

Poznámky

Reference

• Beck, József; Chen, William W. L. (2009). Nesrovnalosti distribuce. Cambridge University Press. ISBN  978-0-521-09300-2.
• Chazelle, Bernard (2000). Metoda nesrovnalosti: náhodnost a složitost. Cambridge University Press. ISBN  0-521-77093-9.
• Doerr, Benjamin (2005). Integrální aproximace (PDF) (Habilitace teze). University of Kiel. OCLC  255383176. Citováno 20. října 2019.
• Matoušek, Jiří (1999). Geometrická odchylka: Ilustrovaný průvodce. Springer. ISBN  3-540-65528-X.