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]
Nechť je dán bipartitní graf, jehož hrany spojují vrcholy z množiny s vrcholy z množiny .
Neboť označujeme hustotou rozložení hran mezi těmito množinami, tzn.
.
Bipartitní graf se nazývá -uniformní, pokud pro všechny splňují podmínky , nerovnost |
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 .
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ů).
-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.
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ý. |
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]
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 .
Rozdělení se provádí pomocí chamtivého algoritmu.
Nejprve se zvolí libovolné rozdělení vrcholů do množin , kde:
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]
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 .
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ě:
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.
Abychom tento proces formalizovali, pro každou jednotlivou komponentu se berou v úvahu všechny „problémové“ podmnožiny, které v něm vznikají:
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í).
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é .
Pokud tímto způsobem rozdělíte každou komponentu , získáte nové dělení .
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.
Výsledný oddíl bude výsledkem jedné iterace 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:
Tato funkce má několik důležitých vlastností:
To vyplývá z nerovnosti , což platí pro , což znamená nerovnost
Stačí ukázat, že sjednocení se zmenšuje nejvýše o (další dělení nesnižuje , podle jiné vlastnosti).
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:
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í .
V první práci na toto téma použil Szemeredi mírně odlišnou potenciální funkci [1] :
Navzdory rozdílům obě tyto funkce sdílejí myšlenku průměrování čtvercových hustot.
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
Počet iterací, kterými algoritmus projde, se odhaduje jako .
Proto lze celkový počet komponent odhadnout pouze pomocí věže, která se zvedá do síly výšky .
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]
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.
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.
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]
Gowersův designVáž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).
Nechť jsou vrcholy rozděleny do stejně velkých skupin. Spojte tyto skupiny do bloků
,kde (předpokládejme, že je to celé číslo).
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 .
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.
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é).
Protipříklad pro -regularity je konstruován podobným způsobem, ale s několika rozdíly:
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]
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.
![]() |
---|