Taqiqlangan subgraf muammosi - Forbidden subgraph problem

Yilda ekstremal grafikalar nazariyasi, taqiqlangan subgraf muammosi quyidagi muammo: grafik berilgan ${displaystyle G}$, qirralarning maksimal sonini toping ${displaystyle operator nomi {ex} (n, G)}$ ichida ${displaystyle n}$a bo'lmagan vertex grafigi subgraf izomorfik ga ${displaystyle G}$. Shu nuqtai nazardan, ${displaystyle G}$ deyiladi a taqiqlangan subgraf.^[1]

Ekvivalent muammo - bu qancha qirralarning ${displaystyle n}$-vertex grafigi uning subgraf izomorfik xususiyatiga ega bo'lishiga kafolat beradi ${displaystyle G}$?^[2]

Ta'riflar

The ekstremal raqam ${displaystyle operator nomi {ex} (n, G)}$ an-dagi qirralarning maksimal soni ${displaystyle n}$uchun izomorf bo'lmagan subgrafani o'z ichiga olgan vertex grafikasi ${displaystyle G}$. ${displaystyle K_ {r}}$ bo'ladi to'liq grafik kuni ${displaystyle r}$ tepaliklar. ${displaystyle T (n, r)}$ bo'ladi Turan grafigi: to'liq ${displaystyle r}$- qismli grafik ${displaystyle n}$ tepaliklar, tepaliklar qismlar orasida iloji boricha teng taqsimlangan. The xromatik raqam ${displaystyle chi (G)}$ ning ${displaystyle G}$ - tepaliklarni bo'yash uchun zarur bo'lgan minimal rang soni ${displaystyle G}$ Shunday qilib, hech qanday qo'shni tepaliklarning rangi bir xil emas.

Natijalar

Ikki tomonlama grafikalar

'Turan teoremasi '. Ijobiy tamsayılar uchun ${displaystyle n, r}$ qoniqarli ${displaystyle ngeq rgeq 3}$,^[3] ${extstyle operator nomi {ex} (n, K_ {r}) = chap (1- {frac {1} {r-1}} ight) {frac {n ^ {2}} {2}}.}$

Bu taqiqlangan subgraf muammosini hal qiladi ${displaystyle G = K_ {r}}$. Turan teoremasi uchun tenglik holatlari quyidagilardan kelib chiqadi Turan grafigi ${displaystyle T (n, r-1)}$.

Ushbu natija o'zboshimchalik bilan grafikalar uchun umumlashtirilishi mumkin ${displaystyle G}$ ni ko'rib chiqib xromatik raqam ${displaystyle chi (G)}$ ning ${displaystyle G}$. Yozib oling ${displaystyle T (n, r)}$ bilan ranglanishi mumkin ${displaystyle r}$ ranglari va shuning uchun xromatik sonidan kattaroq pastki yozuvlari yo'q ${displaystyle r}$. Jumladan, ${displaystyle T (n, chi (G) -1)}$ uchun izomorfik subgrafalar mavjud emas ${displaystyle G}$. Bu taqiqlangan subgraf muammosi bo'yicha umumiy tenglik holatlari tenglik holatlari bilan bog'liq bo'lishi mumkinligidan dalolat beradi ${displaystyle G = K_ {r}}$. Ushbu sezgi to'g'ri bo'lib chiqadi ${displaystyle o (n ^ {2})}$ xato.

'Erdos-Tosh teoremasi '. Barcha musbat sonlar uchun ${displaystyle n}$ va barcha grafikalar ${displaystyle G}$,^[4]${extstyle operator nomi {ex} (n, G) = chap (1- {frac {1} {chi (G) -1}} + o (1) ight) {frac {n ^ {2}} {2}} .}$

Qachon ${displaystyle G}$ ikki tomonlama emas, bu bizga birinchi darajali yaqinlashishni beradi ${displaystyle operator nomi {ex} (n, G)}$.

