En la teoría de grafos , una rama de las matemáticas, el eje de Moser (también llamado eje de Moser o gráfico de Moser ) es un gráfico no dirigido , llamado así por los matemáticos Leo Moser y su hermano William, [1] con siete vértices y once aristas. Es un gráfico de unidad de distancia que requiere cuatro colores en cualquier color de gráfico , y su existencia puede usarse para probar que el número cromático del plano es al menos cuatro. [2]
Husillo Moser | |
---|---|
![]() | |
Lleva el nombre de | Leo Moser , William Moser |
Vértices | 7 |
Bordes | 11 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 8 |
Número cromático | 4 |
Índice cromático | 4 |
Propiedades | unidad plana distancia gráfico de Laman |
Tabla de gráficos y parámetros |
El eje de Moser también se ha denominado gráfico de Hajós en honor a György Hajós , ya que puede verse como una instancia de la construcción de Hajós . [3] Sin embargo, el nombre "gráfico de Hajós" también se ha aplicado a un gráfico diferente, en forma de triángulo inscrito dentro de un hexágono. [4]
Construcción
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a3/Hadwiger-Nelson.svg/240px-Hadwiger-Nelson.svg.png)
Como gráfico de unidad de distancia, el eje de Moser está formado por dos rombos con ángulos de 60 y 120 grados, de modo que los lados y las diagonales cortas de los rombos forman triángulos equiláteros. Los dos rombos se colocan en el plano, compartiendo uno de sus vértices de ángulo agudo, de tal manera que los dos vértices de ángulo agudo restantes están separados por una unidad de distancia entre sí. Los once bordes del gráfico son los ocho lados del rombo, las dos diagonales cortas de los rombos y el borde entre el par de unidades de distancia de vértices de ángulos agudos.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/28/Hajos_construction.svg/220px-Hajos_construction.svg.png)
El eje de Moser también se puede construir de forma gráfica, sin referencia a una incrustación geométrica, utilizando la construcción de Hajós comenzando con dos gráficos completos en cuatro vértices. Esta construcción elimina un borde de cada gráfico completo, fusiona dos de los puntos finales de los bordes eliminados en un solo vértice compartido por ambas camarillas y agrega un nuevo borde que conecta los dos puntos finales restantes del borde eliminado. [5]
Otra forma de construir el eje de Moser es como el gráfico de complemento del gráfico formado a partir del gráfico de utilidad K 3,3 subdividiendo uno de sus bordes. [6]
Aplicación al problema de Hadwiger-Nelson
El problema de Hadwiger-Nelson pregunta cuántos colores se necesitan para colorear los puntos del plano euclidiano de tal manera que a cada par de puntos a una distancia unitaria entre sí se les asignen colores diferentes. Es decir, pide el número cromático del gráfico infinito cuyos vértices son todos los puntos en el plano y cuyas aristas son todos pares de puntos a la unidad de distancia. [2]
El eje de Moser requiere cuatro colores en cualquier color de gráfico: en cualquier color tricolor de uno de los dos rombos a partir de los cuales se forma, los dos vértices de ángulo agudo de los rombos tendrían necesariamente el mismo color entre sí. Pero si el vértice compartido de los dos rombos tiene el mismo color que los dos vértices opuestos de ángulos agudos, entonces estos dos vértices tienen el mismo color entre sí, violando el requisito de que el borde que los conecta tenga extremos de colores diferentes. Esta contradicción muestra que tres colores son imposibles, por lo que son necesarios al menos cuatro colores. Cuatro colores también son suficientes para colorear el huso de Moser, un hecho que se sigue, por ejemplo, del hecho de que su degeneración es de tres.
Una prueba alternativa de que el eje Moser requiere cuatro colores se deriva de la construcción de Hajós. Los dos gráficos completos a partir de los cuales se forma el eje de Moser requieren cuatro colores, y la construcción de Hajós conserva esta propiedad. [5] Incluso más directamente, cada conjunto independiente en el eje de Moser tiene como máximo dos vértices, [7] por lo que se necesitan al menos cuatro conjuntos independientes para cubrir los siete vértices.
Dado que el eje de Moser es un subgrafo del gráfico de distancia unitaria infinita del plano, el gráfico del plano también requiere al menos cuatro colores en cualquier color. Según el teorema de De Bruijn-Erdős (asumiendo que el axioma de elección es verdadero), el número cromático del plano es el mismo que el número cromático más grande de cualquiera de sus subgrafos finitos; Hasta el descubrimiento de una familia de gráficos de distancia de 5 unidades cromáticas en 2018, no se había encontrado ningún subgrafo del gráfico de distancia de unidad infinita que requiera una mayor cantidad de colores que el eje Moser. Sin embargo, el mejor límite superior para el número cromático del plano es siete, significativamente más alto que el número de colores requeridos para el eje Moser. [2]
Otras propiedades y aplicaciones
El eje de Moser es un gráfico plano , lo que significa que se puede dibujar sin cruces en el plano. Sin embargo, no es posible formar un dibujo de este tipo con bordes en línea recta que también sea un dibujo de distancia unitaria; es decir, no es un gráfico de cerillas . El eje de Moser también es un gráfico de Laman , lo que significa que forma un sistema mínimamente rígido cuando está incrustado en el plano. [8] Como gráfico plano de Laman, es el gráfico de una pseudotriangulación puntiaguda, lo que significa que se puede incrustar en el plano de tal manera que la cara ilimitada es el casco convexo de la incrustación y cada cara acotada es un pseudotriangulo con solo tres vértices convexos. [9]
El gráfico de complemento del gráfico de Moser es un gráfico sin triángulos . Por lo tanto, la incrustación de la unidad de distancia del gráfico de Moser puede usarse para resolver el problema de colocar siete puntos en el plano de tal manera que cada triple de puntos contenga al menos un par a una unidad de distancia entre sí. [2] [10]
Agregar cualquier borde al eje de Moser da como resultado un gráfico que no se puede incrustar en el plano como un gráfico de unidad de distancia, y no existe un homomorfismo de gráfico desde el eje de Moser a ningún gráfico de unidad de distancia más pequeño. Estas dos propiedades del husillo de Moser fueron utilizadas por Horvat, Kratochvíl y Pisanski (2011) para mostrar la dureza NP de probar si un gráfico dado tiene una representación de distancia unitaria bidimensional; la prueba utiliza una reducción de 3SAT en la que el eje Moser se utiliza como el dispositivo central de establecimiento de la verdad en la reducción. [8]
El eje de Moser también se puede usar para probar un resultado en la teoría euclidiana de Ramsey : si T es cualquier triángulo en el plano, y los puntos del plano son de dos colores, negro y blanco, entonces hay una traducción negra de T o una par de puntos blancos a una unidad de distancia entre sí. Para, deja que M sea una incrustación unidad de distancia del husillo Moser, y dejar que M + T sea la suma de Minkowski de M y T . Si M + T no tiene un par blanco unidad-distancia, entonces cada una de las tres copias del eje de Moser en M + T debe tener como máximo dos puntos blancos, porque los puntos blancos en cada copia deben formar un conjunto independiente y el mayor independiente en el eje Moser tiene tamaño dos. Por lo tanto, entre los siete vértices del eje de Moser, hay como máximo seis que tienen una copia en blanco en M + T , por lo que debe haber uno de los siete vértices cuyas copias son todas negras. Pero entonces las tres copias de este vértice forman un traducen de T . [7]
Ver también
- Gráfico de Golomb
Referencias
- ^ Moser, L .; Moser, W. (1961), "Solución al problema 10", Can. Matemáticas. Toro. , 4 : 187–189.
- ^ a b c d Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators , Nueva York: Springer, págs. 14-15, ISBN 978-0-387-74640-1.
- ^ Bondy, JA; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, 244 , Springer, p. 358, doi : 10.1007 / 978-1-84628-970-5 , ISBN 978-1-84628-969-9.
- ^ Berge, C. (1989), "Relaciones mínimas para los q -colorings parciales de un gráfico", Matemáticas discretas , 74 (1–2): 3–14, doi : 10.1016 / 0012-365X (89) 90193-3 , Señor 0989117.
- ^ a b Hajós, G. (1961), "Über eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 10 : 116-117.
- ^ Gervacio, Severino V .; Lim, Yvette F .; Maehara, Hiroshi (2008), "Gráficos planos de unidad-distancia con complemento plano de unidad-distancia", Matemáticas discretas , 308 (10): 1973-1984, doi : 10.1016 / j.disc.2007.04.050 , MR 2394465.
- ^ a b Burkert, Jeffrey; Johnson, Peter (2011), "El lema de Szlam: descendiente mutante de un problema de Ramsey euclidiano de 1973, con numerosas aplicaciones", teoría de Ramsey , Progr. Math., 285 , Birkhäuser / Springer, Nueva York, págs. 97-113, doi : 10.1007 / 978-0-8176-8092-3_6 , MR 2759046. Véase también Soifer (2008) , problema 40.26, p. 496.
- ^ a b Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011), "On the Computational Complexity of Degenerate Unit Distance Representations of Graph", Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, Londres, Reino Unido, 26-28 de julio de 2010, artículos seleccionados revisados , notas de conferencias en computadora Science, 6460 , págs. 274–285, arXiv : 1001.0886 , Bibcode : 2011LNCS.6460..274H , doi : 10.1007 / 978-3-642-19222-7_28 , ISBN 978-3-642-19221-0.
- ^ Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servacio, Brigitte ; Servacio, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005), "Gráficos planos mínimamente rígidos y pseudo-triangulaciones", Teoría y aplicaciones de la geometría computacional , 31 (1-2): 31-61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 0.003 , MR 2131802.
- ^ Winkler, Peter (noviembre de 2011), "Desconcertado: Distancias entre puntos en el plano", Comunicaciones del ACM , 54 (11): 120, doi : 10.1145 / 2018396.2018422. Solución, número 12, diciembre de 2011, doi : 10.1145 / 2043174.2043200 .
enlaces externos
- Weisstein, Eric W. "Moser Spindle" . MathWorld .