Cubierta plana

Una cubierta plana de un grafo finito G  es una cubierta finita de G que es un grafo plano . Cualquier gráfico que se pueda incrustar en el plano proyectivo tiene una cubierta plana. La conjetura no resuelta de Seiya Negami establece que solo estos gráficos tienen cubiertas planas [1] .

La existencia de una cubierta plana es una propiedad cerrada bajo menores [2] , y por lo tanto puede ser descrita por un número finito de menores prohibidos , pero se desconoce el conjunto exacto de menores prohibidos. Por las mismas razones, existe un algoritmo de tiempo polinomial para probar si un gráfico dado tiene una cobertura plana, pero no se conoce una descripción explícita de este algoritmo.

Definición

Una aplicación de cobertura de un gráfico C a otro gráfico H se puede describir mediante una función f desde los vértices de C hasta los vértices de H , que para cada vértice v de C crea una biyección entre la vecindad de v y la vecindad de f ( v ) [3] . Si H es un grafo conexo , cada vértice de H debe tener el mismo número de vértices en la preimagen de C [2] . Este número se llama el número de capas del mapa, y C se llama el gráfico de cobertura de G. Si tanto C como H son finitos y C es un gráfico plano , C se llama cubierta plana de H.

Ejemplos

El gráfico de un dodecaedro regular tiene una simetría que asigna cada vértice a un vértice antípoda. El conjunto de pares antípodas de vértices y sus adyacencias también se puede ver como un gráfico, el gráfico de Petersen . El dodecaedro forma una cubierta plana de este gráfico no plano [4] . Este ejemplo muestra que no todos los gráficos con una cubierta plana son en sí mismos planos. Cuando un gráfico plano cubre uno no plano, el número de capas debe ser par [5] [6] .

La gráfica de un prisma k -gonal tiene 2k vértices y es plana con dos k caras -gonales y k caras cuadradas. Si k  =  ab , y , entonces el gráfico tiene una capa que cubre la correspondencia en un prisma de lados b en el que dos vértices del prisma k se asignan al mismo vértice del prisma b si ambos pertenecen al mismo caras k -gonales y la distancia de una a la otra es múltiplo de b . Por ejemplo, un prisma dodecagonal puede formar una cubierta de dos capas de un prisma hexagonal , una cubierta de tres capas de un cubo o una cubierta de cuatro capas de un prisma triangular . Estos ejemplos muestran que un gráfico puede tener muchas cubiertas planas diferentes y puede ser una cubierta plana para muchas gráficas. Además, estos ejemplos muestran que la fibra de una cubierta plana puede ser arbitrariamente grande. No solo cubren prismas, por ejemplo, un prisma hexagonal también puede cubrir un grafo comunal no plano K 3,3 identificando pares de vértices antípodas [7] .

Operaciones de conservación de la cubierta

Si el grafo H tiene una cubierta plana, entonces lo mismo es cierto para cualquier grafo menor del grafo H [2] . Se puede formar una G menor de un grafo H quitando aristas y vértices de H y contrayendo aristas en H . El grafo de cobertura C se puede transformar de la misma manera: para cada vértice eliminado de H , eliminamos su preimagen en C , y para cada borde o vértice contraído de H , reducimos su preimagen a C. El resultado de estas operaciones sobre C será un menor de C que cubre a G. Dado que cualquier menor de un gráfico plano es en sí mismo plano, esto da una cobertura plana del menor de G .

Dado que los grafos con cubiertas planas se cierran bajo la operación de tomar menores, del teorema de Robertson-Seymour se deduce que pueden describirse mediante un conjunto finito de menores prohibidos [8] . Un grafo es un menor prohibido para esta propiedad si no tiene cobertura plana, pero todos sus menores tienen cobertura plana. Esta descripción se puede utilizar para probar la existencia de un algoritmo de tiempo polinomial que prueba la existencia de una cobertura plana buscando cada menor prohibido y devuelve "existe una cobertura plana" si esa búsqueda no encuentra ninguna [9] . Sin embargo, dado que no se conoce el conjunto exacto de menores prohibidos para esta propiedad, esta prueba de existencia no es constructiva y no conduce a una descripción explícita del conjunto de menores prohibidos o un algoritmo basado en ellos [10]

Otra operación sobre grafos que preserva la existencia de una cubierta plana es la transformación estrella-triángulo , que reemplaza cualquier vértice de grado tres en H con un triángulo de sus tres vecinos [2] . Sin embargo, la transformación inversa, la transformación delta-estrella, no conserva necesariamente las cubiertas planas.

Además, la unión disjunta de dos gráficos que tienen cubiertas también tendrá una cubierta formada como la unión disjunta de los gráficos que las cubren. Si dos revestimientos tienen la misma fibra, será también la fibra de su unión.

La hipótesis de Negami

Problemas no resueltos en Matemáticas : ¿Cualquier gráfico conectado con una cubierta plana tiene una incrustación en el plano proyectivo?

Si un grafo H tiene un empotramiento en el plano proyectivo , entonces necesariamente tiene una cobertura plana dada por la imagen inversa de H en la doble cobertura orientable plano proyectivo, que es una esfera. Negami [11] demostró lo contrario, que si un grafo conexo H tiene una cubierta plana de dos capas, entonces H debe tener una incrustación en el plano proyectivo [11] [12] . La suposición de que H es conexa es necesaria aquí, ya que la unión disjunta de grafos proyectivamente planos puede no ser proyectivamente plana [13] pero aun así tener una cubierta plana, la unión disjunta de cubiertas dobles orientables.

