Lema de regularitate Szemeridi

Lema de regularitate a lui Szemeredi este o lemă din teoria generală a grafurilor , care afirmă că vârfurile oricărui graf suficient de mare pot fi împărțite într-un număr finit de grupuri, astfel încât aproape toate graficele bipartite care conectează vârfurile din două grupuri diferite au muchii distribuite aproape uniform între vârfuri. În acest caz, numărul minim necesar de grupuri în care trebuie împărțit setul de vârfuri ale graficului poate fi arbitrar mare, dar numărul de grupuri din partiție este întotdeauna mărginit de sus.

Vorbind informal, lema afirmă prezența unui număr mare de structuri pseudoaleatoare mari în absolut orice grafic de dimensiune suficient de mare.

Lema a fost demonstrată de Endre Szemeredy în 1975. [1] [2]

Formulare

Conceptul de ε-uniformitate

Să fie dat un graf bipartit ale cărui muchii conectează vârfurile din mulțime cu vârfurile din mulțime . $G=(W=U\sqcup V,E)$ $U$ $V$

Căci notăm prin densitatea distribuției muchiilor dintre aceste mulțimi, adică $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|}}

Definiție [1] [3]

Un graf bipartit se numește -uniform dacă pentru oricare care îndeplinește condițiile , inegalitatea $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

Există mai multe definiții care sunt echivalente cu aceasta (echivalent în sensul existenței unei dependențe monotone într-o definiție față de alta atunci când cele două definiții sunt echivalente), dar toate folosesc o cantitate și un fel de comparație cantitativă a valorilor acesteia. pentru diferite perechi de . $\varepsilon$ $\varepsilon$ $d(S,T)$ $SF$

În mod evident, graficele bipartite complete și goale sunt -regular pentru orice . Trebuie remarcat faptul că, în general, acest lucru nu este valabil pentru un graf bipartit arbitrar care este regulat în sensul obișnuit (ca contraexemplu, putem lua în considerare, de exemplu, unirea mai multor grafuri regulate care nu se intersectează în mulțime). de vârfuri). $\varepsilon$ $\varepsilon >0$

$\varepsilon$ Graficele -uniforme pentru un dat sunt uneori numite și pseudo-aleatoare , deoarece sunt similare cu cele generate aleator în ceea ce privește distribuția uniformă a muchiilor între vârfuri. $\varepsilon$

Enunțul lemei

Lema de regularitate a lui Szemeredi [3] [4]

Pentru orice , există astfel încât pentru orice graf cu un număr de vârfuri să existe o partiție în părți cât mai egale ca mărime , astfel încât pentru perechile acestor părți graficul bipartit al muchiilor care se află între ele este -regular. $\varepsilon >0,\m\geq 2$ $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$

Note

Lema lui Szemeredi nu impune nicio restricție asupra muchiilor dintre vârfuri din același set de partiții.

