Szemerediho lemma pravidelnosti

Szemerediho lemma regularity je lemma z obecné teorie grafů , které uvádí, že vrcholy jakéhokoli dostatečně velkého grafu lze rozdělit do konečného počtu skupin tak, že téměř všechny bipartitní grafy spojující vrcholy ze dvou různých skupin mají hrany rozmístěné téměř rovnoměrně mezi vrcholy. V tomto případě může být minimální požadovaný počet skupin, do kterých je nutné množinu vrcholů grafu rozdělit, libovolně velký, ale počet skupin v oddíle je vždy shora omezen.

Neformálně řečeno, lemma tvrdí přítomnost velkého počtu velkých pseudonáhodných struktur v absolutně jakémkoli grafu dostatečně velké velikosti.

Lema dokázal Endre Szemeredy v roce 1975. [1] [2]

Formulace

Pojem ε-jednotnosti

Nechť je dán bipartitní graf, jehož hrany spojují vrcholy z množiny s vrcholy z množiny . $G=(W=U\sqcup V,E)$ $U$ $PROTI$

Neboť označujeme hustotou rozložení hran mezi těmito množinami, tzn. $S\subset U,T\subset V$ $d(S,T)$

d(S,T)={\frac {\#\left\lbrace {(u,v)\in E:u\in S,v\in T}\right\rbrace }{|S|| T|}}

Definice [1] [3]

Bipartitní graf se nazývá -uniformní, pokud pro všechny splňují podmínky , nerovnost $G=(U\sqcup V,E)$ $\varepsilon$ $S\subset U,T\subset V$ $|S|>\varepsilon |U|,|T|>\varepsilon |V|$

|d(S,T)-d(U,V)|\leq \varepsilon

Existuje několik definic, které jsou tomu ekvivalentní (ekvivalentní ve smyslu existence monotónní závislosti v jedné definici od druhé, když jsou obě definice ekvivalentní), ale všechny používají kvantitu a nějaký druh kvantitativního srovnání jejích hodnot. pro různé páry . $\varepsilon$ $\varepsilon$ $d(S,T)$ $SVATÝ$

Je zřejmé, že úplné a prázdné bipartitní grafy jsou -běžné pro všechny . Je třeba poznamenat, že obecně to neplatí pro libovolný bipartitní graf, který je v obvyklém smyslu regulární (za protipříklad můžeme považovat například spojení několika pravidelných grafů, které se v množině neprotínají z vrcholů). $\varepsilon$ $\varepsilon >0$

$\varepsilon$ -jednotné grafy pro danou věc se někdy také nazývají pseudonáhodné , protože jsou podobné náhodně generovaným grafům z hlediska rovnoměrného rozložení hran mezi vrcholy. $\varepsilon$

Výrok lemmatu

Szemerediho lemma pravidelnosti [3] [4]

Pro any existuje takové, že pro jakýkoli graf s počtem vrcholů existuje rozdělení na části co nejstejnější velikosti , takže pro dvojice těchto částí je bipartitní graf hran ležících mezi nimi -pravidelný. $\varepsilon >0,\m\geq 2$ ${\displaystyle M,n_{0))$ $G=(V,E)$ $|V|>n_{0}$ $V=V_{1}\sqcup \dots \sqcup V_{k}\ (m\leq k\leq M)$ $|V_{1}|=\dots =|V_{k-1}|\geq |V_{k}|$ $(1-\varepsilon ){\binom {k}{2))$ $\varepsilon$

Poznámky

Szemerediho lemma neklade žádná omezení na hrany mezi vrcholy ze stejné množiny oddílů.

Výrok lemmatu je netriviální pouze pro grafy s dostatečně velkým počtem hran. Jestliže , pak kterýkoli z jeho bipartitních podgrafů na částech s rozměry bude také řídký (jeho hustota nepřesáhne ) - podmínka rozdílu hustot bude tedy vždy splněna. [5] $|E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}$ ${\frac {\varepsilon }{k}}|V|$ $\varepsilon$

Je třeba také poznamenat, že zmínka o stejné proměnné ve dvou různých charakteristikách – index pravidelnosti a podíl – pravidelných bipartitních podgrafů – nevytváří žádný další vztah mezi těmito charakteristikami. Taková formulace by vyplývala i ze slabší formulace, kde by se například vyžadovalo, aby hrany byly rozmístěny pravidelně pouze mezi dvojicemi množin, kde pro (tedy i pro ). V tomto případě by pro dosažení původní formulace stačilo uvažovat , protože -pravidelnost grafu znamená -pravidelnost v . $\varepsilon$ $\varepsilon$ $\varepsilon$ $(1-\eta ){\binom {k}{2}}$ $\eta =\eta (\varepsilon )\to 0$ $\varepsilon \to 0$ $\eta >\varepsilon$ $\varepsilon _{0}=\eta ^{-1}(\varepsilon )$ $\varepsilon_{0}$ $\varepsilon$ $\varepsilon _{0}<\varepsilon$

Důkaz

Rozdělovací algoritmus

Rozdělení se provádí pomocí chamtivého algoritmu.

Nejprve se zvolí libovolné rozdělení vrcholů do množin , kde: $V_{1},\dots ,V_{k}$

$|V_{1}|=\dots =|V_{k-1}|>|V_{k}|$
$k=\max \left({{\frac {1}{\varepsilon )),m}\right)$

Dále, při každé iteraci algoritmu je určitým způsobem generován nový oddíl z existujícího oddílu s menšími velikostmi dílů a velkým počtem z nich. Je postaven jako poddělení původního oddílu, ale pak je normalizován malými přestavbami tak, aby velikosti všech (možná kromě jedné) části byly stejné.

Taková transformace pokračuje, dokud výsledné rozdělení na množiny neobsahuje alespoň dvojice množin, jejichž bipartitní grafy jsou neregulární . Přechod z jednoho oddílu do druhého probíhá tak, že je možné dokázat, že se algoritmus zastaví přesně po konečném a omezeném konstantním (v závislosti na a ) počtu kroků. Kromě toho je také omezen počet výsledných sad v oddílu v každé konkrétní iteraci algoritmu, takže maximální počet sad, které lze vytvořit při poslední iteraci, bude požadovanou hodnotou . [3] $k'$ $\varepsilon {\binom {k'}{2))$ $\varepsilon$ $\varepsilon$ $m$ $M$

