Szemedi säännöllisyyden lemma

Szemedin säännönmukaisuuslemma on lemma yleisestä graafiteoriasta , jossa sanotaan, että minkä tahansa riittävän suuren graafin kärjet voidaan jakaa äärelliseen määrään ryhmiä siten, että lähes kaikissa kahden eri ryhmän pisteitä yhdistävissä bipartite -grafeissa on reunat, jotka jakautuvat lähes tasaisesti pisteiden välillä. Tällöin vaadittava vähimmäismäärä ryhmiä, joihin graafin kärkijoukko on jaettava, voi olla mielivaltaisen suuri, mutta osion ryhmien määrä on aina ylhäältä rajattu.

Epävirallisesti puhuttaessa lemma vakuuttaa suuren määrän suuria näennäissatunnaisia rakenteita absoluuttisesti missä tahansa riittävän suuressa graafissa.

Lemman todisti Endre Szemeredy vuonna 1975. [1] [2]

Sanamuoto

ε-yhdenmukaisuuden käsite

Olkoon kaksiosainen graafi, jonka reunat yhdistävät joukon kärjet joukon kärkipisteisiin . $G=(W=U\sqcup V,E)$ $U$ $V$

Sillä merkitsemme näiden joukkojen välisten reunojen jakautumisen tiheydellä, eli $S\subset U,T\subset V$ $d(S,T)$

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

Määritelmä [1] [3]

Kaksiosaista graafia kutsutaan -uniformiksi, jos jokaiselle, joka täyttää ehdot , epäyhtälö $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

On olemassa useita määritelmiä, jotka vastaavat tätä (vastaa siinä mielessä, että määritelmässä on monotoninen riippuvuus toisesta , kun kaksi määritelmää ovat samanarvoisia), mutta ne kaikki käyttävät määrää ja jonkinlaista kvantitatiivista sen arvojen vertailua. eri pareille . $\varepsilon$ $\varepsilon$ $d(S,T)$ $S,T$

Ilmeisesti täydelliset ja tyhjät kaksiosaiset graafit ovat -säännöllisiä mille tahansa . On huomattava, että yleisesti ottaen tämä ei pidä paikkaansa mielivaltaiselle kaksiosaiselle graafille, joka on säännöllinen tavallisessa merkityksessä (vastaesimerkkinä voidaan harkita esimerkiksi useiden säännöllisten graafien liittoa, jotka eivät leikkaa joukossa pisteistä). $\varepsilon$ $\varepsilon >0$

$\varepsilon$ -yhtenäisiä graafisia tietylle tiedolle kutsutaan joskus myös pseudosatunnaisiksi , koska ne ovat samankaltaisia kuin satunnaisesti luodut, mitä tulee kulmien tasaiseen jakautumiseen pisteiden välillä. $\varepsilon$

Lausunto lemmasta

Szemedin säännönmukaisuuslemma [3] [4]

Jokaiselle , on olemassa sellainen, että mille tahansa graafille , jossa on useita pisteitä , on olemassa osio mahdollisimman samankokoisiksi osiksi siten , että näiden osien pareille niiden välissä olevien reunojen kaksiosainen graafi on -säännöllinen. $\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$

Muistiinpanot

Szemeredin lemma ei aseta rajoituksia saman osiojoukon kärkien välisille reunoille.

Lemman lause on ei-triviaali vain graafille, jossa on riittävän paljon reunoja. Jos , niin mikä tahansa sen kaksiosainen osagraafi osissa, joilla on mitat , on myös harva (sen tiheys ei ylitä ) - näin ollen tiheyseron ehto täyttyy aina. [5] $|E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}$ ${\frac {\varepsilon }{k}}|V|$ $\varepsilon$

On myös huomattava, että saman muuttujan mainitseminen kahdessa eri ominaisuudessa - säännöllisyysindeksissä ja -säännöllisten kaksiosaisten aligraafien osuudessa - ei luo lisäsuhdetta näiden ominaisuuksien välille. Tällainen muotoilu seuraisi myös heikommalta formulaatiolta, jossa vaadittaisiin esimerkiksi, että reunat jakautuvat säännöllisesti vain joukkoparien kesken, missä for (eli jopa : lle ). Tässä tapauksessa alkuperäisen muotoilun saavuttamiseksi riittäisi huomioida , koska -kaavion säännöllisyys edellyttää -säännöllisyyttä kohdassa . $\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$