Declarația lemei este netrivială numai pentru graficele cu un număr suficient de mare de muchii. Dacă , atunci oricare dintre subgrafele sale bipartite pe părți cu dimensiuni va fi, de asemenea, rare (densitatea sa nu va depăși ) - prin urmare, condiția privind diferența de densitate va fi întotdeauna îndeplinită. [5] $|E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}$ ${\frac {\varepsilon {k}}|V|$ $\varepsilon$

De asemenea, trebuie remarcat faptul că menționarea aceleiași variabile în două caracteristici diferite - indicele de regularitate și proporția -subgrafelor bipartite regulate - nu creează nicio relație suplimentară între aceste caracteristici. O astfel de formulare ar urma și dintr-o formulare mai slabă, unde ar fi necesar, de exemplu, ca muchiile să fie distribuite în mod regulat numai între perechi de mulțimi, unde pentru (adică chiar și pentru ). În acest caz, pentru a realiza formularea inițială, ar fi suficient să luăm în considerare , deoarece -regularitatea graficului implică -regularitatea la . $\varepsilon$ $\varepsilon$ $\varepsilon$ $(1-\eta ){\binom {k}{2)}$ $\eta =\eta (\varepsilon)\la 0$ $\varepsilon \to 0$ $\eta >\varepsilon$ $\varepsilon _{0}=\eta ^{-1}(\varepsilon )$ $\varepsilon_{0}$ $\varepsilon$ $\varepsilon _{0}<\varepsilon$

Dovada

Algoritm de partiționare

Partiționarea se face printr-un algoritm greedy.

În primul rând, se alege o partiție arbitrară a vârfurilor în mulțimi , unde: $V_{1},\dots ,V_{k}$

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

Mai mult, la fiecare iterație a algoritmului, o nouă partiție este generată într-un anumit mod din partiția existentă cu dimensiuni mai mici de părți și un număr mare de ele. Este construit ca o subdiviziune a partiției originale, dar apoi este normalizat prin mici rearanjamente, astfel încât dimensiunile tuturor (cu excepția, poate, a uneia) părți să fie egale.

O astfel de transformare continuă până când partiția rezultată în mulțimi conține cel puțin perechi de mulțimi ale căror grafice bipartite sunt neregulate. Trecerea de la o partiție la alta are loc în așa fel încât este posibil să se demonstreze că algoritmul se oprește exact după un număr finit și mărginit de un număr constant (în funcție de și ) de pași. În plus, numărul de seturi rezultate din partiție la fiecare iterație specifică a algoritmului este de asemenea limitat, astfel încât numărul maxim de seturi care pot fi formate la ultima iterație va fi valoarea dorită . [3] $k'$ $\varepsilon {\binom {k'}{2)}$ $\varepsilon$ $\varepsilon$ $m$ $M$

Trecerea de la divizare la subdivizare

Fie ca partiția curentă să nu satisfacă condițiile lemei, adică există perechi pentru care graficul bipartit dintre ele nu este -regulat. Să notăm această condiție ca . ${\mathcal {P}}=(V_{1},\dots, V_{k})$ $\varepsilon {\binom {k}{2}}$ $(V_{i}, V_{j}), i\not =j$ $\varepsilon$ $P_{\varepsilon}(V_{i},V_{j})$

Dacă , atunci există anumite subseturi de „problemă” care încalcă -regularitatea grafului bipartit care conectează aceste componente. Adică pentru ei: $P_{\varepsilon}(V_{i},V_{j})$ $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$

Pare o idee rezonabilă să scăpați de aceste submulțimi problematice prin simpla separare a acestora într-o componentă separată, formând un cvadruplu în loc de o pereche de componente . Cu toate acestea, una și aceeași componentă poate intra în conflict cu mai multe alte componente simultan, așa că împărțirea ar trebui să se facă nu unul câte unul, ci prin mai multe seturi de probleme deodată. $(V_{i},V_{j})$ $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$ $V_i$

Pentru a oficializa acest proces, pentru fiecare componentă individuală , sunt luate în considerare toate subseturile „probleme” care apar în el: $V_i$

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

iar σ-algebra formată pe (adică este subdivizată în astfel de părți încât oricare două vârfuri, dintre care unul aparține unora , iar celălalt nu îi aparține, să ajungă în părți diferite ale subdiviziunii). ${\mathcal {S}}(V_{i})$ $V_i$ $V_i$ $S_{{ij}}$

Deoarece pentru un individ nu mai există submulțimi problematice (și, în consecință, nu mai există elemente ale σ-algebrei construite pe ele), ca urmare, nu se mai formează altele noi dintr-o componentă. $V_i$ $k-1$ $2^{k-1}$ $2^{k-1}$

Dacă subdivizați fiecare componentă în acest fel , obțineți o nouă subdiviziune . $V_i$ ${\mathcal {P}}'$

