Szemerédi muntazamlik lemmasi - Szemerédi regularity lemma

Qismlar orasidagi qirralar o'zlarini "tasodifiy" tarzda tutishadi.

Szemeredi muntazamlik lemma eng kuchli vositalardan biridir ekstremal grafikalar nazariyasi, ayniqsa katta zich grafikalarni o'rganishda. Unda har bir cho'qqining etarlicha kattaligi ko'rsatilgan grafik qismlarning chegaralangan soniga bo'linishi mumkin, shunda turli qismlar orasidagi qirralar deyarli tasodifiy harakat qiladi.

Lemma bo'yicha, grafik qanchalik katta bo'lmasin, biz uni cheklangan sonli qismlar orasidagi chekka zichlik bilan taxminiy qilishimiz mumkin. Ikkala qism o'rtasida qirralarning taqsimlanishi chekka zichligi bo'yicha soxta tasodifiy bo'ladi. Ushbu taxminlar grafikaning turli xil xususiyatlari uchun, masalan, berilgan subgrafning ko'milgan nusxalari soni yoki ba'zi bir subgraflarning barcha nusxalarini olib tashlash uchun zarur bo'lgan chekkalarni o'chirish soni kabi to'g'ri qiymatlarni beradi.

Bayonot

Szemeredi muntazamlik lemmasini rasmiy ravishda bayon qilish uchun, biz "deyarli tasodifiy" harakat qiladigan qismlar orasidagi chekka taqsimot aslida nimani anglatishini rasmiylashtirishimiz kerak. "Deyarli tasodifiy" so'zlar bilan biz tushunchani nazarda tutamiz $ε$ - muntazamlik. Buning ma'nosini tushunish uchun avval ba'zi ta'riflarni keltiramiz. Keyinchalik nima bo'ladi $G$ bilan grafik tepalik o'rnatilgan $V$ .

Ta'rif 1. Ruxsat bering $X, Y$ ning bo'linmagan bo'linmalari $V$ . The chekka zichligi juftlik $(X, Y)$ quyidagicha aniqlanadi:
${ displaystyle d (X, Y): = { frac { left | E (X, Y) right |} {| X || Y |}}}$
qayerda $E (X, Y)$ bitta uchi vertikal bo'lgan qirralarning to'plamini bildiradi $X$ va bitta $Y$ .

Muntazam juftlikning pastki juftliklari chekka zichligi bo'yicha asl juftlikka o'xshashdir.

Biz bir juft qismni chaqiramiz $ε$ - muntazam ravishda, agar siz har bir qismning katta to'plamini olsangiz, ularning chekka zichligi juft qismning chekka zichligidan unchalik uzoq emas. Rasmiy ravishda,

Ta'rif 2. Uchun $ε> 0$ , bir juft tepalik to'plami $X$ va $Y$ deyiladi $ε$ - muntazam, agar barcha kichik guruhlar uchun $A \subseteq X$ , $B \subseteq Y$ qoniqarli $| A | \geq ε | X |$ , $| B | \geq ε | Y |$ , bizda ... bor
${ displaystyle left | d (X, Y) -d (A, B) right | leq varepsilon.}$

An ni aniqlashning tabiiy usuli $ε$ - muntazam bo'linma har bir juft qism joylashgan bo'lishi kerak $ε$ - muntazam. Biroq, ba'zi bir grafikalar, masalan yarim grafikalar, ko'plab juft qismlarni (lekin barcha juftlarning kichik qismini) tartibsiz bo'lishini talab qiladi.^[1] Shunday qilib, biz aniqlaymiz $ε$ - muntazam qismlar, bu qismlarning ko'p qismi joylashgan joy $ε$ - muntazam.

Ta'rif 3. Ning bo'limi ${ displaystyle V}$ ichiga ${ displaystyle k}$ to'plamlar ${ displaystyle { mathcal {P}} = {V_ {1}, ldots, V_ {k} }}$ deyiladi ${ displaystyle varepsilon}$ - muntazam bo'lim agar
${ displaystyle sum _ {(V_ {i}, V_ {j}) { text {not}} varepsilon { text {-regular}}} | V_ {i} || V_ {j} | leq varepsilon | V (G) | ^ {2}}$

Endi biz lemmani aytishimiz mumkin:

Szemerédi muntazamligi Lemmasi. Har bir kishi uchun $ε> 0$ va ijobiy tamsayı $m$ butun son mavjud $M$ agar shunday bo'lsa $G$ hech bo'lmaganda grafik $M$ vertices, butun son mavjud $k$ oralig'ida $m \leq k \leq M$ va an $ε$ - vertex to'plamining muntazam bo'limi $G$ ichiga $k$ to'plamlar.

Bog'langan $M$ Semeredining qonuniyligi lemmasining dalillari bilan berilgan grafik qismidagi qismlar soni uchun juda katta, a tomonidan berilgan $O (ε.) -5)$ - darajasining takrorlangan eksponentligi $m$ . Bir vaqtning o'zida bir nechta foydali dasturlarga ega bo'lgan haqiqiy chegara ancha kichikroq deb umid qilgandilar. Ammo Gowers (1997) buning uchun grafikalar namunalarini topdi $M$ haqiqatan ham juda tez o'sadi va hech bo'lmaganda a ga teng $ε -1/16$ - darajasining takrorlangan eksponentligi $m$ . Xususan, eng yaxshi chegara to'liq 4-darajaga ega Grzegorchik iyerarxiyasi va shunday emas elementar rekursiv funktsiya.^[2]