Přechod od dělení k dělení

Nechť aktuální rozdělení nesplňuje podmínky lemmatu, to znamená, že existují dvojice , pro které není bipartitní graf mezi nimi -regulární. Označme tuto podmínku jako . ${\mathcal {P}}=(V_{1},\tečky ,V_{k})$ $\varepsilon {\binom {k}{2}}$ $(V_{i},V_{j}),i\not =j$ $\varepsilon$ $P_{\varepsilon }(V_{i},V_{j})$

Pokud , pak existují určité konkrétní "problémové" podmnožiny , které porušují -regularitu bipartitního grafu spojujícího tyto komponenty. Tedy pro ně: $P_{\varepsilon }(V_{i},V_{j})$ ${\displaystyle S_{ij}\in V_{i},S_{ji}\in V_{j))$ $\varepsilon$

$|S_{ij}|>\varepsilon |V_{i}|$
$|S_{ji}|>\varepsilon |V_{j}|$
$|d(S_{ij},S_{ji})-d(V_{i},V_{j})|>\varepsilon$

Vypadá to jako rozumný nápad zbavit se těchto problematických podmnožin tím, že je jednoduše oddělíte do samostatné komponenty, čímž vznikne čtveřice místo dvojice komponent . Jedna a ta samá součást však může kolidovat s několika dalšími součástmi najednou, takže rozdělení by se nemělo provádět po jedné, ale po několika sadách problémů najednou. $(V_{i},V_{j})$ $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$ $V_i$

