Problema no resuelto en matemáticas :
¿Todo gráfico contable tiene una partición hostil en dos partes?
En las matemáticas de gráficos infinitos , una partición hostil o coloración mayoritaria es una partición de los vértices del gráfico en subconjuntos disjuntos, de modo que cada vértice tenga al menos tantos vecinos en otros conjuntos como en su propio conjunto. Es una generalización del concepto de corte máximo para gráficos finitos, que es automáticamente una partición hostil. (De lo contrario, un vértice con más vecinos en su propio conjunto podría moverse al otro conjunto, aumentando el número de bordes cortados). La conjetura de la partición hostil es un problema no resuelto que pregunta si todo gráfico contable tiene una partición hostil en dos subconjuntos. [1]
Robert H. Cowan y William R. Emerson, en un trabajo inédito, conjeturaron que todo grafo infinito tiene una partición hostil en dos subconjuntos. Sin embargo, Saharon Shelah y Eric Charles Milner refutaron la conjetura, mostrando que los gráficos incontables podrían no tener particiones hostiles de dos subconjuntos. Sin embargo, demostraron que siempre existe una división hostil en tres subconjuntos. [2]
Entre los gráficos contables, se conoce la existencia de una partición no amigable de dos subconjuntos para los siguientes casos especiales:
- Gráficos que tienen un número finito de vértices de grado infinito [3]
- Gráficos en los que todos los vértices tienen grado infinito, mediante un argumento que utiliza el método de ida y vuelta [1]
- Gráficos sin fin [4]
- Gráficos sin subdivisión de una camarilla infinita [5]
El caso de los gráficos contables arbitrarios sigue abierto. [1]
Referencias
- ^ abc DeVos, Matthew (22 de octubre de 2007), "Particiones hostiles", Jardín de problemas abiertos
- ^ Sela, Saharon ; Milner, EC (1990), "Gráficos sin particiones hostiles" (PDF) , en Baker, A.; Bollobás, B.; Hajnal, A. (eds.), Un tributo a Paul Erdős , Cambridge University Press, págs. 373–384, doi :10.1177/016502549001300309, MR 1117030, S2CID 143480036
- ^ Aharoni, R.; Milner, CE; Prikry, K. (1990), "Particiones hostiles de un gráfico", Journal of Combinatorial Theory , Serie B, 50 (1): 1–10, doi : 10.1016/0095-8956(90)90092-E , MR 1070461
- ^ Bruhn, Henning; Diestel, Reinhard; Georgakopoulos, Agelos; Sprüssel, Philipp (2010), "Todo gráfico sin rayos tiene una partición hostil", Combinatorica , 30 (5): 521–532, doi :10.1007/s00493-010-2590-3, MR 2776717, S2CID 9304176
- ^ Berger, Eli (2017), "Particiones hostiles para gráficos que no contienen una subdivisión de una camarilla infinita", Combinatorica , 37 (2): 157–166, doi :10.1007/s00493-015-3261-1, MR 3638340, S2CID 254028041
