Sarcasmo (teoría de grafos)

En el campo matemático de la teoría de grafos , un snark es un grafo no dirigido con exactamente tres aristas por vértice, cuyas aristas no pueden colorearse con solo tres colores. Para evitar casos triviales, los snarks suelen estar sujetos a requisitos adicionales en cuanto a su conectividad y la longitud de sus ciclos . Existen infinitos snarks.

Una de las formas equivalentes del teorema de los cuatro colores es que todo snark es un grafo no planar . La investigación sobre los snarks se originó en el trabajo de Peter G. Tait sobre el teorema de los cuatro colores en 1880, pero su nombre es mucho más reciente, dado por Martin Gardner en 1976. Más allá de la coloración, los snarks también tienen conexiones con otros problemas difíciles en la teoría de grafos: escribiendo en el Electronic Journal of Combinatorics , Miroslav Chladný y Martin Škoviera afirman que

En el estudio de diversos problemas importantes y difíciles de la teoría de grafos (como la conjetura de la doble cobertura cíclica y la conjetura del flujo 5 ), uno se encuentra con una variedad de grafos interesante pero algo misteriosa llamada snarks. A pesar de su definición simple... y de más de un siglo de investigación, sus propiedades y estructura son en gran parte desconocidas. ^{[ 1 ]}

Además de los problemas que mencionan, la conjetura de snark de WT Tutte se refiere a la existencia de grafos de Petersen como menores de grafos de snarks; su demostración se anunció hace tiempo pero sigue sin publicarse, y resolvería un caso especial de la existencia de 4-flujos cero en ninguna parte .

Los snarks fueron denominados así por el matemático estadounidense Martin Gardner en 1976, en honor al misterioso y esquivo objeto del poema La caza del snark de Lewis Carroll . ^{[ 2 ]} Sin embargo, el estudio de esta clase de grafos es significativamente anterior a su nombre. Peter G. Tait inició el estudio de los snarks en 1880, cuando demostró que el teorema de los cuatro colores es equivalente a la afirmación de que ningún snark es planar . ^{[ 3 ]} El primer grafo conocido como snark fue el grafo de Petersen ; Julius Petersen demostró que era un snark en 1898, ^{[ 4 ]} aunque Alfred Kempe ya lo había estudiado con un propósito diferente en 1886. ^{[ 5 ]}

Los siguientes cuatro sarcasmos conocidos fueron

• los snarks de Blanuša (dos con 18 vértices), descubiertos por Danilo Blanuša en 1946, ^{[ 6 ]}
• el snark de Descartes (210 vértices), descubierto por Bill Tutte en 1948, ^{[ 7 ]} y
• el snark de Szekeres (50 vértices), descubierto por George Szekeres en 1973. ^{[ 8 ]}

En 1975, Rufus Isaacs generalizó el método de Blanuša para construir dos familias infinitas de snarks: los snarks de flores y los snarks de Blanuša–Descartes–Szekeres, una familia que incluye los dos snarks de Blanuša, el snark de Descartes y el snark de Szekeres. Isaacs también descubrió un snark de 30 vértices que no pertenece a la familia de Blanuša–Descartes–Szekeres y que no es un snark de flores: el snark de doble estrella . ^{[ 9 ]} Otra familia infinita, los snarks de Loupekine , fue publicada por Isaacs en 1976, atribuida a F. Loupekine. Incluye dos snarks de 22 vértices derivados del grafo de Petersen. ^{[ 10 ]} El snark de Watkins de 50 vértices fue descubierto en 1989. ^{[ 11 ]}

Otro grafo cúbico notable que no se puede colorear con tres aristas es el grafo de Tietze , con 12 vértices; como descubrió Heinrich Franz Friedrich Tietze en 1910, forma el límite de una subdivisión de la cinta de Möbius que requiere seis colores. ^{[ 12 ]} Sin embargo, debido a que contiene un triángulo, generalmente no se considera un snark. Según las definiciones estrictas de snarks, los snarks más pequeños son el grafo de Petersen y el snark de Blanuša, seguidos de seis snarks diferentes de 20 vértices. ^{[ 13 ]}

Una lista de todos los snarks de hasta 36 vértices (según una definición estricta) y de hasta 34 vértices (según una definición más débil) fue generada por Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund y Klas Markström en 2012. ^{[ 13 ]} El número de snarks para un número par de vértices dado crece al menos exponencialmente en el número de vértices. ^{[ 14 ]} (Debido a que tienen vértices de grado impar, todos los snarks deben tener un número par de vértices por el lema del apretón de manos ). ^{[ 15 ]} La secuencia OEIS A130315 contiene el número de snarks no triviales de${\displaystyle 2n}$vértices para valores pequeños de${\displaystyle n}$. ^{[ 16 ]}