Abychom tento proces formalizovali, pro každou jednotlivou komponentu se berou v úvahu všechny „problémové“ podmnožiny, které v něm vznikají: $V_i$

{\mathcal {S}}(V_{i})=\left\lbrace {S_{ij}:1\leq j\leq k,P_{\varepsilon }(V_{i},V_{j} )}\vpravo\rbrace

a σ-algebra vzniklá na (tj. je rozdělena na takové části, že libovolné dva vrcholy, z nichž jeden k některému patří a druhý k němu nepatří, skončí v různých částech poddělení). ${\mathcal {S}}(V_{i})$ $V_i$ $V_i$ $S_{{ij}}$

Vzhledem k tomu, že pro jednotlivce neexistují žádné problematičtější podmnožiny (a tím pádem ani další prvky σ-algebry na nich konstruované), v důsledku toho se z jedné složky netvoří další nové . $V_i$ $k-1$ $2^{k-1}$ $2^{k-1}$

Pokud tímto způsobem rozdělíte každou komponentu , získáte nové dělení . $V_i$ ${\mathcal {P}}'$

Dále je potřeba zarovnat velikosti komponent (kterých není více než ). K tomu lze každou její složku rozdělit na nové složky velikosti (a případně jednu zbývající složku menší velikosti - "zbytek") a všechny vrcholy ze "zbytků" libovolně kombinovat do nové součástky stejné velikosti a případně o jednu menší součástku. ${\mathcal {P}}'$ $k2^{k-1}$ $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$ $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$

Výsledný oddíl bude výsledkem jedné iterace algoritmu.

Odhad počtu kroků v algoritmu

Důkaz zastavení algoritmu po konečném počtu kroků se provádí zavedením potenciální funkce - číselné hodnoty, která závisí na aktuálním oddílu - a sledováním její změny při změně iterací algoritmu.

"Potenciál" může být definován například takto:

\Phi ({\mathcal {P}})=\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{{\frac {|V_{i}| |V_{j}|}{|V|^{2}}}d(V_{i},V_{j})^{2}}

Tato funkce má několik důležitých vlastností:

$0\leq \Phi ({\mathcal {P))\leq 1$

pokud je oddíl tvořen rozdělením jedné složky na dvě sady a , pak ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\tečky ,V_{k})$ $V_{1}$ $S\subset V_{1}$ $V_{1}\setminus S$ $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$

Důkaz

To vyplývá z nerovnosti , což platí pro , což znamená nerovnost $(x+y)^{2}\leq {\frac {1}{\alpha }}x^{2}+{\frac {1}{\beta }}y^{2}$ $\alpha +\beta =1$

{\frac {E(V_{1},V_{j})^{2}}{|V_{1}|}}\leq {\frac {E(S,V_{j})^{ 2}}{|S|}}+{\frac {E(V_{1}\setminus S,V_{j})^{2}}{|V_{1}\setminus S|}}

pro rozdělení z algoritmu popsaného v předchozí části je pravda ${\mathcal {P}}'$ $\Phi ({\mathcal {P))')>\Phi ({\mathcal {P)))+\Omega (\varepsilon ^{5})$