Una cobertura regular de un gráfico H  es una cobertura resultante del grupo de simetría de su gráfico de cobertura: las imágenes inversas de cada vértice en H forman una órbita del grupo. Negami [14] probó que cualquier grafo conexo con un recubrimiento plano regular puede estar embebido en un plano proyectivo [14] [15] . Basándose en estos dos resultados, conjeturó que, de hecho, cualquier gráfico conexo con una cubierta plana es proyectivo [14] [16] . A partir de 2013, la hipótesis quedó sin resolver [17] . También se conoce como la " conjetura de Negami", ya que puede reformularse como el enunciado de que el número mínimo de fibras de una cubierta plana, si existe, debe ser 1 o 2 [18] .

Al igual que los gráficos con cubiertas planas, los gráficos con incrustaciones en el plano proyectivo pueden ser descritos por menores prohibidos. En este caso, se conoce el conjunto exacto de menores prohibidos, hay 35. 32 de ellos son conexos, y uno de estos 32 gráficos necesariamente aparece como un menor en cualquier gráfico plano no proyectivo conexo [19] [20] . Cuando Negami presentó su conjetura, se demostró que 31 de estos 32 menores prohibidos no tienen cubiertas planas o pueden reducirse mediante una transformación estrella-triángulo a gráficos más simples de esta lista [14] [18] [21] [22 ] [ 23] . El único gráfico restante para el que aún no se ha hecho esto es K 1,2,2,2 , un gráfico de vértice con siete vértices que forma el esqueleto de una pirámide octaédrica de cuatro dimensiones . Si mostramos que K 1,2,2,2 no tiene cubiertas planas, esta será una prueba completa de la conjetura. Por otro lado, si la conjetura no es cierta, K 1,2,2,2 será un contraejemplo mínimo [24] .

Una conjetura relacionada de Michael Fellows, ya resuelta, se trata de emuladores planos , una generalización de coberturas planas donde las vecindades gráficas se mapean sobreyectivamente en lugar de biyectivamente [25] [26] [27] . Los gráficos con emuladores planos, como los gráficos [29][28]con coberturas planas, se cierran bajo menores y transformaciones estrella-triángulo [30] . La conjetura es cierta para emuladores regulares derivados de automorfismos del grafo de cobertura subyacente, similar al resultado de Negami [14] para coberturas planas regulares [26] . Sin embargo, resultó que algunos de los 32 menores prohibidos conectados para grafos proyectivamente planos tienen emuladores planos [31] [32] [17] . Por lo tanto, la hipótesis de Fellowes no es correcta. Encontrar el conjunto completo de menores prohibidos para la existencia de emuladores planares sigue siendo un problema abierto [33] .

Notas

  1. ↑ Hliněny, 2010 , p. una.
  2. ↑ 1 2 3 4 Hliněný, 2010 , pág. 2 Proposición 1.
  3. ↑ Hliněny, 2010 , p. 2 Definición.
  4. ↑ Inkmann, Thomas (2011 ): "Esta construcción se ilustra en la Figura 1, donde el dodecaedro se muestra como una cubierta doble plana del gráfico de Petersen".
  5. ↑ Archidiácono, Richter, 1990 .
  6. ↑ Negami, 2003 .
  7. ↑ Zelinka, 1982 .
  8. ↑ Robertson, Seymour, 2004 .
  9. ↑ Robertson, Seymour, 1995 .
  10. ↑ Becarios, Langston (1988 ); Becarios, Koblitz (1992 ). Fellowes y Koblitz demostraron como ejemplo la no constructividad de la verificación algorítmica de la existencia de cubiertas planas de plegado k .
  11. ↑ 12 Negami , 1986 .
  12. ↑ Hliněny, 2010 , p. 2 Teorema 2.
  13. ↑ Por ejemplo, dos grafos de Kuratowski son proyectivamente planos, cualquier unión de dos de ellos no lo es ( Archidiácono 1981 ).
  14. ↑ 1 2 3 4 5 Negami, 1988 .
  15. ↑ Hliněny, 2010 , p. 3 Teorema 3.
  16. ↑ Hliněny, 2010 , p. 4 Conjetura 4.
  17. ↑ 1 2 Chimani, Derka, Hliněny, Klusáček, 2013 .
  18. ↑ 12Huneke , 1993 .
  19. ↑ Hliněny, 2010 , p. cuatro
  20. ↑ Se puede encontrar una lista de menores planos proyectivos prohibidos en Archdeacon (1981 ). Negami Negami (1988 ) afirmó la observación correspondiente para 103 gráficos planos no proyectivos irreducibles de Glover, Huneke, Wang (1979 ).
  21. ↑ Hliněny, 1998 .
  22. ↑ Archidiácono, 2002 .
  23. ↑ Hliněny, 2010 , p. 4–6.
  24. ↑ Hliněny, 2010 , p. 6–9.
  25. ↑ Becarios, 1985 .
  26. ↑ 12Kitakubo , 1991 .
  27. ↑ Hliněny, 2010 , p. 9 Definición, pág.
  28. ↑ Hliněny, 2010 , p. 9 Proposición 13.
  29. ↑ Glineny atribuye este hecho a Fellows y escribe que su prueba no es trivial
  30. ↑ Hliněny, 2010 , p. 9, Conjetura 14.
  31. ↑ Hliněny, 2010 , p. 9–10.
  32. ↑ Rieck, Yamashita, 2010 .
  33. ↑ Hliněny, 2010 , p. diez.

Literatura

Fuentes secundarias sobre la conjetura de Negami

Principales fuentes sobre revestimientos planos

Literatura auxiliar