La definición precisa de snarks varía entre autores, ^{[ 13 ] [ 9 ]} pero generalmente se refiere a grafos cúbicos (con exactamente tres aristas en cada vértice) cuyas aristas no pueden colorearse con solo tres colores. Según el teorema de Vizing , el número de colores necesarios para las aristas de un grafo cúbico es tres (grafos de "clase uno") o cuatro (grafos de "clase dos"), por lo que los snarks son grafos cúbicos de clase dos. Sin embargo, para evitar casos en los que un snark sea de clase dos por razones triviales, o se construya de forma trivial a partir de grafos más pequeños, a menudo se imponen restricciones adicionales sobre la conectividad y la longitud de los ciclos. En particular:

• Si un grafo cúbico tiene un puente , una arista cuya eliminación lo desconectaría, entonces no puede ser de clase uno. Según el lema del apretón de manos , los subgrafos a cada lado del puente tienen un número impar de vértices cada uno. Cualquiera que sea el color elegido para el puente, su número impar de vértices impide que estos subgrafos estén cubiertos por ciclos que alternen entre los otros dos colores, como sería necesario en una coloración de 3 aristas. Por esta razón, generalmente se requiere que los snarks no tengan puente. ^{[ 2 ] [ 9 ]}
• Un bucle (una arista que conecta un vértice consigo mismo) no puede colorearse sin que el mismo color aparezca dos veces en ese vértice, lo que viola los requisitos habituales para la coloración de aristas de grafos. Además, un ciclo formado por dos vértices conectados por dos aristas siempre puede reemplazarse por una sola arista que conecte sus otros dos vecinos, simplificando el grafo sin cambiar su capacidad de coloración de tres aristas. Por estas razones, los snarks generalmente se limitan a grafos simples , grafos sin bucles ni adyacencias múltiples. ^{[ 9 ]}
• Si un grafo contiene un triángulo, puede simplificarse nuevamente sin cambiar su colorabilidad de tres aristas, contrayendo los tres vértices del triángulo en un solo vértice. Por lo tanto, muchas definiciones de snarks prohíben los triángulos. ^{[ 9 ]} Sin embargo, aunque este requisito también se mencionó en el trabajo de Gardner que dio el nombre de "snark" a estos grafos, Gardner incluye el grafo de Tietze , que contiene un triángulo, como un snark. ^{[ 2 ]}
• Si un grafo contiene un ciclo de cuatro vértices, puede simplificarse de dos maneras distintas eliminando dos aristas opuestas del ciclo y reemplazando los caminos resultantes de vértices de grado dos por aristas simples. Tiene una coloración de tres aristas si y solo si al menos una de estas simplificaciones la tiene. Por lo tanto, Isaacs requiere un grafo cúbico de clase dos "no trivial" para evitar ciclos de cuatro vértices, ^{[ 9 ]} y otros autores han seguido su ejemplo prohibiendo estos ciclos. ^{[ 13 ]} El requisito de que un snark evite ciclos de longitud cuatro o menos puede resumirse afirmando que la circunferencia de estos grafos, la longitud de sus ciclos más cortos, es al menos cinco.
• Más concretamente, la definición utilizada por Brinkmann et al. (2012) exige que los snarks sean cíclicamente 4-aristas-conectados. Esto significa que no puede haber un subconjunto de tres o menos aristas, cuya eliminación desconectaría el grafo en dos subgrafos, cada uno de los cuales tiene al menos un ciclo. Brinkmann et al. definen un snark como un grafo cúbico y cíclicamente 4-aristas-conectado de circunferencia cinco o más y clase dos; definen un "snark débil" para permitir una circunferencia cuatro. ^{[ 13 ]}

Aunque estas definiciones solo consideran restricciones en la circunferencia hasta cinco, existen snarks con circunferencias arbitrariamente grandes. ^{[ 17 ]}

El trabajo de Peter G. Tait estableció que el teorema de los cuatro colores es verdadero si y solo si todo snark es no planar. ^{[ 3 ]} Este teorema afirma que todo grafo planar tiene una coloración de sus vértices con cuatro colores, pero Tait demostró cómo convertir las coloraciones de 4 vértices de grafos planares maximales en coloraciones de 3 aristas de sus grafos duales , que son cúbicos y planares, y viceversa. Por lo tanto, un snark planar sería necesariamente dual a un contraejemplo del teorema de los cuatro colores. Así, la demostración posterior del teorema de los cuatro colores ^{[ 18 ]} también demuestra que todos los snarks son no planares. ^{[ 19 ]}