Apoi, trebuie să aliniați dimensiunile componentelor (din care nu există mai mult de ). Pentru a face acest lucru, fiecare dintre componentele sale poate fi împărțită în noi componente ale mărimii (și, eventual, o componentă rămasă de o dimensiune mai mică - „restul”), iar toate vârfurile din „rămășii” pot fi combinate în mod arbitrar în componente noi de aceeași dimensiune și, eventual, o dimensiune mai mică a componentei. ${\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$

Partiția rezultată va fi rezultatul unei iterații a algoritmului.

Estimarea numărului de pași dintr-un algoritm

Dovada opririi algoritmului după un număr finit de pași se realizează prin introducerea unei funcție potențiale - o valoare numerică care depinde de partiția curentă - și urmărirea modificării acesteia la schimbarea iterațiilor algoritmului.

„Potențial” poate fi definit, de exemplu, după cum urmează:

\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}}

Această funcție are o serie de proprietăți importante:

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

dacă partiția este formată prin subîmpărțirea unei componente în două seturi și , atunci ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\dots, V_{k})$ $V_{1}$ $S\subset V_{1}$ $V_{1}\setminus S$ $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$

Dovada

Aceasta rezultă din inegalitatea , care este adevărată pentru , care implică inegalitatea $(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|}}

pentru partiţionarea din algoritmul descris în secţiunea anterioară, este adevărată ${\mathcal {P}}'$ $\Phi ({\mathcal {P))')>\Phi ({\mathcal {P)})+\Omega (\varepsilon ^{5})$

dacă o partiție este obținută dintr-o partiție prin repartiționarea vârfurilor mai multor componente în alte componente (nu neapărat printr-o subpartiție), atunci ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\dots, V_{k})$ $V_{1},\dots ,V_{s}$ $\Phi ({\mathcal {Q))\geq \Phi ({\mathcal {P)})-{\frac {|V_{1}|+\dots +|V_{s}|}{ | V|}}$

Dovada

Este suficient să arătăm că unirea se reduce cu cel mult (subdiviziunea ulterioară nu reduce , după o altă proprietate). $V_{1},\dots ,V_{s}$ $\Phi$ ${\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ $\Phi$

Când componentele sunt combinate , unii termeni dispar din sumă și apar alții noi. Deoarece toți termenii sunt pozitivi, este suficient să luăm în considerare cei care dispar. Suma acestor termeni este ușor de estimat: $\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}|\sum \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}|+\ puncte +|V_{s}|}{|V|}}$

Deoarece, la obținerea unei noi partiții, conform algoritmului, nu se reconstruiesc mai mult de vârfuri în subdiviziune și deoarece pentru suficient de mare pentru orice constantă , din proprietățile funcției potențiale rezultă că algoritmul se va opri după pași. ${\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)$

În prima lucrare pe această temă, Szemeredi a folosit o funcție potențială ușor diferită [1] :

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

În ciuda diferențelor, ambele aceste funcții împărtășesc ideea de a media densitățile pătrate.

Estimarea dimensiunii unei partiții

După cum reiese din descrierea algoritmului, estimarea superioară a numărului de componente din partiție la a --a iterație a algoritmului este exprimată prin relația recursivă $n$

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

Numărul de iterații prin care va funcționa algoritmul este estimat ca . $O\left({\frac {1}{\varepsilon ^{5)}}\right)$

Prin urmare, numărul total de componente poate fi estimat doar printr-un turn de ridicare la puterea înălțimii . ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k)}))))$ $O\left({\frac {1}{\varepsilon ^{5)}}\right)$

Algoritm eficient de căutare divizată

Demonstrația matematică tipică a lemei lui Szemeredi nu-i pasă de complexitatea computațională a algoritmului.

Cu toate acestea, un grup de cinci matematicieni într-o lucrare separată a investigat aspectul algoritmic al găsirii partiției dorite - în special, au descris un algoritm care permite găsirea unei partiții a unui grafic -vertex în timp pentru fix și . Timpul de rulare al algoritmului lor este limitat de timpul de înmulțire a două matrici formate din zerouri și unu. De asemenea, algoritmul poate fi paralelizat și executat în timp pe un polinom dependent de numărul de procesoare. [6] $n$ $O(n^{2,376})$ $\varepsilon$ $m$ $n\ ori n$ $O(\log{n})$ $n$

Limita inferioară a dimensiunii partiției necesare

