Burr–Erdős-sejtés

A matematika, azon belül a gráfelmélet és Ramsey-elmélet területén a Choongbum Lee által 2015-ben bebizonyított Burr–Erdős-sejtés vagy Erdős–Burr-sejtés (tulajdonképpen: Lee-tétel) a ritka gráfok Ramsey-számával kapcsolatos probléma. Az Erdős Pál és Stefan Burr által felvetett kérdés az volt, hogy tetszőleges ritka gráfcsaládot figyelembe véve vajon a gráfok Ramsey-száma a csúcsok számával lineárisan növekszik-e.

Definíciók

Egy G irányítatlan gráf degeneráltsága az a minimális p természetes szám, melyre G bármely részgráfjában található legfeljebb p fokszámú csúcs. Egy p degeneráltságú gráfot p-degeneráltnak mondunk. Ekvivalens megfogalmazás szerint egy p-degenerált gráf a p-nél nem nagyobb fokszámú csúcsok ismételt eltávolításával üres gráffá redukálható.

A Ramsey-tételből következik, hogy minden G gráfhoz tartozik egy legkisebb $r(G)$ egész szám, avagy a G gráf Ramsey-száma, hogy bármely, legalább $r(G)$ méretű teljes gráf csúcsait két színnel kiszínezve a gráf tartalmazni fogja a G egyszínű kópiáját. Például a háromszög Ramsey-száma 6, mert a hat csúcsból álló teljes gráfot kék és piros színnel kiszínezve mindig találni fogunk vagy kék, vagy piros háromszöget.

A sejtés

1973-ban Stefan Burr és Erdős Pál a következőt sejtették meg:

Minden p egész számhoz létezik egy c_p konstans, melyre igaz, hogy bármely n csúcsú p-degenerált gráf Ramsey-száma legfeljebb c_p n.

Tehát ha egy n csúcsból álló G gráf p-degenerált, akkor a G egyszínű kópiája megtalálható bármely, két színnel színezett c_p n csúcsú teljes gráfban.

Ismert eredmények

Jóval a sejtés teljes bizonyítása előtt már léteztek részeredmények vele kapcsolatban. (Chvátal et al. 1983) igazolta korlátos fokszámú gráfokra; az ő bizonyításuk nagyon magas c_p konstanshoz vezetett; a konstanst (Eaton 1998), majd (Graham, Rödl & Rucínski 2000) javította meg. Általánosabban a sejtést igazolták a p-átrendezhető (p-arrangeable) gráfokra, melyek magukban foglalják a K_p felosztását nem tartalmazó gráfokat, a korlátos maximális fokszámú gráfokat és a síkbarajzolható gráfokat. Bizonyították a sejtést felosztott gráfokra, melyekben (élek úttá felosztása miatt) nem található egymással szomszédos csúcspár, melynek mindkét tagjának fokszáma kettőnél nagyobb lenne.

Általános gráfok Ramsey-számáról ismert, hogy felső korlátja egy a lineárisnál csak kissé erősebben növekvő függvény. Specifikusan, (Fox & Sudakov 2009) megmutatta, hogy létezik olyan c_p konstans, amire bármely p-degenerált n-csúcsú G gráfra:

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

Fordítás

• Ez a szócikk részben vagy egészben az Erdős–Burr conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Alon, Noga (1994), "Subdivided graphs have linear Ramsey numbers", Journal of Graph Theory 18 (4): 343–347, DOI 10.1002/jgt.3190180406.
• Burr, Stefan A. & Erdős, Paul (1975), "On the magnitude of generalized Ramsey numbers for graphs", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. 1, vol. 10, Colloq. Math. Soc. János Bolyai, Amsterdam: North-Holland, pp. 214–240, <http://www.renyi.hu/~p_erdos/1975-26.pdf>.
• Chen, Guantao & Schelp, Richard H. (1993), "Graphs with linearly bounded Ramsey numbers", Journal of Combinatorial Theory, Series B 57 (1): 138–149, DOI 10.1006/jctb.1993.1012.
• Chvátal, Václav; Rödl, Vojtěch & Szemerédi, Endre et al. (1983), "The Ramsey number of a graph with bounded maximum degree", Journal of Combinatorial Theory, Series B 34 (3): 239–243, DOI 10.1016/0095-8956(83)90037-0.
• Eaton, Nancy (1998), "Ramsey numbers for sparse graphs", Discrete Mathematics 185 (1–3): 63–75, DOI 10.1016/S0012-365X(97)00184-2.
• Fox, Jacob & Sudakov, Benny (2009), "Two remarks on the Burr–Erdős conjecture", European Journal of Combinatorics 30 (7): 1630–1645, DOI 10.1016/j.ejc.2009.03.004.
• Graham, Ronald; Rödl, Vojtěch & Rucínski, Andrzej (2000), "On graphs with linear Ramsey numbers", Journal of Graph Theory 35 (3): 176–192, DOI 10.1002/1097-0118(200011)35:3<176::AID-JGT3>3.0.CO;2-C.
• Graham, Ronald; Rödl, Vojtěch & Rucínski, Andrzej (2001), "On bipartite graphs with linear Ramsey numbers", Combinatorica 21 (2): 199–209, DOI 10.1007/s004930100018
• Kalai, Gil (May 22, 2015), Choongbum Lee proved the Burr-Erdős conjecture, <https://gilkalai.wordpress.com/2015/05/22/choongbum-lee-proved-the-burr-erdos-conjecture/>. Hozzáférés ideje: 2017-10-01
• Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics 185 (3): 791-829, DOI 10.4007/annals.2017.185.3.2
• Li, Yusheng; Rousseau, Cecil C. & Soltés, Ľubomír (1997), "Ramsey linear families and generalized subdivided graphs", Discrete Mathematics 170 (1–3): 269–275, DOI 10.1016/S0012-365X(96)00311-1.
• Rödl, Vojtěch & Thomas, Robin (1991), "Arrangeability and clique subdivisions", in Graham, Ronald & Nešetřil, Jaroslav, The Mathematics of Paul Erdős, II, Springer-Verlag, pp. 236–239, <http://www.math.gatech.edu/~thomas/PAP/arran.pdf>. Hozzáférés ideje: 2017-10-02.