Erdős-Bura sejtés

Az Erdős-Bur sejtés a Ramsey-számmal kapcsolatos  matematikai probléma ritka gráfokon . A hipotézis Erdős Pal és Stefan Boer nevéhez fűződik . A sejtés szerint a Ramsey-számnak bármely ritka gráfcsaládban csaknem lineárisan kell növekednie a gráf csúcsainak számával .

Ezt a sejtést Choongbum Lee 2017-ben teljes mértékben bebizonyította (és így ez mára tétel) [1]

Definíciók

Ha G  nem irányított gráf , akkor G degeneráltsága az  a minimális p szám, hogy G bármely részgráfja p vagy annál kisebb fokú csúcsot tartalmaz . A p degenerált A gráfot p -degeneráltnak nevezzük . A gráf p -degeneráltsága úgy is meghatározható, mint egy gráf üressé való redukálása a p vagy annál kisebb fokú csúcsok szekvenciális eltávolításával.

A Ramsey-tételből az következik, hogy bármely G gráfhoz létezik egy egész szám , amelyet G - re Ramsey-számnak neveznek , és minden olyan teljes gráf legalább csúcsokkal , amelynek élei piros és kék színűek, tartalmazza a G gráf monokróm másolatát . Például egy háromszög Ramsey-száma 6: nem számít, hogy egy hat csúcsból álló teljes gráf élei piros és kék színűek, mindig lesz piros vagy kék háromszög.

Hipotézis

1973-ban Paul Erdős és Stefan Boer a következő hipotézist állította fel:

Bármely p egész számra van egy c p konstans , így bármely p -degenerált G gráf n csúcson legfeljebb c p n Ramsey-számmal rendelkezik .

Így, ha egy n csúcsú G gráf p -degenerált, akkor G monokromatikus másolatának léteznie kell bármely p n csúcsú kétszínű gráfban .

Köztes eredmények

A sejtés teljes bizonyítása előtt néhány speciális esetben bebizonyosodott, például a sejtés bizonyítását korlátos fokú csúcsú gráfokra Chvatal, Rödl, Szemedy és Trotter [2] cikkében adja meg . Bizonyításuk igen nagy c p értékhez vezet . Az állandót Nancy Eaton [3] és Ronald Graham [4] javította .

Ismeretes, hogy a sejtés igaz a p -korlátos gráfokra, amelyek korlátozott maximális csúcsfokú gráfokat, síkgráfokat és olyan gráfokat tartalmaznak , felosztástpKamelyek nem tartalmaznak [5] .

Ismeretes, hogy a sejtés igaz az osztott gráfokra, vagyis olyan gráfokra, amelyekben nincs két szomszédos csúcsnak kettőnél nagyobb foka [6] .

Egy tetszőleges gráf esetében ismert, hogy a Ramsey-számot egy enyhén szuperlineárisan növekvő függvény határolja. Fox és Sudakov [7] ugyanis kimutatta, hogy létezik olyan c p konstans , amely bármely n csúcsú p - degenerált G gráfra

Jegyzetek

  1. ↑ Choongbum Lee. A degenerált gráfok Ramsey-számai  // Annals of Mathematics. - 2017. - T. 185 , sz. 3. kérdés . - S. 791-829 . - arXiv : 1505.04773 .
  2. ↑ Václav Chvátal, Vojtěch Rödl, Semeredy Endre , William Trotter, Jr. Ramsey-szám korlátos fokszámú gráfhoz. (angolul)  = The Ramsey number of a graph with bounded maximum grade // 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. Ramsey-számok ritka gráfokhoz = Ramsey-számok ritka gráfokhoz // Discrete Mathematics. - 1998. - T. 185 , sz. 1–3 . – S. 63–75 . - doi : 10.1016/S0012-365X(97)00184-2 .
  4. ↑ Ronald Graham, Vojtěch Rödl, Andrzej Rucínski. Graphs with linear Ramsey numbers  = On graphs with linear Ramsey numbers // Journal of Graph Theory. - 2000. - T. 35 , sz. 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. Erdős Pál matematikája, II = The Mathematics of Paul Erdős, II / Szerk. Ronald Graham, Jaroslav Nešetřil. - Springer-Verlag, 1991. - S. 236-239.
  6. ↑ Noga Alon. A felosztott gráfoknak lineáris Ramsey-számai vannak  // Journal of Graph Theory. - 1994. - T. 18 , sz. 4 . – S. 343–347 . - doi : 10.1002/jgt.3190180406 . , Yusheng Li , Cecil C. Rousseau, Lubomir Soltes (Ľubomír Soltés). Ramsey lineáris családok és általánosított felosztott gráfok // Discrete Mathematics. - 1997. - T. 170 , sz. 1–3 . – S. 269–275 . - doi : 10.1016/S0012-365X(96)00311-1 .
  7. ↑ Jacob Fox, Benny Sudakov. Two  remarks on the Burr–Erdős conjecture (angol)  = Two remarks on the Burr–Erdős conjecture // European Journal of Combinatorics : Journal. - 2009. - 1. évf. 30 , iss. 7 . — P. 1630–1645 . - doi : 10.1016/j.ejc.2009.03.004 .

Linkek