Todiste

Osiointialgoritmi

Osiointi tapahtuu ahneella algoritmilla.

Ensin valitaan mielivaltainen kärkien osio joukoiksi , jossa: $V_{1},\dots ,V_{k}$

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

Lisäksi jokaisessa algoritmin iteraatiossa olemassa olevasta osiosta luodaan tietyllä tavalla uusi osio, jossa on pienempiä osia ja niitä on suuri määrä. Se on rakennettu alkuperäisen osion alaosastoksi, mutta sitten se normalisoidaan pienin uudelleenjärjestelyin siten, että kaikkien (ei ehkä yhtä) osien koot ovat yhtä suuret.

Tällainen muunnos jatkuu, kunnes tuloksena oleva osio joukoiksi sisältää vähintään joukkopareja, joiden kaksiosaiset graafit ovat epäsäännöllisiä . Siirtyminen osiosta toiseen tapahtuu siten, että on mahdollista todistaa, että algoritmi pysähtyy tarkalleen äärellisen jälkeen ja jota rajoittaa vakio (riippuen ja ) askelmäärästä. Lisäksi tuloksena olevien joukkojen lukumäärä osiossa kussakin tietyssä algoritmin iteraatiossa on myös rajoitettu, joten viimeisellä iteraatiolla muodostettavien joukkojen enimmäismäärä on haluttu arvo . [3] $k'$ $\varepsilon {\binom {k'}{2))$ $\varepsilon$ $\varepsilon$ $m$ $M$

Siirtyminen jakamisesta edelleen jakamiseen

Älköön nykyinen osio täytä lemman ehtoja, eli on pareja , joiden välinen kaksiosainen graafi ei ole -säännöllinen. Merkitään tämä ehto muodossa . ${\mathcal {P}}=(V_{1},\pisteet ,V_{k})$ $\varepsilon {\binom {k}{2))$ $(V_{i},V_{j}),i\not =j$ $\varepsilon$ $P_{\varepsilon }(V_{i},V_{j})$

Jos , niin tietyt "ongelma"-alajoukot rikkovat näitä komponentteja yhdistävän kaksiosaisen graafin -säännöllisyyttä. Eli heille: $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$

Vaikuttaa järkevältä idealta päästä eroon näistä ongelmallisista osajoukoista yksinkertaisesti erottamalla ne erilliseksi komponentiksi muodostamalla nelinkertainen komponenttiparin sijaan . Yksi ja sama komponentti voi kuitenkin olla ristiriidassa useiden muiden komponenttien kanssa kerralla, joten jakamista ei tulisi tehdä yksitellen, vaan useiden ongelmaryhmien mukaan kerralla. ${\näyttötyyli (V_{i}, V_{j})}$ $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$ $V_i$

Tämän prosessin virallistamiseksi kunkin yksittäisen komponentin osalta otetaan huomioon kaikki siinä esiintyvät "ongelma"-alajoukot: $V_i$

{\mathcal {S}}(V_{i})=\left\lhakasulku {S_{ij}:1\leq j\leq k,P_{\varepsilon }(V_{i},V_{j} )}\oikea\rhaulu

ja kohtaan muodostettu σ-algebra ( eli se on jaettu sellaisiin osiin, että mikä tahansa kaksi kärkeä, joista toinen kuuluu jollekin ja toinen ei, päätyy alajaon eri osiin). ${\mathcal {S}}(V_{i})$ $V_i$ $V_i$ $S_{{ij}}$

Koska yksilölle ei ole enää ongelmallisia osajoukkoja (eikä niille rakenneta enää σ-algebran alkioita), ei yhdestä komponentista muodostu enää uusia . $V_i$ $k-1$ $2^{k-1}$ $2^{k-1}$

Jos jaat jokaisen komponentin tällä tavalla , saat uuden alajaon . $V_i$ ${\mathcal {P))'$