În 1997, William Gowers a arătat că estimarea pentru dimensiunea numărului de componente din partiția necesară nu poate fi îmbunătățită mai mult decât până la turnul exponent de înălțime . Și anume, el a arătat că există întotdeauna un grafic, orice partiție a căruia într-un număr mai mic de părți nu satisface condițiile lemei. ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k)}))))$ $O\left({\log {\left({\frac {1}{\varepsilon }}\right)))\right)$

El a considerat o noțiune și mai generală de -regularitate, în care un subset de părți ale unui graf bipartit , a cărui abatere de densitate este limitată de definiție, sunt constrânse în loc de , și a demonstrat, de asemenea, existența unui contraexemplu pentru acesta. $(\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 a folosit o metodă probabilistă pentru a găsi un contraexemplu , astfel încât demonstrația sa nu este constructivă . Lucrarea a luat în considerare grafice ponderate cu ponderi din intervalul . Pentru astfel de grafice, putem considera o formulare complet similară a lemei, unde densitatea va fi considerată suma greutăților muchiilor în loc de numărul lor. Construind un contraexemplu sub forma unui grafic ponderat, Gowers a mai arătat că un grafic aleator generat de schema Bernoulli cu probabilități de muchie corespunzătoare ponderilor din acest grafic ponderat va fi cu o probabilitate mare un contraexemplu pentru lema obișnuită (mai mult, cu o mare probabilitate densitățile nu se vor abate puternic de la densitățile similare într-un grafic ponderat cu condiția ca și să fie suficient de mari). [7] $(0;1)$ $d(U,V)$ $d(U,V)$ $|U|$ $|V|$

Designul lui Gowers

Un grafic ponderat, care servește ca un contraexemplu pentru lema cu definiția obișnuită a -regularității, este construit ca o combinație cu ponderi diferite a mai multor grafice mari aranjate în mod specific. Când se construiește fiecare graf următor din această mulțime, vârfurile sunt combinate în grupuri din ce în ce mai mari de dimensiuni egale, astfel încât vârfurile din două grupuri diferite fie fie conectate între ele printr-un graf bipartit complet, fie deloc conectate (grupurile noi sunt întotdeauna o unire a celor anterioare). $\varepsilon$

Lăsați vârfurile să fie împărțite în grupuri de aceeași dimensiune. Combinați aceste grupuri în blocuri $X_{1},\dots ,X_{s}$

B_{1}=(X_{1},\dots, X_{t})

B_{2}=(X_{t+1},\dots, X_{2t})

\dots

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

unde (presupunem că este un număr întreg). $k={\frac {s}{t)}$

Pentru fiecare pereche de blocuri diferite, alegem o partiție a grupurilor din două părți și o partiție a grupurilor din două părți. Adăugați la grafic toate muchiile graficelor bipartite complete și . $(B_{i}, B_{j})$ $B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2))$ $B_{i}$ $B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2))$ $B j$ $(B_{ij}^{(1)}, B_{ji}^{(1)})$ $(B_{ij}^{(2)}, B_{ji}^{(2)})$

Dacă partițiile sunt alese în așa fel încât orice , aparținând aceluiași , să nu mai aibă blocuri în care există vârfuri adiacente ambelor, atunci cu selecția corectă , construcția rezultată va fi construcția Gowers. Dar aceasta este construcția unui singur grafic - pentru a construi următorul grafic, blocurile sunt puse în loc de grupuri și întregul proces începe din nou până când toate vârfurile sunt combinate într-un singur grup. $X_{j},X_{j'}$ $B_{i}$ ${\frac {3}{4}}k$ $s$ $t$ $B_{1},\dots, B_{m)$ $X_{1},\dots ,X_{s}$

Lanțul de grafice rezultat este combinat într-un grafic ponderat conform formulei (graficele în care grupurile combinate de vârfuri sunt foarte mari au cele mai mari ponderi). $G_{1},\dots ,G_{s}$ $G=\sum \limits _{r=1}^{s}{2^{rs-1}G_{r))$

Contraexemplul pentru -regularitate este construit într-un mod similar, dar cu câteva diferențe: $(\varepsilon, \delta)$

grupurile dintr-un bloc nu sunt împărțite în două, într-un număr arbitrar de mulțimi ; $B_{i}$ $d$ $B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d))$