Todos los snarks son no hamiltonianos : cuando un grafo cúbico tiene un ciclo hamiltoniano, siempre es posible 3-colorear sus aristas, usando dos colores alternativamente para el ciclo y el tercer color para las aristas restantes. Sin embargo, muchos snarks conocidos están cerca de ser hamiltonianos, en el sentido de que son grafos hipohamiltonianos : la eliminación de cualquier vértice deja un subgrafo hamiltoniano. Un snark hipohamiltoniano debe ser bicrítico : la eliminación de dos vértices cualesquiera deja un subgrafo coloreable con tres aristas. ^{[ 20 ]} La imprecisión de un grafo cúbico se define como el número mínimo de ciclos impares, en cualquier sistema de ciclos que cubre cada vértice una vez (un 2-factor ). Por la misma razón que no tienen ciclos hamiltonianos, los snarks tienen imprecisión positiva: un 2-factor completamente par llevaría a una coloración de 3 aristas, y viceversa. Es posible construir familias infinitas de snarks cuya rareza crece linealmente con su número de vértices. ^{[ 15 ]}

La conjetura de la doble cobertura cíclica postula que en todo grafo sin puentes se puede encontrar una colección de ciclos que cubren cada arista dos veces, o equivalentemente, que el grafo puede incrustarse en una superficie de tal manera que todas las caras de la incrustación sean ciclos simples. Cuando un grafo cúbico tiene una coloración de 3 aristas, tiene una doble cobertura cíclica que consiste en los ciclos formados por cada par de colores. Por lo tanto, entre los grafos cúbicos, los snarks son los únicos contraejemplos posibles. De manera más general, los snarks forman el caso difícil para esta conjetura: si es cierta para los snarks, es cierta para todos los grafos. ^{[ 21 ]} En este sentido, Branko Grünbaum conjeturó que ningún snark podría incrustarse en una superficie de tal manera que todas las caras sean ciclos simples y que cada dos caras sean disjuntas o compartan solo una arista; si algún snark tuviera tal incrustación, sus caras formarían una doble cobertura cíclica. Sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum. ^{[ 22 ]}

Determinar si un grafo cúbico cíclicamente 5-conectado dado es 3-arista-coloreable es NP-completo . Por lo tanto, determinar si un grafo es un snark es co-NP-completo . ^{[ 23 ]}

WT Tutte conjeturó que todo snark tiene el grafo de Petersen como menor . Es decir, conjeturó que el snark más pequeño, el grafo de Petersen, puede formarse a partir de cualquier otro snark contrayendo algunas aristas y eliminando otras. De forma equivalente (porque el grafo de Petersen tiene grado máximo tres), todo snark tiene un subgrafo que puede formarse a partir del grafo de Petersen subdividiendo algunas de sus aristas . Esta conjetura es una forma reforzada del teorema de los cuatro colores , porque cualquier grafo que contenga el grafo de Petersen como menor debe ser no planar. En 1999, Neil Robertson , Daniel P. Sanders , Paul Seymour y Robin Thomas anunciaron una demostración de esta conjetura. ^{[ 24 ]} Se han publicado pasos hacia este resultado en 2016 y 2019, ^{[ 25 ] [ 26 ]} pero la demostración completa permanece inédita. ^{[ 19 ]} Véase la conjetura de Hadwiger para otros problemas y resultados que relacionan la coloración de grafos con los menores de grafos.

Tutte también conjeturó una generalización a grafos arbitrarios: todo grafo sin puentes y sin menor de Petersen tiene un 4-flujo sin ceros en ninguna parte . Es decir, a las aristas del grafo se les puede asignar una dirección y un número del conjunto {1, 2, 3}, de tal manera que la suma de los números entrantes menos la suma de los números salientes en cada vértice sea divisible por cuatro. Como demostró Tutte, para grafos cúbicos dicha asignación existe si y solo si las aristas se pueden colorear con tres colores, por lo que la conjetura se derivaría de la conjetura de Snark en este caso. Sin embargo, demostrar la conjetura de Snark no resolvería la cuestión de la existencia de 4-flujos para grafos no cúbicos. ^{[ 27 ]}

• Weisstein, Eric W. , "Snark" , MathWorld
• Catálogo de comentarios sarcásticos en la Casa de los Gráficos.