Seuraavaksi sinun on kohdistettava komponenttien koot (joita ei ole enempää kuin ). Tätä varten kukin sen komponenteista voidaan jakaa uusiin kokoisiin komponentteihin (ja mahdollisesti yhdeksi jäljellä olevaksi pienemmäksi komponentiksi - "jäännökseksi"), ja kaikki "jäännösten" kärjet voidaan yhdistää mielivaltaisesti uudet samankokoiset komponentit ja mahdollisesti yksi pienempi komponenttikoko. ${\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$

Tuloksena oleva osio on algoritmin yhden iteroinnin tulos.

Algoritmin vaiheiden määrän arvioiminen

Todistus algoritmin pysähtymisestä äärellisen askelmäärän jälkeen suoritetaan ottamalla käyttöön potentiaalinen funktio - nykyisestä osiosta riippuva numeerinen arvo - ja seuraamalla sen muutosta, kun algoritmin iteraatioita muutetaan.

"Potentiaali" voidaan määritellä esimerkiksi seuraavasti:

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

Tällä toiminnolla on useita tärkeitä ominaisuuksia:

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

jos osio muodostetaan jakamalla yksi komponentti kahteen joukkoon ja , sitten ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\pisteet ,V_{k})$ $V_{1}$ $S\subset V_{1}$ $V_{1}\setminus S$ $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$

Todiste

Tämä seuraa epätasa-arvosta , joka pätee kohtaan , joka sisältää epätasa-arvon $(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|}}

osioinnin osalta edellisessä osiossa kuvatun algoritmin perusteella, on totta ${\mathcal {P))'$ $\Phi ({\mathcal {P))')>\Phi ({\mathcal {P)))+\Omega (\varepsilon ^{5})$

jos osio saadaan osiosta osioimalla useiden komponenttien kärjet joiksikin muiksi komponenteiksi (ei välttämättä aliosion avulla), niin ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\pisteet ,V_{k})$ $V_{1},\dots ,V_{s}$ $\Phi ({\mathcal {Q))\geq \Phi ({\mathcal {P)))-{\frac {|V_{1}|+\dots +|V_{s}|}{ | V|}}$

Todiste

Riittää, kun osoitetaan, että liitto pienenee korkeintaan (lisäjako ei pienennä toisen ominaisuuden mukaan). $V_{1},\dots ,V_{s}$ $\Phi$ ${\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ $\Phi$

Kun komponentit yhdistetään , osa termeistä häviää summasta ja joitain uusia ilmaantuu. Koska kaikki termit ovat positiivisia, riittää, kun tarkastellaan niitä, jotka katoavat. Tällaisten termien summa on helppo arvioida: $\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}|+\ pisteet +|V_{s}|}{|V|}}$

Koska uutta osiota hankittaessa, algoritmin mukaan, alajakoon rakennetaan uudelleen korkeintaan kärkipisteitä ja koska riittävän suurelle mille tahansa vakiolle , potentiaalifunktion ominaisuuksista seuraa, että algoritmi pysähtyy vaiheiden jälkeen. ${\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))}\oikea)$

Ensimmäisessä tätä aihetta käsittelevässä työssä Szemedi käytti hieman erilaista potentiaalifunktiota [1] :

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

Eroista huolimatta molemmilla näillä funktioilla on ajatus neliötiheyksien keskiarvoistamisesta.

Osion koon arvioiminen

Kuten algoritmin kuvauksesta seuraa, osion komponenttien lukumäärän ylempi arvio algoritmin -. iteraatiossa ilmaistaan rekursiivisella suhteella. $n$

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

Algoritmin suorittamien iteraatioiden lukumääräksi arvioidaan . $O\left({\frac {1}{\varepsilon ^{5))}\oikea)$

Siksi komponenttien kokonaismäärä voidaan arvioida vain korkeustehoon nostetun tornin avulla . ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k)))))))$ $O\left({\frac {1}{\varepsilon ^{5))}\oikea)$

Tehokas jaettu hakualgoritmi

Tyypillinen Szemedin lemman matemaattinen todistus ei välitä algoritmin laskennallisesta monimutkaisuudesta .

Kuitenkin viiden matemaatikon ryhmä erillisessä artikkelissa tutki halutun osion löytämisen algoritmista - erityisesti he kuvasivat algoritmin, joka mahdollistaa -vertex-graafin osion löytämisen ajoissa kiinteälle ja . Niiden algoritmin ajoaikaa rajoittaa kahden noloista ja ykkösistä koostuvan matriisin kertomisaika. Algoritmi voidaan myös rinnakkaista ja suorittaa ajallaan polynomisesti riippuen prosessorien määrästä. [6] $n$ $O(n^{2,376})$ $\varepsilon$ $m$ $n\ kertaa n$ $O(\log{n})$ $n$

Vaaditun osion koon alaraja

