En matemáticas , la conjetura de Burr-Erd era un problema relacionado con el número de gráficos dispersos de Ramsey . La conjetura lleva el nombre de Stefan Burr y Paul Erdős , y es una de las muchas conjeturas que llevan el nombre de Erdős ; establece que el número de gráficos de Ramsey en cualquier familia de gráficos dispersos debería crecer linealmente en el número de vértices del gráfico.
La conjetura fue probada por Choongbum Lee (por lo que ahora es un teorema). [1]
Definiciones
Si G es un gráfico no dirigido , entonces la degeneración de G es el número mínimo p tal que cada subgrafo de G contiene un vértice de grado p o menor. Un gráfico con degeneración p se llama p -degenerado. De manera equivalente, un gráfico p -degenerado es un gráfico que se puede reducir al gráfico vacío eliminando repetidamente un vértice de grado p o menor.
Se deduce del teorema de Ramsey que para cualquier grafo G existe un número entero mínimo, el número de Ramsey de G , de modo que cualquier gráfico completo en al menos vértices cuyos bordes son de color rojo o azul contiene una copia monocromática de G . Por ejemplo, el número de Ramsey de un triángulo es 6: no importa cómo los bordes de un gráfico completo en seis vértices sean de color rojo o azul, siempre hay un triángulo rojo o un triángulo azul.
La conjetura
En 1973, Stefan Burr y Paul Erdős hicieron la siguiente conjetura:
- Para cada entero p existe una constante c p de modo que cualquier grafo p -degenerado G en n vértices tiene un número de Ramsey como máximo c p n .
Es decir, si un gráfico de n -vértices G es p -degenerado, entonces debería existir una copia monocromática de G en cada gráfico completo de dos bordes de color en c p n vértices.
Resultados conocidos
Antes de que se probara la conjetura completa, primero se resolvió en algunos casos especiales. Fue probado para gráficos de grados acotados por Chvátal et al. (1983) ; su demostración condujo a un valor muy alto de c p , y Eaton (1998) y Graham, Rödl & Rucínski (2000) mejoraron esta constante . De manera más general, se sabe que la conjetura es cierta para las gráficas ordenables p , que incluyen gráficas con grado máximo acotado, gráficas planas y gráficas que no contienen una subdivisión de K p . [2] También es conocido por gráficos subdivididos, gráficos en los que no hay dos vértices adyacentes que tengan un grado mayor que dos. [3]
Para gráficas arbitrarias, se sabe que el número de Ramsey está limitado por una función que crece solo ligeramente de manera superlineal. Específicamente, Fox y Sudakov (2009) demostraron que existe una constante c p tal que, para cualquier gráfico p -degenerado n- vértice G ,
Notas
Referencias
- Alon, Noga (1994), "Los gráficos subdivididos tienen números lineales de Ramsey", Journal of Graph Theory , 18 (4): 343–347, doi : 10.1002 / jgt.3190180406 , MR 1277513.
- Burr, Stefan A .; Erdős, Paul (1975), "Sobre la magnitud de los números de Ramsey generalizados para gráficos", Conjuntos infinitos y finitos (Colloq., Keszthely, 1973; dedicado a P. Erdős en su 60 cumpleaños), vol. 1 (PDF) , Coloq. Matemáticas. Soc. János Bolyai, 10 , Amsterdam: North-Holland, págs. 214-240, MR 0371701.
- Chen, Guantao; Schelp, Richard H. (1993), "Gráficos con números de Ramsey acotados linealmente", Journal of Combinatorial Theory, Serie B , 57 (1): 138–149, doi : 10.1006 / jctb.1993.1012 , MR 1198403.
- Chvátal, Václav ; Rödl, Vojtěch; Szemerédi, Endre ; Trotter, William T., Jr. (1983), "El número de Ramsey de un gráfico con grado máximo acotado", Journal of Combinatorial Theory, Serie B , 34 (3): 239–243, doi : 10.1016 / 0095-8956 ( 83) 90037-0 , MR 0714447.
- Eaton, Nancy (1998), "Ramsey numbers for sparse graphs", Discrete Mathematics , 185 (1-3): 63-75, doi : 10.1016 / S0012-365X (97) 00184-2 , MR 1614289.
- Fox, Jacob; Sudakov, Benny (2009), "Dos observaciones sobre la conjetura de Burr-Erdős", European Journal of Combinatorics , 30 (7): 1630-1645, arXiv : 0803.1860 , doi : 10.1016 / j.ejc.2009.03.004 , MR 2548655.
- Graham, Ronald ; Rödl, Vojtěch; Rucínski, Andrzej (2000), "Sobre gráficas con números lineales de Ramsey", Journal of Graph Theory , 35 (3): 176-192, doi : 10.1002 / 1097-0118 (200011) 35: 3 <176 :: AID-JGT3 > 3.0.CO; 2-C , MR 1788033.
- Graham, Ronald ; Rödl, Vojtěch; Rucínski, Andrzej (2001), "Sobre gráficos bipartitos con números lineales de Ramsey", Paul Erdős y sus matemáticas (Budapest, 1999), Combinatorica , 21 (2): 199-209, doi : 10.1007 / s004930100018 , MR 1832445
- Kalai, Gil (22 de mayo de 2015), "Choongbum Lee demostró la conjetura de Burr-Erdős" , Combinatoria y más , consultado el 22 de mayo de 2015
- Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi : 10.4007 / annals.2017.185.3.2
- Li, Yusheng; Rousseau, Cecil C .; Soltés, Ľubomír (1997), "Familias lineales de Ramsey y gráficas subdivididas generalizadas", Matemáticas discretas , 170 (1-3): 269-275, doi : 10.1016 / S0012-365X (96) 00311-1 , MR 1452956.
- Rödl, Vojtěch; Thomas, Robin (1991), "Arrangeability and clique subdivisions", en Graham, Ronald ; Nešetřil, Jaroslav (eds.), Las matemáticas de Paul Erdős, II (PDF) , Springer-Verlag, págs. 236–239, MR 1425217.