Ikki tomonlama grafikalar

Ikki tomonlama grafikalar uchun ${displaystyle G}$, Erdős-Tosh teoremasi bizga buni faqat aytib beradi ${displaystyle operator nomi {ex} (n, G) = o (n ^ {2})}$. Ikki tomonlama grafikalar uchun taqiqlangan subgraf muammosi Zarankievich muammosi, va umuman hal qilinmagan.

Zarankevich muammosi bo'yicha taraqqiyot quyidagi teoremani o'z ichiga oladi:

Kvari-Sós-Turan teoremasi. Har bir musbat butun son uchun ${displaystyle s, t}$ bilan ${displaystyle tgeq sgeq 1}$, ba'zi bir doimiy mavjud ${displaystyle C}$ (mustaqil ravishda ${displaystyle n}$) shu kabi ${extstyle operator nomi {ex} (n, K_ {s, t}) leq Cn ^ {2- {frac {1} {s}}}}$ har bir musbat butun son uchun ${displaystyle n}$.^[5]

Ikki tomonlama grafikalar uchun yana bir natija - bu juft tsikllar, ${displaystyle G = C_ {2k}, kgeq 2}$. Hatto tsikllar bilan ham ildiz tepasi va ushbu tepalikdan tarvaqaylab ketgan yo'llarni ko'rib chiqish mumkin. Agar bir xil uzunlikdagi ikkita yo'l bo'lsa ${displaystyle k}$ bir xil so'nggi nuqtaga ega va bir-birining ustiga chiqmaydi, keyin ular uzunlik tsikli hosil qiladi ${displaystyle 2k}$. Bu quyidagi teoremani beradi.

Teorema (Bondy va Simonovits, 1974). Doimiy mavjud ${displaystyle C}$ shu kabi ${extstyle operatorname {ex} (n, C_ {2k}) leq Cn ^ {1+ {frac {1} {k}}}}$ har bir musbat butun son uchun ${displaystyle n}$ va musbat tamsayı ${displaystyle kgeq 2}$.^[6]

Kuchli lemma ekstremal grafikalar nazariyasi bu qaram tasodifiy tanlov. Ushbu lemma bir qismda chegaralangan darajadagi ikki tomonlama grafikalar bilan ishlashga imkon beradi:

Teorema (Alon, Krivelevich va Sudakov, 2003). Ruxsat bering ${displaystyle G}$ vertex qismlari bo'lgan ikki tomonlama grafik bo'ling ${displaystyle A}$ va ${displaystyle B}$ shunday qilib har bir tepalik ${displaystyle A}$ eng yuqori darajaga ega ${displaystyle r}$. Keyin doimiy doimiy mavjud ${displaystyle C}$ (faqat bog'liq ${displaystyle G}$) shu kabi ${extstyle operator nomi {ex} (n, G) leq Cn ^ {2- {frac {1} {r}}}}$har bir musbat butun son uchun ${displaystyle n}$.^[7]

Umuman olganda, bizda quyidagi taxmin mavjud:

Ratsional ko'rsatkichlar gumoni (Erdős va Simonovits). Har qanday cheklangan oila uchun ${displaystyle {mathcal {L}}}$ agar ikki tomonlama bo'lsa, grafikalar ${displaystyle Lin {mathcal {L}}}$, keyin mantiqiy narsa mavjud ${displaystyle alfa [0,1)}$ shu kabi ${displaystyle operatorname {ex} (n, {mathcal {L}}) = Theta (n ^ {1 + alfa})}$.^[8]

Tomonidan so'rovnoma Furedi va Simonovits taqiqlangan subgraf muammosi bo'yicha rivojlanishni batafsilroq tavsiflaydi.^[8]

Pastki chegaralar

Har qanday grafik uchun ${displaystyle G}$, biz quyidagi pastki chegaraga egamiz:

Taklif. ${displaystyle operator nomi {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ ba'zi bir doimiy uchun ${displaystyle c}$.^[9]

Isbot. Ning texnikasidan foydalanamiz ehtimollik usuli, "o'zgartirishlar usuli". O'ylab ko'ring Erdős-Rényi tasodifiy grafigi ${displaystyle G (n, p)}$, ya'ni bilan grafik ${displaystyle n}$ cho'qqilar va istalgan ikkita tepalik o'rtasida, ehtimollik bilan chekka chizilgan ${displaystyle p}$, mustaqil ravishda. Kutilayotgan nusxalarini topishimiz mumkin ${displaystyle G}$ yilda ${displaystyle G (n, p)}$ tomonidan kutishning lineerligi. Keyin har bir nusxadagi bitta chekkani olib tashlang ${displaystyle G}$, biz a bilan qoldik ${displaystyle G}$- bepul grafik. Qolgan qirralarning kutilgan sonini topish mumkin ${displaystyle operator nomi {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ ba'zi bir doimiy uchun ${displaystyle c}$. Shuning uchun, hech bo'lmaganda bittasi ${displaystyle n}$-vertex grafigi kamida kutilgan songa teng qirralar bilan mavjud.

Muayyan holatlar uchun algebraik konstruktsiyalarni topish orqali yaxshilanishlar amalga oshirildi.

Teorema (Erdős, Rényi va Sős, 1966). ${displaystyle operatorname {ex} (n, K_ {2,2}) geq chap ({frac {1} {2}} - o (1) ight) n ^ {3/2}.}$^[10]

Isbot.^[11] Birinchidan, shunday deb taxmin qiling ${displaystyle n = p ^ {2} -1}$ ba'zi bir yaxshi narsalar uchun ${displaystyle p}$. Ni ko'rib chiqing qutblanish grafigi ${displaystyle G}$ ning tepalik elementlari bilan ${displaystyle mathbb {F} _ {p} ^ {2} - {0,0}}$ va tepaliklar orasidagi qirralar ${displaystyle (x, y)}$ va ${displaystyle (a, b)}$ agar va faqat agar ${displaystyle ax + by = 1}$ yilda ${displaystyle mathbb {F} _ {p}}$. Ushbu grafik ${displaystyle K_ {2,2}}$- bepul, chunki ikkita chiziqli tenglama tizimi ${displaystyle mathbb {F} _ {p}}$ bir nechta echimga ega bo'lishi mumkin emas. Tepalik ${displaystyle (a, b)}$ (taxmin qiling ${displaystyle beq 0}$) ga ulangan ${displaystyle chap (x, {frac {1-ax} {b}} ight)}$ har qanday kishi uchun ${displaystyle xin mathbb {F} _ {p}}$, jami kamida ${displaystyle p-1}$ qirralar (agar 1 bo'lsa, olib tashlanadi ${displaystyle (a, b) = chap (x, {frac {1-ax} {b}} ight)}$). Shunday qilib, hech bo'lmaganda bor ${displaystyle {frac {1} {2}} (p ^ {2} -1) (p-1) = chap ({frac {1} {2}} - o (1) ight) p ^ {3} = chap ({frac {1} {2}} - o (1) ight) n ^ {3/2}}$ xohlagancha qirralar. Umuman olganda ${displaystyle n}$, biz olishimiz mumkin ${displaystyle p = (1-o (1)) {sqrt {n}}}$ bilan ${displaystyle pleq {sqrt {n + 1}}}$ (bu mumkin, chunki asosiy narsa mavjud ${displaystyle p}$ oralig'ida${displaystyle [k-k ^ {0.525}, k]}$ etarli darajada katta ${displaystyle k}$^[12]) va shu yordamida qutblanish grafigini tuzing ${displaystyle p}$, keyin qo'shib qo'ying ${displaystyle n-p ^ {2} +1}$ asimptotik qiymatga ta'sir qilmaydigan izolyatsiya qilingan tepalar.

Teorema (Braun, 1966). ${displaystyle operatorname {ex} (n, K_ {3,3}) geq chap ({frac {1} {2}} - o (1) ight) n ^ {5/3}.}$^[13]

Tasdiqlangan kontur.^[14] Oldingi teoremadagi kabi, biz ham olishimiz mumkin ${displaystyle n = p ^ {3}}$ eng yaxshi uchun ${displaystyle p}$ va bizning grafamizning tepalari elementlar bo'lsin ${displaystyle mathbb {F} _ {p} ^ {3}}$. Bu safar tepaliklar ${displaystyle (a, b, c)}$ va ${displaystyle (x, y, z)}$ va agar shunday bo'lsa ulanadi ${displaystyle (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2} = u}$ yilda ${displaystyle mathbb {F} _ {p}}$, maxsus tanlanganlar uchun ${displaystyle u}$. Keyin bu ${displaystyle K_ {3,3}}$- bepul, chunki ko'pi bilan ikkita nuqta uchta sharning kesishmasida yotadi. Keyin qiymati beri ${displaystyle (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2}}$ bo'ylab deyarli bir xil ${displaystyle mathbb {F} _ {p}}$, har bir nuqta atrofida bo'lishi kerak ${displaystyle p ^ {2}}$ qirralarning, shuning uchun qirralarning umumiy soni ${displaystyle chap ({frac {1} {2}} - o (1) ight) p ^ {2} cdot p ^ {3} = chap ({frac {1} {2}} - o (1) ight) n ^ {5/3}}$.

Biroq, pastki chegarani kuchaytirish ochiq savol bo'lib qolmoqda ${displaystyle operator nomi {ex} (n, K_ {t, t})}$ uchun ${displaystyle tgeq 4}$.

Teorema (Alon va boshq., 1999) Uchun ${displaystyle tgeq (s-1)! + 1}$, ${displaystyle operatorname {ex} (n, K_ {s, t}) = Theta (n ^ {2- {frac {1} {s}}}).}$^[15]

Umumlashtirish

Muammoni taqiqlangan subgrafalar to'plami uchun umumlashtirish mumkin ${displaystyle S}$: an-dagi qirralarning maksimal sonini toping ${displaystyle n}$dan biron bir grafik uchun subgraf izomorfik bo'lmagan vertex grafigi ${displaystyle S}$.^[16]

Shuningdek, bor gipergraf taqiqlangan subgraf muammolarining versiyalari ancha qiyin. Masalan, Turan muammosi, eng ko'p qirralarning sonini so'rash bilan umumlashtirilishi mumkin ${displaystyle n}$-telektra bo'lmagan vertex 3-formali gipergraf. Turan qurilishining analogi, tepaliklarni deyarli teng pastki qismlarga bo'lishdir ${displaystyle V_ {1}, V_ {2}, V_ {3}}$va tepaliklarni ulang ${displaystyle x, y, z}$ agar ularning barchasi boshqacha bo'lsa, 3 qirrali ${displaystyle V_ {i}}$s, yoki ulardan ikkitasi bo'lsa ${displaystyle V_ {i}}$ uchinchisi esa ${displaystyle V_ {i + 1}}$ (qayerda ${displaystyle V_ {4} = V_ {1}}$). Bu tetraedrsiz va chekka zichligi ${displaystyle 5/9}$. Biroq, bayroq algebralari texnikasidan foydalangan holda, eng yaxshi ma'lum bo'lgan yuqori chegara 0,562 ga teng.^[17]

Shuningdek qarang

• Bikliksiz grafik
• Erduss-Xajnal gumoni
• Turan teoremasi
• Turan raqami
• Subgraf izomorfizmi muammosi
• Taqiqlangan grafikani tavsiflash
• Erdos-Stoun teoremasi
• Zarankievich muammosi
• Ekstremal grafikalar nazariyasi

Adabiyotlar