Vuonna 1997 William Gowers osoitti, että arviota tarvittavan osion komponenttien lukumäärästä ei voida parantaa enempää kuin korkeuseksponenttitorniin asti . Nimittäin hän osoitti, että aina on olemassa graafi, jonka mikä tahansa osio pienempään määrään osia ei täytä lemman ehtoja. ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k)))))))$ $O\left({\log {\left({\frac {1}{\varepsilon }}\right)))\right)$

Hän tarkasteli vielä yleisempää -säännönmukaisuuden käsitettä , jossa kaksiosaisen graafin osien osajoukkoa , jonka tiheyspoikkeama määritelmä rajoittaa, on rajoitettu sijasta , ja todisti myös vastaesimerkin olemassaolon. $(\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 käytti probabilistista menetelmää löytääkseen vastaesimerkin , joten hänen todisteensa ei ole rakentava . Paperi käsitteli painotettuja kaavioita intervallin painoilla . Tällaisille kaavioille voidaan harkita täysin samanlaista lemman formulaatiota, jossa tiheyttä pidetään reunojen painojen summana niiden lukumäärän sijaan. Muodostamalla vastaesimerkin painotetun graafin muodossa Gowers osoitti myös, että Bernoulli- kaaviolla generoitu satunnainen graafi, jonka reunatodennäköisyydet vastaavat tämän painotetun graafin painoja, on suurella todennäköisyydellä vastaesimerkki tavalliselle lemmalle (lisäksi, suurella todennäköisyydellä tiheydet eivät poikkea voimakkaasti samanlaisista tiheydistä painotetussa kaaviossa, jos ja ovat riittävän suuria). [7] $(0;1)$ $d(U,V)$ $d(U,V)$ $|U|$ $|V|$

Gowersin suunnittelu

Painotettu graafi, joka toimii vastaesimerkkinä lemmalle tavallisella -säännöllisyyden määritelmällä, on muodostettu yhdistelmänä useiden erityisesti järjestettyjen suurten graafien eri painoilla. Kun kutakin seuraavaa graafia tästä joukosta rakennetaan, kärjet yhdistetään suurempiin ja suurempiin samankokoisiin ryhmiin siten, että kahden eri ryhmän kärjet joko yhdistetään toisiinsa täydellisellä kaksiosaisella graafilla tai niitä ei yhdistetä ollenkaan (uusia ryhmiä syntyy aina aiempien liitto). $\varepsilon$

Olkoon kärjet jaettu samankokoisiin ryhmiin. Yhdistä nämä ryhmät lohkoiksi $X_{1},\dots ,X_{s}$

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

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

\pisteet

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

missä (oletetaan, että se on kokonaisluku). $k={\frac {s}{t))$

Jokaiselle eri lohkoparille valitsemme ryhmien osion kahteen osaan ja ryhmien osion kahteen osaan. Lisää kuvaajaan kaikki täydellisten kaksiosaisten graafien reunat ja . ${\näyttötyyli (B_{i},B_{j})}$ ${\displaystyle B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2)))$ $B_{i}$ ${\displaystyle B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2)))$ $B_j$ $(B_{ij}^{(1)},B_{ji}^{(1)})$ ${\näyttötyyli (B_{ij}^{(2)},B_{ji}^{(2)})}$

Jos osiot valitaan siten, että millään samaan ryhmään kuuluvalla ei ole enää lohkoja, joissa molempien vieressä on kärkipisteitä, niin oikealla valinnalla tuloksena on Gowersin konstruktio. Mutta tämä on vain yhden graafin rakentaminen - seuraavan graafin rakentamiseksi lohkot laitetaan ryhmien tilalle ja koko prosessi alkaa alusta, kunnes kaikki kärjet yhdistetään yhdeksi ryhmäksi. ${\displaystyle X_{j},X_{j'))$ $B_{i}$ ${\frac {3}{4}}k$ $s$ $t$ ${\displaystyle B_{1},\dots ,B_{m))$ $X_{1},\dots ,X_{s}$

Tuloksena oleva graafinen ketju yhdistetään painotetuksi graafiksi kaavan mukaan (suurimmat painot ovat kaavioilla, joissa yhdistetyt kärkiryhmät ovat erittäin suuria). $G_{1},\dots ,G_{s}$ $G=\sum \limits _{r=1}^{s}{2^{rs-1}G_{r))$

Vastaesimerkki -säännöllisyydelle on rakennettu samalla tavalla, mutta muutamalla erolla: $(\varepsilon, \delta)$

yhden lohkon ryhmiä ei jaeta kahteen, mielivaltaiseen joukkoon ; $B_{i}$ $d$ ${\displaystyle B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d)))$

