En la teoría de grafos , una rama de las matemáticas, el huso de Moser (también llamado huso de Moser o grafo de Moser ) es un grafo no dirigido , llamado así por los matemáticos Leo Moser y su hermano William, [1] con siete vértices y once aristas. Es un grafo de distancia unitaria que requiere cuatro colores en cualquier coloración del grafo , y su existencia puede usarse para demostrar que el número cromático del plano es al menos cuatro. [2]
El huso de Moser también ha sido llamado grafo de Hajós en honor a György Hajós , ya que puede considerarse como un ejemplo de la construcción de Hajós . [3] Sin embargo, el nombre "grafo de Hajós" también se ha aplicado a un grafo diferente, en forma de un triángulo inscrito dentro de un hexágono. [4]
Como grafo de distancia unitaria, el huso 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 están colocados en el plano, compartiendo uno de sus vértices acutángulos, de tal manera que los dos vértices acutángulos restantes están separados por una distancia unitaria. Las once aristas del grafo son los ocho lados del rombo, las dos diagonales cortas de los rombos y la arista entre el par de vértices acutángulos de distancia unitaria.
El huso de Moser también puede construirse 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 una arista de cada gráfico completo, fusiona dos de los puntos finales de las aristas eliminadas en un único vértice compartido por ambas camarillas y agrega una nueva arista que conecta los dos puntos finales restantes de la arista eliminada. [5]
Otra forma de construir el huso de Moser es como el gráfico complementario del gráfico formado a partir del gráfico de utilidad K 3,3 al subdividir una de sus aristas. [6]
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 que se encuentran a una distancia unitaria entre sí se les asigne un color diferente. Es decir, pregunta por el número cromático del grafo infinito cuyos vértices son todos los puntos del plano y cuyas aristas son todos los pares de puntos que se encuentran a una distancia unitaria. [2]
El huso de Moser requiere cuatro colores en cualquier coloración del grafo: en cualquier coloración tricolor de uno de los dos rombos de los que está formado, los dos vértices acutángulos 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 acutángulos opuestos, entonces estos dos vértices tienen el mismo color entre sí, violando el requisito de que la arista que los conecta tenga puntos finales de diferente color. Esta contradicción muestra que tres colores son imposibles, por lo que al menos son necesarios cuatro colores. Cuatro colores también son suficientes para colorear el huso de Moser, un hecho que se desprende, por ejemplo, del hecho de que su degeneración es tres.
Una prueba alternativa de que el huso de Moser requiere cuatro colores se desprende de la construcción de Hajós. Ambos grafos completos a partir de los cuales se forma el huso de Moser requieren cuatro colores, y la construcción de Hajós conserva esta propiedad. [5] De manera aún más directa, cada conjunto independiente en el huso 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 huso de Moser es un subgrafo del grafo de distancia unitaria infinita del plano, el grafo del plano también requiere al menos cuatro colores en cualquier coloración. Por el teorema de de Bruijn–Erdős (con la suposición de 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 grafos de distancia unitaria de 5 cromáticos en 2018, no se había encontrado ningún subgrafo del grafo de distancia unitaria infinita que requiriera un número mayor de colores que el huso de Moser. Sin embargo, el mejor límite superior para el número cromático del plano es siete, significativamente mayor que el número de colores requeridos para el huso de Moser. [2]
El huso de Moser es un grafo 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 de línea recta que también sea un dibujo de distancia unitaria; es decir, no es un grafo de cerillas . El huso de Moser también es un grafo de Laman , lo que significa que forma un sistema mínimamente rígido cuando se incrusta en el plano. [8] Como grafo de Laman plano, es el grafo de una pseudotriangulación puntiaguda, lo que significa que se puede incrustar en el plano de tal manera que la cara no acotada sea la envoltura convexa de la incrustación y cada cara acotada sea un pseudotriángulo con solo tres vértices convexos. [9]
El grafo complementario del grafo de Moser es un grafo sin triángulos . Por lo tanto, la incrustación de distancia unitaria del grafo de Moser se puede utilizar 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 distancia unitaria entre sí. [2] [10]
La adición de cualquier borde al huso de Moser da como resultado un grafo que no se puede incrustar en el plano como un grafo de distancia unitaria, y no existe un homomorfismo de grafos desde el huso de Moser a ningún grafo de distancia unitaria más pequeño. Horvat, Kratochvíl y Pisanski (2011) utilizaron estas dos propiedades del huso de Moser para demostrar la NP-dureza de probar si un grafo dado tiene una representación de distancia unitaria bidimensional; la prueba utiliza una reducción de 3SAT en la que el huso de Moser se utiliza como el dispositivo central de establecimiento de la verdad en la reducción. [8]
El huso de Moser también puede utilizarse para demostrar un resultado de la teoría euclidiana de Ramsey : si T es cualquier triángulo en el plano, y los puntos del plano son bicolores, blanco y negro, entonces hay una traducida negra de T o un par de puntos blancos a una distancia unitaria entre sí. Pues, sea M una incrustación a una distancia unitaria del huso de Moser, y sea M + T la suma de Minkowski de M y T. Si M + T no tiene un par de distancias unitarias blancas, entonces cada una de las tres copias del huso 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 conjunto independiente más grande en el huso de Moser tiene un tamaño de dos. Por lo tanto, entre los siete vértices del huso de Moser, hay como máximo seis que tienen una copia blanca en M + T , por lo que debe haber uno de los siete vértices cuyas copias sean todas negras. Pero entonces las tres copias de este vértice forman una traducida de T. [7]