Burr-Erdning taxminlari - Burr–Erdős conjecture

Yilda matematika, Burr-Erdning taxminlari bilan bog'liq muammo edi Ramsey raqami ning siyrak grafikalar. Gumon nomi bilan nomlangan Stefan Burr va Pol Erdos, va bu ko'plardan biri Erdo's nomidagi taxminlar; har qanday siyrak grafika oilasidagi Ramsey grafika soni kerak bo'lishi kerak chiziqli o'sadi sonida tepaliklar grafikning

Gumonni Choongbum Li isbotlagan (shuning uchun u endi teorema).^[1]

Ta'riflar

Agar G bu yo'naltirilmagan grafik, keyin degeneratsiya ning G minimal raqam p shunday qilib har bir subgrafasi G daraja tepaligini o'z ichiga oladi p yoki kichikroq. Degeneratsiyasi bo'lgan grafik p deyiladi p- buzilish. Teng ravishda, a p-degenerat grafigi - ga kamaytiriladigan grafik bo'sh grafik daraja tepaligini bir necha marta olib tashlash orqali p yoki kichikroq.

Bu quyidagidan kelib chiqadi Ramsey teoremasi bu har qanday grafik uchun G eng kam butun son mavjud ${ displaystyle r (G)}$, Ramsey raqami ning G, shunday qilib har qanday to'liq grafik hech bo'lmaganda ${ displaystyle r (G)}$ tepaliklar kimning qirralar qizil yoki ko'k ranglarda monoxromatik nusxasi mavjud G. Masalan, uchburchakning Ramsey soni 6 ga teng: oltita tepalikdagi to'liq grafika qirralari qanday qilib qizil yoki ko'k rangga ega bo'lishidan qat'iy nazar, har doim qizil uchburchak yoki ko'k uchburchak mavjud.

Taxmin

1973 yilda, Stefan Burr va Pol Erdos quyidagi gumon qildi:

Har bir butun son uchun p doimiy mavjud v_p shunday qilib har qanday p- buzilgan grafik G kuni n tepaliklar eng ko'p Ramsey raqamiga ega v_p n.

Ya'ni, agar n-vertex grafigi G bu p- degeneratsiya, keyin monoxromatik nusxasi G har ikki qirrali to'liq grafikada mavjud bo'lishi kerak v_p n tepaliklar.

Ma'lum natijalar

To'liq gumon isbotlanmasdan oldin, u birinchi navbatda ba'zi bir maxsus holatlarda hal qilindi. Bu chegaralangan gradusli grafikalar uchun isbotlangan Chvatal va boshq. (1983); ularning isboti juda yuqori qiymatga olib keldi v_pva ushbu doimiylikni takomillashtirish tomonidan amalga oshirildi Eaton (1998) va Grem, Rodl va Ruchinski (2000). Umuman olganda, gumon haqiqat ekanligi ma'lum p- chegaralangan maksimal darajadagi grafikalarni o'z ichiga olgan tartibga solinadigan grafikalar, planar grafikalar va a tarkibiga kirmagan grafikalar bo'linish ning K_p.^[2] Shuningdek, u ikkala qo'shni tepalik ikkitadan katta darajaga ega bo'lmagan grafiklarga bo'lingan grafikalar bilan tanilgan.^[3]

Ixtiyoriy grafikalar uchun Ramsey sonini faqat bir oz super chiziqli o'sib boruvchi funktsiya cheklashi ma'lum. Xususan, Fox va Sudakov (2009) doimiy mavjudligini ko'rsatdi v_p shunday qilib, har qanday kishi uchun p- buzilish n-vertex grafigi G,

${ displaystyle r (G) leq 2 ^ {c_ {p} { sqrt { log n}}} n.}$

Izohlar

Adabiyotlar