En matemáticas , la conjetura de Burr-Erdős fue un problema relacionado con el número de Ramsey de grafos dispersos . 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 ; afirma que el número de Ramsey de los grafos en cualquier familia dispersa de grafos debería crecer linealmente en el número de vértices del grafo.
La conjetura fue demostrada por Choongbum Lee, por lo que ahora es un teorema. [1]
Definiciones
Si G es un grafo 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 grafo con degeneración p se llama p -degenerado. De manera equivalente, un grafo p -degenerado es un grafo que se puede reducir al grafo vacío eliminando repetidamente un vértice de grado p o menor.
Del teorema de Ramsey se deduce que para cualquier grafo G existe un número entero mínimo , el número de Ramsey de G , tal que cualquier grafo completo en al menos vértices cuyas aristas estén coloreadas de 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 se coloreen de rojo o azul las aristas de un grafo completo en seis vértices, 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 número de Ramsey como máximo c p n .
Es decir, si un grafo G de n vértices es p -degenerado, entonces debería existir una copia monocromática de G en cada grafo completo de dos aristas coloreadas en c p n vértices.
Resultados conocidos
Antes de que se demostrara por completo la conjetura, se estableció primero en algunos casos especiales. Fue demostrada para grafos de grado acotado 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 y Rucínski (2000) realizaron mejoras a esta constante. De manera más general, se sabe que la conjetura es verdadera para grafos p -ordenables, que incluyen grafos con grado máximo acotado, grafos planares y grafos que no contienen una subdivisión de K p . [2] También es conocida para grafos subdivididos, grafos en los que ningún par de vértices adyacentes tiene un grado mayor que dos. [3]
Para grafos arbitrarios, se sabe que el número de Ramsey está limitado por una función que crece sólo ligeramente de manera superlineal. Específicamente, Fox y Sudakov (2009) demostraron que existe una constante c p tal que, para cualquier grafo p -degenerado de n -vértices G ,
Notas
- ^ Lee (2017); Kalai (2015)
- ^ Rödl y Thomas (1991).
- ^ Alón (1994); Li, Rousseau y Soltés (1997).
Referencias
- Alon, Noga (1994), "Los gráficos subdivididos tienen números de Ramsey lineales", Journal of Graph Theory , 18 (4): 343–347, CiteSeerX 10.1.1.106.6586 , 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, vol. 10, Ámsterdam: Holanda Septentrional, págs. 214–240, SEÑOR 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 grafo 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), "Números de Ramsey para gráficos dispersos", 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, S2CID 8570007.
- Graham, Ronald ; Rödl, Vojtěch; Rucínski, Andrzej (2000), "Sobre gráficos 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, SEÑOR 1788033.
- Graham, Ronald ; Rödl, Vojtěch; Rucínski, Andrzej (2001), "Sobre grafos bipartitos con números de Ramsey lineales", Paul Erdős y sus matemáticas (Budapest, 1999), Combinatorica , 21 (2): 199–209, doi :10.1007/s004930100018, MR 1832445, S2CID 485716
- 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), "Números de Ramsey de grafos degenerados", Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi :10.4007/annals.2017.185.3.2, S2CID 7974973
- Li, Yusheng; Rousseau, Cecil C.; Soltés, Ľubomír (1997), "Familias lineales de Ramsey y grafos subdivididos generalizados", Discrete Mathematics , 170 (1–3): 269–275, doi :10.1016/S0012-365X(96)00311-1, MR 1452956.
- Rödl, Vojtěch; Thomas, Robin (1991), "Capacidad de organización y subdivisiones de camarillas", 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.