ryhmien lukumäärä kussakin sarjassa on rajoitettu koon mukaan (ne eivät saa olla liian pieniä); ${\displaystyle B_{i}^{(j)))$

lopussa saadut graafit yhdistetään ei painotetun graafin muodossa, vaan poissulkevalla "tai" :lla (lopullinen graafi sisältää vain ne reunat, jotka olivat läsnä parittomassa määrässä kaavioita ). $G_{1},\dots ,G_{s}$ $G_{r},1\leq r\leq s$

Yleistykset

Vuonna 2007 William Gowers yleisti säännönmukaisuuslemman hypergrafeiksi ja käytti yleistystä todistaakseen Szemerédyn moniulotteisen lauseen. [kahdeksan]

Szemeredin lemmalle on olemassa myös analogi harvalle graafille (tavallisessa formulaatiossa lemma on triviaali sellaisille graafeille, koska mikä tahansa osio täyttää tarvittavat ehdot). [9]

Sovellukset

Tunnetuin säännönmukaisuuslemman sovellus on Szemedin lauseen ja sen yleistysten kombinatorinen todistus (esim. kulmalause ). [5] Lemalla ja sen ideoilla on kuitenkin lukuisia sovelluksia myös yleisessä graafiteoriassa [10] - Szemedyn ensimmäinen tätä lemmaa käsittelevä artikkeli on lainattu yli 500 eri aihetta käsittelevässä artikkelissa. [yksi]

Erityisen kiinnostava on myös kolmion poistolemma , joka on johdettu säännönmukaisuuslemasta ja jota käytetään Szemedin lauseen todistuksen yhteydessä.

Katso myös

Endre Semeredy
Szemedin lause
Kolmion poistolemma

Muistiinpanot

↑ 1 2 3 4 E. Szemedi, "Säännölliset kaavioiden osiot", Tietojenkäsittelytieteen osasto, Humanististen ja tieteiden korkeakoulu, Stanfordin yliopisto, 1975
↑ E. Szemedi, "Säännölliset kaavioiden osiot", Tietojenkäsittelytieteen osasto, Humanististen ja tieteiden korkeakoulu, Stanfordin yliopisto, 1975 . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 23. helmikuuta 2020. (määrätön)
↑ 1 2 3 "Additiivisen kombinatoriikan minikurssi", Princetonin yliopiston luentomuistiinpanot . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 29. elokuuta 2017. (määrätön)
↑ Matemaattinen laboratorio. Chebyshev, luentokurssi "Additiivinen kombinatoriikka", luento 3
↑ 1 2 I. D. Shkredov, "Szemeredin lause ja aritmeettisen progression ongelmat" . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 24. heinäkuuta 2018. (määrätön)
↑ N. Alon, R.A. Duke, H. Lefmann, V. Rodl, R. Yusterk, "The Algorithmic Aspects of the Regularity Lemma", Tel Avivin yliopisto . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 8. elokuuta 2017. (määrätön)
↑ WT Gowers, "Szemerédin yhtenäisyyslemman tornityypin alarajat", Geometric & Functional Analysis GAFA, toukokuu 1997, osa 7, numero 2, s. 322–337 . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 18. kesäkuuta 2018. (määrätön)
↑ WT Gowers, "Hypergraafin säännöllisyys ja moniulotteinen Szemer´edi-lause", Annals of Mathematics, 166 (2007), 897–946 . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 20. heinäkuuta 2018. (määrätön)
↑ Y. Kohayakawa, "Szemeredin säännöllisyyslemma harvoille kaavioille" . Haettu 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 10. kesäkuuta 2018. (määrätön)
↑ Janos Komlos, Miklos Simonovits, "Szemeredin säännöllisyyslemma ja sen sovellukset graafiteoriassa", Rutgersin yliopisto, Unkarin tiedeakatemia . Käyttöpäivä: 29. heinäkuuta 2018. Arkistoitu alkuperäisestä 23. huhtikuuta 2005. (määrätön)

Sanakirjat ja tietosanakirjat	Britannica (verkossa)