pokud je oddíl získán z oddílu přerozdělením vrcholů několika komponent na nějaké jiné komponenty (ne nutně pododdíl), pak ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\tečky ,V_{k})$ $V_{1},\tečky ,V_{s}$ $\Phi ({\mathcal {Q))\geq \Phi ({\mathcal {P)))-{\frac {|V_{1}|+\dots +|V_{s}|}{ | V|}}$

Důkaz

Stačí ukázat, že sjednocení se zmenšuje nejvýše o (další dělení nesnižuje , podle jiné vlastnosti). $V_{1},\tečky ,V_{s}$ $\Phi$ ${\frac {|V_{1}|+\tečky +|V_{s}|}{|V|}}$ $\Phi$

Když se komponenty spojí , některé pojmy ze součtu zmizí a některé se objeví nové. Protože všechny termíny jsou kladné, stačí vzít v úvahu ty, které mizí. Součet těchto výrazů lze snadno odhadnout: $\Phi$

$\sum \limits _{i=1}^{s}{\sum \limits _{j>i}({\frac {|V_{i}||V_{j}|}{|V| ^{2}}}d(V_{i},V_{j})}}\leq \sum \limits _{i=1}^{s}{|V_{i}|\součet \limits _{j >i}{\frac {|V_{j}|}{|V|^{2))))\leq {\frac {1}{|V|^{2))}\sum \limits _{i =1}^{s}{|V_{i}|\sum \limits _{j=1}^{k}{|V_{j}|}}={\frac {|V_{1}|+\ tečky +|V_{s}|}{|V|}}$

Vzhledem k tomu, že při získávání nového oddílu se podle algoritmu v pododdělení nepřebudovává více než vrcholy, a protože pro dostatečně velké pro jakoukoli konstantu , vyplývá z vlastností potenciální funkce, že se algoritmus po krocích zastaví . ${\mathcal {P}}'$ $k2^{k-1}\left\lfloor {\frac {n}{{(k2^{k-1})}^{2))}\right\rfloor \leq {\frac {n} {k2^{k-1}}}$ ${\frac {1}{k2^{k-1}}}<c\varepsilon ^{5}$ $k$ $C$ $O\left({\frac {1}{\varepsilon ^{5))}\right)$

V první práci na toto téma použil Szemeredi mírně odlišnou potenciální funkci [1] :

\Phi ({\mathcal {P)))={\frac {1}{|{\mathcal {P}}|^{2}}}\sum \limits _{1\leq i<j\ leq |{\mathcal {P}}|}{d(V_{i},V_{j})^{2}}

Navzdory rozdílům obě tyto funkce sdílejí myšlenku průměrování čtvercových hustot.

Odhad velikosti oddílu

Jak vyplývá z popisu algoritmu, horní odhad počtu komponent v oddílu při -té iteraci algoritmu je vyjádřen rekurzivním vztahem $n$

a_{n}={a_{n}}^{2}2^{a_{n}-1}

Počet iterací, kterými algoritmus projde, se odhaduje jako . $O\left({\frac {1}{\varepsilon ^{5))}\right)$

Proto lze celkový počet komponent odhadnout pouze pomocí věže, která se zvedá do síly výšky . ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k))))))$ $O\left({\frac {1}{\varepsilon ^{5))}\right)$

Efektivní rozdělený vyhledávací algoritmus

Typický matematický důkaz Szemerediho lemmatu se nestará o výpočetní složitost algoritmu.

Skupina pěti matematiků však v samostatném článku zkoumala algoritmický aspekt nalezení požadovaného rozdělení - konkrétně popsali algoritmus, který umožňuje najít rozdělení -vertexového grafu v čase pro pevné a . Doba běhu jejich algoritmu je omezena dobou násobení dvou matic složených z nul a jedniček. Algoritmus lze také paralelizovat a provádět v čase na polynomiálně závislém na počtu procesorů. [6] $n$ $O(n^{2,376})$ $\varepsilon$ $m$ $n\krát n$ $O(\log{n})$ $n$

Dolní hranice velikosti požadovaného oddílu

V roce 1997 William Gowers ukázal, že odhad velikosti počtu komponent v požadovaném oddílu nelze zlepšit více než do výšky exponent tower . Ukázal totiž, že vždy existuje graf, jehož jakékoli rozdělení na menší počet částí nesplňuje podmínky lemmatu. ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k))))))$ $O\left({\log {\left({\frac {1}{\varepsilon }}\right)))\right)$

