Conjectura Erdős-Bura

Conjectura Erdős-Bur  este o problemă matematică referitoare la numărul Ramsey pe grafice rare . Ipoteza este numită după Pal Erdős și Stefan Boer . Conjectura afirmă că numărul Ramsey din orice familie de grafice rare ar trebui să crească aproape liniar cu numărul de vârfuri din grafic.

Această presupunere a fost pe deplin dovedită de Choongbum Lee în 2017 (și, prin urmare, este acum o teoremă) [1]

Definiții

Dacă G  nu este un graf direcționat , atunci degenerarea lui G  este numărul minim p astfel încât orice subgraf al lui G conține un vârf de gradul p sau mai mic. Un grafic A cu degenerare p se numește p -degenerat. p -degenerarea unui graf poate fi definită și ca abilitatea de a reduce un graf la unul gol prin eliminarea secvenţială a vârfurilor de gradul p sau mai mic.

Din teorema Ramsey rezultă că pentru orice graf G există un număr întreg , numit număr Ramsey pentru G , astfel încât orice graf complet cu cel puțin vârfuri , ale căror margini sunt colorate în roșu și albastru, conține o copie monocromă a graficului G . De exemplu, numărul Ramsey pentru un triunghi este 6: indiferent de modul în care marginile unui grafic complet de șase vârfuri sunt colorate în roșu și albastru, va exista întotdeauna un triunghi roșu sau albastru.

Ipoteza

În 1973, Paul Erdős și Stefan Boer au formulat următoarea ipoteză:

Pentru orice număr întreg p există o constantă c p astfel încât orice graf p -degenerat G pe n vârfuri are un număr Ramsey cel mult c p n .

Astfel, dacă un graf G cu n vârfuri este p -degenerat, atunci o copie monocromatică a lui G trebuie să existe în orice graf bicolor cu p n vârfuri .

Rezultate intermediare

Înainte ca conjectura să fie pe deplin dovedită, a fost demonstrată în unele cazuri speciale, de exemplu, demonstrarea conjecturei pentru grafuri cu un grad mărginit de vârfuri este dată în articolul lui Chvatal, Rödl, Szemeredy și Trotter [2] . Dovada lor conduce la o valoare foarte mare a lui c p . Constanta a fost îmbunătățită de Nancy Eaton [3] și de Ronald Graham [4] .

Se știe că conjectura este adevărată pentru grafurile p -mărginite, care includ grafuri cu un grad maxim limitat de vârfuri, grafuri plane și grafuri care pKdivizareanu conțin [5] .

Se știe că conjectura este adevărată pentru graficele împărțite, adică pentru graficele în care două vârfuri învecinate nu au un grad mai mare decât doi [6] .

Pentru un grafic arbitrar, se știe că numărul Ramsey este mărginit de o funcție care crește ușor superliniar. Și anume, Fox și Sudakov [7] au arătat că există o constantă c p astfel încât pentru orice graf p -degenerat G cu n vârfuri

Note

  1. ↑ Choongbum Lee. Numerele Ramsey ale graficelor degenerate  // Analele matematicii. - 2017. - T. 185 , nr. Problema 3 . - S. 791-829 . - arXiv : 1505.04773 .
  2. ↑ Václav Chvátal, Vojtěch Rödl, Endre Semeredy , William Trotter, Jr. Numărul Ramsey pentru un grafic cu gradul mărginit de vârfuri. (Engleză)  = Numărul Ramsey al unui grafic cu gradul maxim mărginit // Journal of Combinatorial Theory, Series B. - 1983. - Vol. 34 , iss. 3 . — P. 239–243 . - doi : 10.1016/0095-8956(83)90037-0 .
  3. ↑ Nancy Eaton. Numerele Ramsey pentru grafice rare = Numerele Ramsey pentru grafice rare // Matematică discretă. - 1998. - T. 185 , nr. 1–3 . — S. 63–75 . - doi : 10.1016/S0012-365X(97)00184-2 .
  4. ↑ Ronald Graham, Vojtěch Rödl, Andrzej Rucínski. Grafice cu numere Ramsey liniare  = Pe grafice cu numere Ramsey liniare // Journal of Graph Theory. - 2000. - T. 35 , nr. 3 . — S. 176–192 . - doi : 10.1002/1097-0118(200011)35:3<176::AID-JGT3>3.0.CO;2-C .
  5. ↑ Vojtěch Rödl, Robin Thomas. Matematica lui Paul Erdős, II = The Mathematics of Paul Erdős, II / Ed. Ronald Graham, Jaroslav Nešetřil. - Springer-Verlag, 1991. - S. 236-239.
  6. ↑ Noga Alon. Graficele subdivizate au numere Ramsey liniare  // Journal of Graph Theory. - 1994. - T. 18 , nr. 4 . — S. 343–347 . - doi : 10.1002/jgt.3190180406 . , Yusheng Li, Cecil C. Rousseau, Lubomir Soltes (Ľubomír Soltés). Familii liniare Ramsey și grafice subdivizate generalizate // Matematică discretă. - 1997. - T. 170 , nr. 1–3 . — S. 269–275 . - doi : 10.1016/S0012-365X(96)00311-1 .
  7. ↑ Jacob Fox, Benny Sudakov. Două  observații despre conjectura lui Burr–Erdő (engleză)  = Two remarks on the Burr–Erdős conjecture // European Journal of Combinatorics : journal. - 2009. - Vol. 30 , iss. 7 . — P. 1630–1645 . - doi : 10.1016/j.ejc.2009.03.004 .

Link -uri