Conjecture d'Erdős-Burr
En théorie des graphes, la conjecture d'Erdős-Burr, proposée en 1973 par Paul Erdős et Stefan Burr (en), concerne la croissance du nombre de Ramsey d'un graphe non orienté de degré de dégénérescence donné, en fonction de son nombre de sommets. Elle a été démontrée par Choongbum Lee en 2015[1] - [2].
Il découle du théorème de Ramsey qu'il existe un plus petit entier r(G), le nombre de Ramsey de G, tel que tout graphe complet d'au moins r(G) sommets dont les arêtes sont coloriées en rouge et bleu contienne une copie monochromatique de G.
Un graphe est dit p-dégénéré si tout sous-graphe contient un sommet de degré inférieur ou égal à p.
La conjecture est :
- pour tout entier p, il existe une constante cp telle que tout graphe p-dégénéré à n sommets ait son nombre de Ramsey majoré par cp n.
Avant d'être démontrée, elle a été vérifiée dans certains cas particuliers :
- pour les graphes de degré maximal borné ;
- pour les graphes p-arrangeables et, en particulier, les graphes planaires et les graphes sans subdivisions de ;
- pour les graphes subdivisés.
Références
, dont les références (en anglais) étaient (en 2005) :
- Noga Alon, Subdivided graphs have linear ramsey numbers, J. Graph Theory 18(4) (1994), 343–347.
- S. Burr et P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, Colloquia Mathematica Societatis Janos Bolyai 10 Infinite and Finite Sets 1 (1975), 214–240.
- Guantao Chen et Richard Schelp, Graphs with linearly bounded Ramsey numbers, J. Combin. Theory Ser. B 57(1) (1993), 138–149.
- Václav Chvátal, Vojtěch Rödl, Endre Szemerédi et William T. Trotter Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34(3) (1983), 239–243.
- Nancy Eaton, Ramsey numbers for sparse graphs, Discrete Maths 185 (1998), 63–75
- Ronald Graham, V. Rödl et Andrzej RucĂnski, On graphs with linear Ramsey numbers, Journal of Graph Theory 35 (2000), 176–192.
- R. Graham, V. Rödl et A. RucĂnski, On bipartite graphs with linear Ramsey numbers, Paul ErdĹ‘s and his mathematics, Combinatorica 21 (2001), 199–209.
- Yusheng Li, Cecil C. Rousseau et Ä˝ubomĂr SoltĂ©s, Ramsey linear families and generalized subdivided graphs, Discrete Mathematics (1997), 269–275.
- V. Rödl et Robin Thomas, Arrangeability and clique subdivisions, The mathematics of Paul Erdős (R. L. Graham et J. Nešetřil, éds.), Springer, 1991, p. 236–239.
- (en) Gil Kalai, « Choongbum Lee proved the Burr-Erdős conjecture », sur Combinatorics and more, .
- (en) Choongbum Lee, « Ramsey numbers of degenerate graphs », Annals of Mathematics, vol. 185, no 3,‎ , p. 791-829 (DOI 10.4007/annals.2017.185.3.2, arXiv 1505.04773).