Uvažoval o ještě obecnějším pojmu -regularity, kde podmnožina částí bipartitního grafu , jehož odchylka hustoty je omezena definicí, je omezena namísto , a také pro to dokázal existenci protipříkladu. $(\varepsilon, \delta)$ $S\subset U,T\subset V$ $|S|\geq \delta |U|,|T|\geq \delta |V|$ $|S|\geq \varepsilon |U|,|T|\geq \varepsilon |V|$

Gowers použil pravděpodobnostní metodu k nalezení protipříkladu , takže jeho důkaz není konstruktivní . Práce uvažovala vážené grafy s váhami z intervalu . U takových grafů můžeme uvažovat o zcela podobné formulaci lemmatu, kde za hustotu budeme považovat součet vah hran místo jejich počtu. Sestrojením protipříkladu ve formě váženého grafu Gowers také ukázal, že náhodný graf generovaný Bernoulliho schématem s hranovými pravděpodobnostmi odpovídajícími vahám v tomto váženém grafu bude s vysokou pravděpodobností protipříkladem obvyklého lemmatu (navíc, s vysokou pravděpodobností se hustoty nebudou výrazně lišit od podobných hustot ve váženém grafu za předpokladu, že a jsou dostatečně velké). [7] $(0;1)$ $d(U,V)$ $d(U,V)$ $|U|$ $|V|$

Gowersův design

Vážený graf, který slouží jako protipříklad k lemmatu s obvyklou definicí -regularity, je konstruován jako kombinace s různými váhami několika specificky uspořádaných velkých grafů. Při konstrukci každého dalšího grafu z této množiny se vrcholy spojují do větších a větších skupin stejné velikosti tak, že vrcholy ze dvou různých skupin jsou buď vzájemně spojeny úplným bipartitním grafem, nebo nejsou spojeny vůbec (nové skupiny jsou vždy spojeny). spojení předchozích). $\varepsilon$

Nechť jsou vrcholy rozděleny do stejně velkých skupin. Spojte tyto skupiny do bloků $X_{1},\dots ,X_{s}$

B_{1}=(X_{1},\tečky ,X_{t})

B_{2}=(X_{t+1},\tečky ,X_{2t})

\tečky

B_{k}=(X_{(m-1)t+1},\tečky ,X_{s})

kde (předpokládejme, že je to celé číslo). $k={\frac {s}{t))$

Pro každou dvojici různých bloků zvolíme rozdělení skupin z na dvě části a rozdělení skupin z na dvě části. Přidejte do grafu všechny hrany úplných bipartitních grafů a . $(B_{i},B_{j})$ ${\displaystyle B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2)))$ $Bi}$ ${\displaystyle B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2)))$ $B_j$ $(B_{ij}^{(1)},B_{ji}^{(1)})$ $(B_{ij}^{(2)},B_{ji}^{(2)})$

Pokud jsou oddíly vybrány tak, že žádný , patřící do stejného , nemá žádné další bloky, ve kterých jsou vrcholy sousedící s oběma, pak při správném výběru bude výsledná konstrukce Gowersova konstrukce. Ale to je konstrukce pouze jednoho grafu - pro sestavení dalšího grafu jsou bloky umístěny na místo skupin a celý proces začíná znovu, dokud nejsou všechny vrcholy spojeny do jedné skupiny. $X_{j},X_{j'}$ $Bi}$ ${\frac {3}{4}}k$ $s$ $t$ ${\displaystyle B_{1},\tečky ,B_{m))$ $X_{1},\dots ,X_{s}$

Výsledný řetězec grafů se spojí do váženého grafu podle vzorce (největší váhy mají grafy, ve kterých jsou sdružené skupiny vrcholů velmi velké). $G_{1},\tečky ,G_{s}$ $G=\sum \limits _{r=1}^{s}{2^{rs-1}G_{r))$

Protipříklad pro -regularity je konstruován podobným způsobem, ale s několika rozdíly: $(\varepsilon, \delta)$

skupiny v rámci jednoho bloku nejsou rozděleny do dvou, do libovolného počtu sad ; $Bi}$ $d$ ${\displaystyle B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d)))$