Isbot

Shaxsiy tartibsizliklarga guvohlik berish chegaralari bo'limning har bir qismini yaxshilaydi.

Algoritm bo'yicha berilgan grafik uchun ε muntazam bo'linmani topamiz. Qisqa kontur:

Ixtiyoriy qismdan boshlang (faqat 1 qism bo'lishi mumkin)
Bo'lim odatiy bo'lmagan bo'lsa-da:
- Har bir noqonuniy juftlik uchun ε-tartibsizlikka guvoh bo'lgan pastki qismlarni toping.
- Bir vaqtning o'zida barcha guvohlik beradigan pastki qismlardan foydalangan holda bo'limni yaxshilang.

Biz deb nomlangan texnikani qo'llaymiz energiya ortishi argumenti bu jarayon cheklangan sonli qadamlardan so'ng tugashini ko'rsatish uchun. Asosan, biz har bir qadamda ma'lum miqdorga ko'payishi kerak bo'lgan monovariantni aniqlaymiz, lekin u yuqorida chegaralangan va shuning uchun abadiy o'sishi mumkin emas. Ushbu monovariant "energiya" deb nomlanadi, chunki u ${ displaystyle L ^ {2}}$ miqdor.

Ta'rif 4. Ruxsat bering $U, V$ pastki qismlar bo'lishi $V$ . O'rnatish ${ displaystyle | V | = n}$ . The energiya juftlik $(U, V)$ quyidagicha aniqlanadi:
${ displaystyle q (U, W): = { frac {| U || W |} {n ^ {2}}} d (U, W) ^ {2}}$
Bo'limlar uchun ${ displaystyle { mathcal {P}} _ {U} = {U_ {1}, ldots, U_ {k} }}$ ning $U$ va ${ displaystyle { mathcal {P}} _ {W} = {W_ {1}, ldots, W_ {l} }}$ ning $V$ , biz energiyani har bir juft qism orasidagi energiya yig'indisi sifatida aniqlaymiz:
${ displaystyle q ({ mathcal {P}} _ {U}, { mathcal {P}} _ {W}): = sum _ {i = 1} ^ {k} sum _ {j = 1 } ^ {l} q (U_ {i}, W_ {j})}$
Nihoyat, bo'lim uchun ${ displaystyle { mathcal {P}} = {V_ {1}, ldots, V_ {k} }}$ ning $V$ , ning energiyasini aniqlang ${ displaystyle { mathcal {P}}}$ bolmoq ${ displaystyle q ({ mathcal {P}}, { mathcal {P}})}$ . Xususan,
${ displaystyle q ({ mathcal {P}}) = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {k} q (V_ {i}, V_ {j}) = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {k} { frac {| V_ {i} || V_ {j} |} {n ^ {2}}} d (V_ {i}, V_ {j}) ^ {2}}$

Energiya 0 dan 1 gacha bo'lganligiga e'tibor bering, chunki chekka zichligi yuqorida 1 bilan chegaralangan:

{ displaystyle q ({ mathcal {P}}) = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {k} { frac {| V_ {i} || V_ {j} |} {n ^ {2}}} d (V_ {i}, V_ {j}) ^ {2} leq sum _ {i = 1} ^ {k} sum _ {j = 1 } ^ {k} { frac {| V_ {i} || V_ {j} |} {n ^ {2}}} = 1}

Keling, energiya noziklashganda kamaymasligini isbotlashdan boshlaymiz.

Lemma 1. (Energiya qismlarga bo'linishda kamaymaydi) Har qanday bo'lim uchun ${ displaystyle { mathcal {P}} _ {U}}$ va ${ displaystyle { mathcal {P}} _ {W}}$ tepalik to'plamlari ${ displaystyle U}$ va ${ displaystyle W}$ , ${ displaystyle q ({ mathcal {P}} _ {U}, { mathcal {P}} _ {W}) geq q (U, W)}$ .

Isbot: Ruxsat bering ${ displaystyle { mathcal {P}} _ {U} = {U_ {1}, ldots, U_ {k} }}$ va ${ displaystyle { mathcal {P}} _ {W} = {W_ {1}, ldots, W_ {l} }}$ . Tepaliklarni tanlang ${ displaystyle x}$ bir xil ${ displaystyle U}$ va ${ displaystyle y}$ bir xil ${ displaystyle W}$ , bilan ${ displaystyle x}$ qisman ${ displaystyle U_ {i}}$ va ${ displaystyle y}$ qisman ${ displaystyle W_ {j}}$ . Keyin tasodifiy o'zgaruvchini aniqlang ${ displaystyle Z = d (U_ {i}, W_ {j})}$ . Ning xususiyatlarini ko'rib chiqaylik ${ displaystyle Z}$ . Kutish
${ displaystyle mathbb {E} [Z] = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {l} { frac {| U_ {i} |} {| U |}} { frac {| W_ {j} |} {| W |}} d (U_ {i}, W_ {j}) = { frac {e (U, W)} {| U || W |}} = d (U, V)}$
Ikkinchi lahza
${ displaystyle mathbb {E} [Z ^ {2}] = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {l} { frac {| U_ {i} | } {| U |}} { frac {| W_ {j} |} {| W |}} d (U_ {i}, W_ {j}) ^ {2} = { frac {n ^ {2} } {| U || W |}} q ({ mathcal {P}} _ {U}, { mathcal {P}} _ {W})}$
Qavariqlik bilan, ${ displaystyle mathbb {E} [Z ^ {2}] geq mathbb {E} [Z] ^ {2}}$ . Qayta tartibga solish, biz buni tushunamiz ${ displaystyle q ({ mathcal {P}} _ {U}, { mathcal {P}} _ {W}) geq q (U, W)}$ Barcha uchun ${ displaystyle U, W}$ . ${ displaystyle square}$

Agar har bir qismi ${ displaystyle { mathcal {P}}}$ qo'shimcha qismlarga bo'linadi, yangi bo'lim takomillashtirish deb nomlanadi ${ displaystyle { mathcal {P}}}$ . Endi, agar ${ displaystyle { mathcal {P}} = {V_ {1}, ldots, V_ {m} }}$ , har bir juftga Lemma 1 ni qo'llash ${ displaystyle (V_ {i}, V_ {j})}$ har bir takomillashtirish uchun buni isbotlaydi ${ displaystyle { mathcal {P '}}}$ ning ${ displaystyle { mathcal {P}}}$ , ${ displaystyle q ({ mathcal {P '}}) geq q ({ mathcal {P}})}$ . Shunday qilib algoritmdagi takomillashtirish bosqichi hech qanday kuch yo'qotmaydi.

Lemma 2. (Energiyani kuchaytirish lemmasi) Agar ${ displaystyle (U, W)}$ emas ${ displaystyle varepsilon}$ - muntazam ravishda guvoh bo'lganidek ${ displaystyle U_ {1} subset U, W_ {1} subset W}$ , keyin,
${ displaystyle q chap ( {U_ {1}, U teskari burish U_ {1} }, {W_ {1}, W teskari burilish W_ {1} } o'ng)> q (U, W) + varepsilon ^ {4} { frac {| U || W |} {n ^ {2}}}}$

Isbot: Aniqlang ${ displaystyle Z}$ yuqoridagi kabi. Keyin,
${ displaystyle Var (Z) = mathbb {E} [Z ^ {2}] - mathbb {E} [Z] ^ {2} = { frac {n ^ {2}} {| U || W |}} chap (q chap ( {U_ {1}, U teskari burilish U_ {1} }, {W_ {1}, W teskari burilish W_ {1} } o'ng) -q (U , W) o'ng)}$
Ammo shunga e'tibor bering ${ displaystyle | Z- mathbb {E} [Z] | = | d (U_ {1}, W_ {1}) - d (U, W) |}$ ehtimollik bilan ${ displaystyle { frac {| U_ {1} |} {| U |}} { frac {| W_ {1} |} {| W |}}}$ (mos keladigan ${ displaystyle x U_ {1}} da$ va $W_ {1}} da { displaystyle y$ ), shuning uchun
${ displaystyle Var (Z) = mathbb {E} [(Z- mathbb {E} [Z]) ^ {2}] geq { frac {| U_ {1} |} {| U |}} { frac {| W_ {1} |} {| W |}} (d (U_ {1}, W_ {1}) - d (U, W)) ^ {2}> varepsilon cdot varepsilon cdot varepsilon ^ {2}}$ ${ displaystyle square}$

Endi biz energiya ortishi argumentini isbotlashimiz mumkin, bu algoritmning har bir takrorlanishida energiya sezilarli darajada ko'payishini ko'rsatadi.

Lemma 3 (Energiya o'sish lemmasi) Agar bo'lim bo'lsa ${ displaystyle { mathcal {P}} = {V_ {1}, ldots, V_ {k} }}$ ning ${ displaystyle V (G)}$ emas ${ displaystyle varepsilon}$ - muntazam, keyin aniqlik mavjud ${ displaystyle { mathcal {Q}}}$ ning ${ displaystyle { mathcal {P}}}$ qaerda har biri ${ displaystyle V_ {i}}$ ko'pi bilan bo'linadi ${ displaystyle 2 ^ {k}}$ shunday qismlar
${ displaystyle q ({ mathcal {Q}}) geq q ({ mathcal {P}}) + varepsilon ^ {5}.}$

Isbot: Barcha uchun ${ displaystyle (i, j)}$ shu kabi ${ displaystyle (V_ {i}, V_ {j})}$ emas ${ displaystyle varepsilon}$ - muntazam, toping ${ displaystyle A ^ {i, j} subset V_ {i}}$ va ${ displaystyle A ^ {j, i} subset V_ {j}}$ qonunbuzarlikning guvohi (barcha tartibsiz juftliklar uchun bir vaqtning o'zida bajaring). Ruxsat bering ${ displaystyle { mathcal {Q}}}$ umumiy takomillashtirish bo'lishi ${ displaystyle { mathcal {P}}}$ tomonidan ${ displaystyle A ^ {i, j}}$ . Har biri ${ displaystyle V_ {i}}$ ko'pi bilan bo'linadi ${ displaystyle 2 ^ {k}}$ kerakli qismlar. Keyin,
${ displaystyle q ({ mathcal {Q}}) = sum _ {(i, j) in [k] ^ {2}} q ({ mathcal {Q}} _ {V_ {i}}, { mathcal {Q}} _ {V_ {j}}) = sum _ {(V_ {i}, V_ {j}) { text {}} varepsilon { text {-regular}}} q ( { mathcal {Q}} _ {V_ {i}}, { mathcal {Q}} _ {V_ {j}}) + sum _ {(V_ {i}, V_ {j}) { text { not}} varepsilon { text {-regular}}} q ({ mathcal {Q}} _ {V_ {i}}, { mathcal {Q}} _ {V_ {j}})}$
Qaerda ${ displaystyle { mathcal {Q}} _ {V_ {i}}}$ ning bo'linishi ${ displaystyle V_ {i}}$ tomonidan berilgan ${ displaystyle { mathcal {Q}}}$ . Lemma 1 bo'yicha yuqoridagi miqdor kamida
${ displaystyle sum _ {(V_ {i}, V_ {j}) { text {}} varepsilon { text {-regular}}} q (V_ {i}, V_ {j}) + sum _ {(V_ {i}, V_ {j}) { text {not}} varepsilon { text {-regular}}} q ( {A ^ {i, j}, V_ {i} backslash A ^ {i, j} }, {A ^ {j, i}, V_ {j} teskari chiziq A ^ {j, i} })}$
Beri ${ displaystyle V_ {i}}$ tomonidan kesiladi ${ displaystyle A ^ {i, j}}$ yaratishda ${ displaystyle { mathcal {Q}}}$ , shuning uchun ${ displaystyle { mathcal {Q}} _ {V_ {i}}}$ takomillashtirish hisoblanadi ${ displaystyle {A ^ {i, j}, V_ {i} teskari chiziq A ^ {i, j} }}$ . 2-lemma bo'yicha yuqoridagi yig'indisi hech bo'lmaganda
${ displaystyle sum _ {(i, j) in [k] ^ {2}} q (V_ {i}, V_ {j}) + sum _ {(V_ {i}, V_ {j}) { text {not}} varepsilon { text {-regular}}} varepsilon ^ {4} { frac {| V_ {i} || V_ {j} |} {n ^ {2}}}}$
Ammo ikkinchi yig'indisi hech bo'lmaganda ${ displaystyle varepsilon ^ {5}}$ beri ${ displaystyle { mathcal {P}}}$ emas ${ displaystyle varepsilon}$ - muntazam, shuning uchun biz kerakli tengsizlikni chiqaramiz. ${ displaystyle square}$

Endi, har qanday bo'limdan boshlab, agar bo'linma bo'lmaganda Lemma 3 ni qo'llashimiz mumkin ${ displaystyle varepsilon}$ - muntazam. Ammo har bir qadamda energiya ortadi ${ displaystyle varepsilon ^ {5}}$ , va u yuqorida 1 bilan chegaralangan. Keyin bu jarayon eng ko'p takrorlanishi mumkin ${ displaystyle varepsilon ^ {- 5}}$ marta, u tugamasdan oldin va bizda bo'lishi kerak ${ displaystyle varepsilon}$ - muntazam bo'lim.

Ilovalar

Agar grafikaning muntazamligi to'g'risida etarli ma'lumotga ega bo'lsak, ma'lum bir subgrafning nusxalari sonini grafadagi kichik xatolarga qadar hisoblashimiz mumkin.

Graflarni hisoblash Lemmasi. Ruxsat bering ${ displaystyle H}$ bilan grafik bo'ling ${ displaystyle V (H) = [k]}$ va ruxsat bering ${ displaystyle varepsilon> 0}$ . Ruxsat bering ${ displaystyle G}$ bo'lish ${ displaystyle n}$ - vertex to'plamlari bilan vertex grafigi ${ displaystyle V_ {1}, dots, V_ {k} subseteq V (G)}$ shu kabi ${ displaystyle (V_ {i}, V_ {j})}$ bu ${ displaystyle varepsilon}$ - har doim ${ displaystyle {i, j } in E (H)}$ . Keyin, etiketli nusxalari soni ${ displaystyle H}$ yilda ${ displaystyle G}$ ichida ${ displaystyle e (H) varepsilon | V_ {1} | cdots | V_ {k} |}$ ning
${ displaystyle left ( prod _ { {i, j } in E (H)} d (V_ {i}, V_ {j}) right) left ( prod _ {i = 1} ^ {k} | V_ {i} | o'ng)}$

Buni Szemeredi muntazamligi lemmasi bilan birlashtirib, buni isbotlash mumkin Grafikni olib tashlash lemmasi. Grafikni olib tashlash lemmasi isbotlash uchun ishlatilishi mumkin Rotning "Arifmetik progressiyalar to'g'risida" teoremasi,^[3] va uni umumlashtirish, gipergrafiyani olib tashlash lemmasi, isbotlash uchun ishlatilishi mumkin Szemeredi teoremasi.^[4]

Grafikni olib tashlash lemmasi umumlashtiriladi induktsiya qilingan subgraflar, faqat cheklarni o'chirish o'rniga chekka tahrirlarni ko'rib chiqish orqali. Buni Alon, Fischer, Krivelevich va Szegedi 2000 yilda isbotladilar.^[5] Biroq, bu doimiylik lemmasining kuchliroq o'zgarishini talab qildi.

Szemeredi muntazamligi lemmasi muhim natijalarni bermaydi siyrak grafikalar. Siyrak grafikalar substantant chekka zichlikka ega bo'lgani uchun, ${ displaystyle varepsilon}$ - muntazamlik ahamiyatsiz qoniqtiriladi. Natija faqat nazariy ko'rinishga ega bo'lsa ham, ba'zi urinishlar ^[6]^[7] muntazamlik usulidan katta grafikalar uchun siqishni texnikasi sifatida foydalanish uchun qilingan.

Tarix va kengaytmalar

Szemeredi qonuniyligi lemmasining pastki chegarasi uchun Govers qurilishi

Semeredi (1975) isbotlash maqsadida dastlab ushbu lemmaning ikki tomonlama grafikalar bilan cheklangan zaif versiyasini taqdim etdi Szemeredi teoremasi,^[8]va (Szemerédi 1978 yil ) u to'liq lemmani isbotladi.^[9] Doimiylik usulining kengaytmalari gipergrafalar tomonidan olingan Rödl va uning hamkorlari^[10]^[11]^[12] va Gowers.^[13]^[14]

Yanos Komlos, Gábor Sarkozy va Endre Szemeredi keyinchalik (1997 yilda) portlovchi lemma^[15]^[16] Szemerédi muntazamlik lemmasidagi muntazam juftliklar o'zlarini to'liq sharoitlarda to'liq bipartitli grafikalar kabi tutishlari. Lemma katta siyrak grafiklarni zich grafiklarga singdirish tabiatini chuqurroq o'rganishga imkon berdi.

Birinchi konstruktiv versiya Alon, Dyuk, Lefmann, Rödl va Yuster.^[17]Keyinchalik, Friz va Kannan boshqa versiyasini berdi va uni gipergrafalarga kengaytirdi.^[18] Keyinchalik Alan Friz va Ravi Kannan tufayli ular matritsalarning singular qiymatlaridan foydalanadigan boshqa konstruktsiyani ishlab chiqarishdi.^[19] Rasmiy ravishda batafsilroq tavsiflangan samaraliroq bo'lmagan deterministik algoritmlarni topish mumkin Terens Tao blog^[20] va turli xil hujjatlarda bevosita qayd etilgan.^[21]^[22]^[23]

Ning tengsizligi Terens Tao Szemerédi qonuniylik lemmasini grafik nazariyasi o'rniga ehtimollar nazariyasi va axborot nazariyasi nuqtai nazaridan qayta ko'rib chiqib kengaytiradi.^[24] Terens Tao, shuningdek, grafiklarning qo'shni matritsalaridan foydalangan holda, spektral nazariyaga asoslangan lemmaning isbotini keltirdi.^[25]

Barcha juftlik bo'linmalari muntazam bo'lgan muntazamlik lemmasining bir variantini isbotlash mumkin emas. Kabi ba'zi bir grafikalar, masalan yarim grafikalar, ko'plab juft qismlarni (lekin barcha juftlarning kichik qismini) tartibsiz bo'lishini talab qiladi.^[26]

Bu an ta'rifidagi keng tarqalgan variant ${ displaystyle varepsilon}$ - vertikal to'plamlarning barchasi bir xil o'lchamda bo'lishini talab qiladigan muntazam bo'linma, qolgan cho'qqilarni "xato" to'plamida yig'ish ${ displaystyle V_ {0}}$ uning kattaligi ko'pi bilan an ${ displaystyle varepsilon}$ - ning tepa to'plami hajmining fraktsiyasi ${ displaystyle G}$ .

Muntazamlik lemmasining kuchliroq o'zgarishini Alon, Fischer, Krivelevich va Szegedi graflarni olib tashlash bo'yicha lemmani isbotlagan holda isbotladilar. Bu ketma-ketlik bilan ishlaydi ${ displaystyle varepsilon}$ faqat bitta o'rniga va juda muntazam ravishda takomillashtirilgan qism mavjudligini ko'rsatadi, bu erda aniqlanish juda katta energiya o'sishiga ega emas.

Szemeredi muntazamligi lemmasi barcha grafikalar maydoni shunday deb talqin qilinishi mumkin to'liq chegaralangan (va shuning uchun oldindan aniq ) mos metrikada ( masofani kesib tashlash ). Ushbu ko'rsatkichning chegaralari quyidagicha ifodalanishi mumkin grafonlar; muntazamlik lemmasining yana bir versiyasida grafonlar maydoni shunchaki ekanligini bildiradi ixcham.^[27]

Adabiyotlar

^ Konlon, Devid; Tulki, Yoqub (2012), "Grafik muntazamligi va lemmalarini olib tashlash chegaralari", Geometrik va funktsional tahlil, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, JANOB 2989432, S2CID 1623986
^ Govers, V. T. (1997), "Szemeredi bir xilligi lemmasi uchun minora turining pastki chegaralari", Geometrik va funktsional tahlil, 7 (2): 322–337, doi:10.1007 / PL00001621, JANOB 1445389, S2CID 115242956.
^ Rot, K. F. (1953), "Muayyan tamsayılar to'plami to'g'risida", London Matematik Jamiyati jurnali, 28 (1): 104–109, doi:10.1112 / jlms / s1-28.1.104, JANOB 0051853
^ Tao, Terens (2006), "Gipergrafiyani olib tashlash lemmasi varianti", Kombinatorial nazariya jurnali, A seriyasi, 113 (7): 1257–1280, arXiv:matematik / 0503572, doi:10.1016 / j.jcta.2005.11.006, JANOB 2259060, S2CID 14337591
^ Alon, Noga; Fischer, Eldar; Krivelevich, Maykl; Szegdi, Mario (2000), "Katta grafikalarni samarali sinovdan o'tkazish", Kombinatorika, 20 (4): 451–476, doi:10.1007 / s004930070001, JANOB 1804820, S2CID 44645628
^ Pelosin, Franchesko (2018). "Muntazamlik usulidan foydalangan holda grafikani siqish". arXiv:1810.07275. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ Fiorucci, Marko; Pelosin, Franchesko; Pelillo, Marchello (2020). "Doimiylik lemmasidan foydalangan holda tuzilmani katta grafikalarda shovqindan ajratish". 98. arXiv:1905.06917. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ Szemeredi, Endre (1975), "Arifmetik progresiyada k elementi bo'lmagan tamsayılar to'plami to'g'risida", Polska Akademiya Nauk. Instytut Matematyczny. Acta Arithmetica, 27: 199–245, JANOB 0369312.
^ Szemeredi, Endre (1978), "Grafiklarning muntazam bo'linmalari", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, Parij: CNRS, 399-401 betlar, JANOB 0540024.
^ Frankl, Piter; Rydl, Voytix (2002), "O'rnatilgan tizimlardagi o'ta muammolar", Tasodifiy tuzilmalar va algoritmlar, 20 (2): 131–164, doi:10.1002 / rsa.10017.abs, JANOB 1884430.
^ Rydl, Voytix; Skokan, Jozef (2004), "Muntazamlik uchun lemma $k$ - bir xil gipergrafalar ", Tasodifiy tuzilmalar va algoritmlar, 25 (1): 1–42, doi:10.1002 / rsa.20017, JANOB 2069663.
^ Nagl, Brendan; Rydl, Voytix; Shaxt, Matias (2006), "Muntazam ravishda hisoblash lemmasi $k$ - bir xil gipergrafalar ", Tasodifiy tuzilmalar va algoritmlar, 28 (2): 113–179, CiteSeerX 10.1.1.378.8503, doi:10.1002 / rsa.20117 yil, JANOB 2198495.
^ Govers, V. T. (2006), "3-formali gipergrafalar uchun kvasadandomlik, hisoblash va muntazamlik", Kombinatorika, ehtimollik va hisoblash, 15 (1–2): 143–184, doi:10.1017 / S0963548305007236, JANOB 2195580, S2CID 14632612.
^ Govers, V. T. (2007), "Gipergraf muntazamligi va ko'p o'lchovli Szemeredi teoremasi", Matematika yilnomalari, Ikkinchi seriya, 166 (3): 897–946, arXiv:0710.3032, Bibcode:2007arXiv0710.3032G, doi:10.4007 / annals.2007.166.897, JANOB 2373376, S2CID 56118006.
^ Komlos, Yanos; Sarkozy, Gábor N.; Szemeredi, Endre (1997), "Portlashli lemma", Kombinatorika, 17 (1): 109–123, doi:10.1007 / BF01196135, JANOB 1466579, S2CID 6720143
^ Komlos, Yanos; Sarkozy, Gábor N.; Szemeredi, Endre (1998), "Portlash lemmasining algoritmik versiyasi", Tasodifiy tuzilmalar va algoritmlar, 12 (3): 297–312, arXiv:matematik / 9612213, doi:10.1002 / (SICI) 1098-2418 (199805) 12: 3 <297 :: AID-RSA5> 3.3.CO; 2-V, JANOB 1635264
^ N. Alon va R. A. Dyuk va X. Lefmann va V. Rodl va R. Yuster (1994). "Muntazamlik lemmasining algoritmik tomonlari". J. Algoritmlar. 16: 80–109. CiteSeerX 10.1.1.102.681. doi:10.1006 / jagm.1994.1005.
^ A. Friz va R. Kannan (1996). "Zich masalalar uchun muntazamlik lemmasi va taxminiy sxemalari". FOCS '96: Kompyuter fanlari asoslari bo'yicha 37-yillik simpozium materiallari. doi:10.1109 / SFCS.1996.548459.
^ A. Friz va R. Kannan (1999). "Szemeredi muntazamlik bo'limini qurish uchun oddiy algoritm" (PDF). Elektron. J. Taroq. 6.
^ Tao, Terens (2009), Szemeredining muntazamlik lemmasi tasodifiy bo'limlar orqali
^ Alon, Noga; Shapira, Asaf (2008), "Har bir monoton grafik xususiyatini sinab ko'rish mumkin", SIAM J. Comput., 38 (2): 505–522, doi:10.1137/050633445, ISSN 0097-5397, JANOB 2411033
^ Ishigami, Yoshiyasu (2006), Gipergrafalarni oddiy tartibga solish, arXiv:matematik / 0612838, Bibcode:2006 yil ..... 12838I
^ Ostin, Tim (2008), "O'zgaruvchan tasodifiy o'zgaruvchilar va katta grafikalar va gipergrafalar statistikasi to'g'risida", Ehtimollarni o'rganish, 5: 80–145, arXiv:0801.1698, Bibcode:2008arXiv0801.1698A, doi:10.1214 / 08-PS124, S2CID 15421306
^ Tao, Terens (2006), "Szemerédi muntazamligi lemmasi qayta ko'rib chiqildi", Diskret matematikaga qo'shgan hissasi, 1 (1): 8–28, arXiv:matematik / 0504472, Bibcode:2005 yil ...... 4472T, JANOB 2212136.
^ Tao, Terens (2012), Szemeredi muntazamligi lemmasining spektral isboti
^ Konlon, Devid; Tulki, Yoqub (2012), "Grafik muntazamligi va lemmalarini olib tashlash chegaralari", Geometrik va funktsional tahlil, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, JANOB 2989432, S2CID 1623986
^ Lovash, Laslo; Szegedy, Balázs (2007), "Szemerédi analitik uchun lemmasi", Geometrik va funktsional tahlil, 17: 252–270, doi:10.1007 / s00039-007-0599-6, ISSN 1016-443X, JANOB 2306658, S2CID 15201345

Qo'shimcha o'qish

Komlos, J.; Simonovits, M. (1996), "Szemeredi qonuniyligi lemmasi va uning grafik nazariyasida qo'llanilishi", Kombinatorika, Pol Erdos sakson yoshda, Vol. 2 (Keszthely, 1993), Bolyai Soc. Matematika. Stud., 2, Xanos Bolyay matematikasi. Soc., Budapesht, 295–352 betlar, JANOB 1395865.
Komlos, J.; Shokufandeh, Ali; Simonovits, Miklos; Szemeredi, Endre (2002), "qonuniylik lemmasi va uning grafik nazariyasida qo'llanilishi", Kompyuter fanining nazariy jihatlari (Tehron, 2000), Kompyuter fanidan ma'ruza matnlari, 2292, Springer, Berlin, 84-112 betlar, doi:10.1007/3-540-45878-6_3, ISBN 978-3-540-43328-6, JANOB 1966181.

[1] Konlon, Devid; Tulki, Yoqub (2012), "Grafik muntazamligi va lemmalarini olib tashlash chegaralari", Geometrik va funktsional tahlil, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, JANOB 2989432, S2CID 1623986

[2] Govers, V. T. (1997), "Szemeredi bir xilligi lemmasi uchun minora turining pastki chegaralari", Geometrik va funktsional tahlil, 7 (2): 322–337, doi:10.1007 / PL00001621, JANOB 1445389, S2CID 115242956.

[roth-3] Rot, K. F. (1953), "Muayyan tamsayılar to'plami to'g'risida", London Matematik Jamiyati jurnali, 28 (1): 104–109, doi:10.1112 / jlms / s1-28.1.104, JANOB 0051853

[4] Tao, Terens (2006), "Gipergrafiyani olib tashlash lemmasi varianti", Kombinatorial nazariya jurnali, A seriyasi, 113 (7): 1257–1280, arXiv:matematik / 0503572, doi:10.1016 / j.jcta.2005.11.006, JANOB 2259060, S2CID 14337591

[afk-5] Alon, Noga; Fischer, Eldar; Krivelevich, Maykl; Szegdi, Mario (2000), "Katta grafikalarni samarali sinovdan o'tkazish", Kombinatorika, 20 (4): 451–476, doi:10.1007 / s004930070001, JANOB 1804820, S2CID 44645628

[fp-6] Pelosin, Franchesko (2018). "Muntazamlik usulidan foydalangan holda grafikani siqish". arXiv:1810.07275. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[fpp-7] Fiorucci, Marko; Pelosin, Franchesko; Pelillo, Marchello (2020). "Doimiylik lemmasidan foydalangan holda tuzilmani katta grafikalarda shovqindan ajratish". 98. arXiv:1905.06917. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[8] Szemeredi, Endre (1975), "Arifmetik progresiyada k elementi bo'lmagan tamsayılar to'plami to'g'risida", Polska Akademiya Nauk. Instytut Matematyczny. Acta Arithmetica, 27: 199–245, JANOB 0369312.

[9] Szemeredi, Endre (1978), "Grafiklarning muntazam bo'linmalari", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, Parij: CNRS, 399-401 betlar, JANOB 0540024.

[10] Frankl, Piter; Rydl, Voytix (2002), "O'rnatilgan tizimlardagi o'ta muammolar", Tasodifiy tuzilmalar va algoritmlar, 20 (2): 131–164, doi:10.1002 / rsa.10017.abs, JANOB 1884430.

[11] Rydl, Voytix; Skokan, Jozef (2004), "Muntazamlik uchun lemma $k$ - bir xil gipergrafalar ", Tasodifiy tuzilmalar va algoritmlar, 25 (1): 1–42, doi:10.1002 / rsa.20017, JANOB 2069663.

[12] Nagl, Brendan; Rydl, Voytix; Shaxt, Matias (2006), "Muntazam ravishda hisoblash lemmasi $k$ - bir xil gipergrafalar ", Tasodifiy tuzilmalar va algoritmlar, 28 (2): 113–179, CiteSeerX 10.1.1.378.8503, doi:10.1002 / rsa.20117 yil, JANOB 2198495.

[13] Govers, V. T. (2006), "3-formali gipergrafalar uchun kvasadandomlik, hisoblash va muntazamlik", Kombinatorika, ehtimollik va hisoblash, 15 (1–2): 143–184, doi:10.1017 / S0963548305007236, JANOB 2195580, S2CID 14632612.

[14] Govers, V. T. (2007), "Gipergraf muntazamligi va ko'p o'lchovli Szemeredi teoremasi", Matematika yilnomalari, Ikkinchi seriya, 166 (3): 897–946, arXiv:0710.3032, Bibcode:2007arXiv0710.3032G, doi:10.4007 / annals.2007.166.897, JANOB 2373376, S2CID 56118006.

[15] Komlos, Yanos; Sarkozy, Gábor N.; Szemeredi, Endre (1997), "Portlashli lemma", Kombinatorika, 17 (1): 109–123, doi:10.1007 / BF01196135, JANOB 1466579, S2CID 6720143

[16] Komlos, Yanos; Sarkozy, Gábor N.; Szemeredi, Endre (1998), "Portlash lemmasining algoritmik versiyasi", Tasodifiy tuzilmalar va algoritmlar, 12 (3): 297–312, arXiv:matematik / 9612213, doi:10.1002 / (SICI) 1098-2418 (199805) 12: 3 <297 :: AID-RSA5> 3.3.CO; 2-V, JANOB 1635264

[17] N. Alon va R. A. Dyuk va X. Lefmann va V. Rodl va R. Yuster (1994). "Muntazamlik lemmasining algoritmik tomonlari". J. Algoritmlar. 16: 80–109. CiteSeerX 10.1.1.102.681. doi:10.1006 / jagm.1994.1005.

[:0-18] A. Friz va R. Kannan (1996). "Zich masalalar uchun muntazamlik lemmasi va taxminiy sxemalari". FOCS '96: Kompyuter fanlari asoslari bo'yicha 37-yillik simpozium materiallari. doi:10.1109 / SFCS.1996.548459.

[19] A. Friz va R. Kannan (1999). "Szemeredi muntazamlik bo'limini qurish uchun oddiy algoritm" (PDF). Elektron. J. Taroq. 6.

[20] Tao, Terens (2009), Szemeredining muntazamlik lemmasi tasodifiy bo'limlar orqali

[21] Alon, Noga; Shapira, Asaf (2008), "Har bir monoton grafik xususiyatini sinab ko'rish mumkin", SIAM J. Comput., 38 (2): 505–522, doi:10.1137/050633445, ISSN 0097-5397, JANOB 2411033

[22] Ishigami, Yoshiyasu (2006), Gipergrafalarni oddiy tartibga solish, arXiv:matematik / 0612838, Bibcode:2006 yil ..... 12838I

[23] Ostin, Tim (2008), "O'zgaruvchan tasodifiy o'zgaruvchilar va katta grafikalar va gipergrafalar statistikasi to'g'risida", Ehtimollarni o'rganish, 5: 80–145, arXiv:0801.1698, Bibcode:2008arXiv0801.1698A, doi:10.1214 / 08-PS124, S2CID 15421306

[24] Tao, Terens (2006), "Szemerédi muntazamligi lemmasi qayta ko'rib chiqildi", Diskret matematikaga qo'shgan hissasi, 1 (1): 8–28, arXiv:matematik / 0504472, Bibcode:2005 yil ...... 4472T, JANOB 2212136.

[25] Tao, Terens (2012), Szemeredi muntazamligi lemmasining spektral isboti

[26] Konlon, Devid; Tulki, Yoqub (2012), "Grafik muntazamligi va lemmalarini olib tashlash chegaralari", Geometrik va funktsional tahlil, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, JANOB 2989432, S2CID 1623986

[27] Lovash, Laslo; Szegedy, Balázs (2007), "Szemerédi analitik uchun lemmasi", Geometrik va funktsional tahlil, 17: 252–270, doi:10.1007 / s00039-007-0599-6, ISSN 1016-443X, JANOB 2306658, S2CID 15201345

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]