numărul de grupuri din fiecare set este limitat de mărime (nu trebuie să fie prea mici); $B_{i}^{(j))$

la sfârșit, graficele rezultate sunt combinate nu sub forma unui grafic ponderat, ci printr-un „sau” exclusiv (graficul final include doar acele muchii care au fost prezente într-un număr impar de grafice ). $G_{1},\dots ,G_{s}$ $G_{r},1\leq r\leq s$

Generalizări

În 2007, William Gowers a generalizat lema de regularitate la hipergrafe și a folosit generalizarea pentru a demonstra teorema multidimensională a lui Szemerédy. [opt]

Există, de asemenea, un analog al lemei lui Szemeredi pentru graficele rare (în formularea obișnuită, lema este trivială pentru astfel de grafice, deoarece orice partiție îndeplinește condițiile necesare). [9]

Aplicații

Cea mai cunoscută aplicație a lemei de regularitate este pentru demonstrarea combinatorie a teoremei Szemeredi și a generalizărilor acesteia (de exemplu, teorema colțului ). [5] Cu toate acestea, lema și ideile sale au o serie de aplicații și în teoria generală a grafurilor [10] - Prima lucrare a lui Szemeredy despre această lemă este citată în peste 500 de lucrări pe diverse subiecte. [unu]

De asemenea, de interes deosebit este Lema de îndepărtare a triunghiului , care este derivată din lema de regularitate și este utilizată în cursul demonstrației teoremei lui Szemeredi.

Vezi și

Endre Semeredy
teorema lui Szemeredi
Lema de eliminare a triunghiului

Note

↑ 1 2 3 4 E. Szemeredi, „Regular partitions of graphs”, departamentul de informatică, Școala de Științe Umaniste și Științe, Universitatea Stanford, 1975
^ E. Szemeredi , „Regular partitions of graphs”, departamentul de informatică, Școala de Științe Umaniste și Științe, Universitatea Stanford, 1975 . Preluat la 29 iulie 2018. Arhivat din original la 23 februarie 2020. (nedefinit)
↑ 1 2 3 „Mini curs de combinatorică aditivă”, note de curs de la Universitatea Princeton . Preluat la 29 iulie 2018. Arhivat din original la 29 august 2017. (nedefinit)
↑ Laborator de matematică. Cebyshev, curs de prelegeri „Combinatorică aditivă”, prelegerea 3
↑ 1 2 I. D. Shkredov, „Teorema lui Szemeredi și probleme privind progresiile aritmetice” . Preluat la 29 iulie 2018. Arhivat din original la 24 iulie 2018. (nedefinit)
↑ N. Alon, R.A. Duke, H. Lefmann, V. Rodl, R. Yusterk, „The Algorithmic Aspects of the Regularity Leemma”, Universitatea din Tel Aviv . Preluat la 29 iulie 2018. Arhivat din original la 8 august 2017. (nedefinit)
^ WT Gowers, „Lower bounds of tower type for Szemerédi's uniformity leemma”, Geometric & Functional Analysis GAFA, mai 1997, volumul 7, numărul 2, pp 322–337 . Preluat la 29 iulie 2018. Arhivat din original la 18 iunie 2018. (nedefinit)
^ WT Gowers, „Regularitatea hipergrafului și teorema multidimensională Szemer´edi”, Annals of Mathematics, 166 (2007), 897–946 . Preluat la 29 iulie 2018. Arhivat din original la 20 iulie 2018. (nedefinit)
^ Y. Kohayakawa , „Szemeredi's Regularity Leemma for Sparse Graphs” . Preluat la 29 iulie 2018. Arhivat din original la 10 iunie 2018. (nedefinit)
↑ Janos Komlos, Miklos Simonovits, „Szemeredi’s Regularity Leemma and its applications in graph theory”, Universitatea Rutgers, Academia Maghiară de Științe . Data accesului: 29 iulie 2018. Arhivat din original la 23 aprilie 2005. (nedefinit)

Dicționare și enciclopedii	Britannica (online)