počet skupin v každé sadě je omezen velikostí (neměly by být příliš malé); ${\displaystyle B_{i}^{(j)))$

na konci jsou výsledné grafy spojeny nikoli ve formě váženého grafu, ale výhradním „nebo“ (výsledný graf zahrnuje pouze ty hrany, které byly přítomny v lichém počtu grafů ). $G_{1},\tečky ,G_{s}$ $G_{r},1\leq r\leq s$

Zobecnění

V roce 2007 William Gowers zobecnil lemma regularity na hypergrafy a použil zobecnění k prokázání Szemerédyho multidimenzionálního teorému. [osm]

Existuje také analogie Szemerediho lemmatu pro řídké grafy (v obvyklé formulaci je lemma pro takové grafy triviální, protože jakékoli rozdělení splňuje nezbytné podmínky). [9]

Aplikace

Nejznámější aplikace lemmatu regularity je pro kombinatorický důkaz Szemerediho věty a jejích zobecnění (například rohová věta ). [5] Avšak lemma a jeho myšlenky mají řadu aplikací i v obecné teorii grafů [10] - Szemeredyho první článek o tomto lemmatu je citován ve více než 500 pracích na různá témata. [jeden]

Zvláště zajímavé je také lemma pro odstranění trojúhelníku , které je odvozeno od lemmatu regularity a používá se při důkazu Szemerediho věty.

Viz také

Endre Semeredy
Szemerediho věta
Eliminační lemma trojúhelníku

Poznámky

↑ 1 2 3 4 E. Szemeredi, "Pravidelné dělení grafů", Katedra informatiky, School of Humanities and Sciences, Stanford University, 1975
↑ E. Szemeredi, "Regular partitions of graphs", Katedra informatiky, School of Humanities and Sciences, Stanford University, 1975 . Získáno 29. července 2018. Archivováno z originálu dne 23. února 2020. (neurčitý)
↑ 1 2 3 „Mini kurz aditivní kombinatoriky“, poznámky k přednášce Princetonské univerzity . Získáno 29. července 2018. Archivováno z originálu 29. srpna 2017. (neurčitý)
↑ Matematická laboratoř. Čebyšev, kurz přednášek "Aditivní kombinatorika", přednáška 3
↑ 1 2 I. D. Shkredov, „Szemerediho věta a problémy aritmetických posloupností“ . Získáno 29. července 2018. Archivováno z originálu 24. července 2018. (neurčitý)
↑ N. Alon, R. A. Duke, H. Lefmann, V. Rodl, R. Yusterk, "Algorithmic Aspects of the Regularity Lemma", Tel Aviv University . Získáno 29. července 2018. Archivováno z originálu 8. srpna 2017. (neurčitý)
↑ WT Gowers, „Dolní hranice typu věže pro Szemerédiho lemma uniformity“, Geometric & Functional Analysis GAFA, květen 1997, svazek 7, vydání 2, str. 322–337 . Získáno 29. července 2018. Archivováno z originálu 18. června 2018. (neurčitý)
↑ WT Gowers, „Hypergraph regularity and the multidimenzionální Szemer´ediho teorém“, Annals of Mathematics, 166 (2007), 897–946 . Získáno 29. července 2018. Archivováno z originálu dne 20. července 2018. (neurčitý)
↑ Y. Kohayakawa, „Szemerediho lemma pravidelnosti pro řídké grafy“ . Získáno 29. července 2018. Archivováno z originálu 10. června 2018. (neurčitý)
↑ Janos Komlos, Miklos Simonovits, „Szemerediho lemma pravidelnosti a jeho aplikace v teorii grafů“, Rutgers University, Maďarská akademie věd . Datum přístupu: 29. července 2018. Archivováno z originálu 23. dubna 2005. (neurčitý)

Slovníky a encyklopedie	Britannica (online)