De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Este artículo trata sobre un término en teoría de grafos. Para otros usos, consulte Snark (desambiguación) .
El gráfico de Petersen es el snark más pequeño.
La flor snark J 5 es una de las seis snarks en 20 vértices.

En el campo matemático de la teoría de grafos , un snark es un grafo cúbico simple , conectado y sin puentes con un índice cromático igual a 4. En otras palabras, es un grafo en el que cada vértice tiene tres vecinos, la conectividad es redundante, por lo que eliminar no un borde dividiría el gráfico y los bordes no se pueden colorear con solo tres colores sin que dos bordes del mismo color se encuentren en un punto. (Según el teorema de Vizing , el índice cromático de un gráfico cúbico es 3 o 4.) Para evitar casos triviales, los snarks a menudo se limitan a tener una circunferencia de al menos 5.

Miroslav Chladný , escribiendo en The Electronic Journal of Combinatorics , afirma que

En el estudio de varios problemas importantes y difíciles de la teoría de grafos (como la conjetura de la doble cobertura del ciclo y la conjetura de los 5 flujos ), uno se encuentra con una variedad interesante pero algo misteriosa de gráficos llamados 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]

Historia [ editar ]

Peter Guthrie 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 plano . [2] El primer snark conocido fue el grafo de Petersen , descubierto en 1898. En 1946, el matemático croata Danilo Blanuša descubrió dos snarks más, ambos en 18 vértices, ahora llamados Blanuša snarks . [3] El cuarto snark conocido fue encontrado dos años más tarde por WT Tutte bajo el seudónimo de Blanche Descartes ; tiene orden 210. [4] [5] En 1973, George Szekeresencontró el quinto snark conocido: el snark de Szekeres . [6] En 1975, Rufus Isaacs generalizó el método de Blanuša para construir dos familias infinitas de snarks: la flor snark y la BDS o Blanuša-Descartes-Szekeres snark , una familia que incluye los dos Blanuša snarks, el Descartes snark y el Szekeres snark. [7] Isaacs también descubrió un snark de 30 vértices que no pertenece a la familia BDS y que no es un snark de flores: el snark de doble estrella .

Los snarks fueron nombrados 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 . [8]

Propiedades [ editar ]

Todos los snarks son no hamiltonianos y muchos snarks conocidos son 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 de 3 bordes. [9] [10]

Se ha demostrado que el número de snarks para un número par dado de vértices está acotado a continuación por una función exponencial. [11] (Al ser gráficas cúbicas, todos los snarks deben tener un número par de vértices). La secuencia OEIS A130315 contiene el número de snarks no triviales de 2n vértices para valores pequeños de n .

La conjetura de la cubierta doble del ciclo postula que en cada gráfico sin puentes se puede encontrar una colección de ciclos que cubren cada borde dos veces, o de manera equivalente, que el gráfico se puede incrustar en una superficie de tal manera que todas las caras de la incrustación sean ciclos simples. Los snarks forman el caso difícil para esta conjetura: si es cierto para snarks, lo es para todos los gráficos. [12] A este respecto, Branko Grünbaum conjeturaba que no era posible incrustar ningún snark en una superficie de tal manera que todas las caras fueran ciclos simples y que cada dos caras fueran disjuntas o compartieran un solo borde; sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum. [13] [14] [15]

El trabajo de Peter Tait estableció que el teorema de los 4 colores es verdadero si y solo cada snark es no plano. Por tanto, todos los snarks no son planos.

Conjetura de Snark [ editar ]

WT Tutte conjeturó que cada snark tiene el gráfico de Petersen como menor . Es decir, conjeturó que el snark más pequeño, el gráfico de Petersen, puede formarse a partir de cualquier otro snark contrayendo algunos bordes y eliminando otros. De manera equivalente (debido a que el gráfico de Petersen tiene un grado máximo de tres), cada snark tiene un subgráfico que se puede formar a partir del gráfico de Petersen subdividiendo algunos de sus bordes . Esta conjetura es una forma reforzada del teorema de los cuatro colores , porque cualquier gráfico que contenga el gráfico de Petersen como menor debe ser no plano. En 1999, Neil Robertson , Daniel P. Sanders , Paul Seymour y Robin Thomasanunció una prueba de esta conjetura. [16] A partir de 2020 , su prueba permanece en gran parte inédita. [17] Consulte la conjetura de Hadwiger para ver otros problemas y resultados que relacionan el color de la gráfica con los menores de la gráfica.

Tutte también conjeturó una generalización a gráficos arbitrarios: cada gráfico sin puente sin menor de Petersen tiene un flujo 4 de cero en ninguna parte . Es decir, a los bordes del gráfico se les puede asignar una dirección y un número del conjunto {1, 2, 3}, de modo 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 mostró Tutte, para las gráficas cúbicas, tal asignación existe si y solo si los bordes se pueden colorear con tres colores, por lo que la conjetura se deriva del teorema de snark en este caso. Sin embargo, esta conjetura permanece abierta para gráficos no cúbicos. [18]

Lista de snarks [ editar ]

  • Gráfico de Petersen (10 vértices; descubierto en 1898)
  • Gráfico de Tietze (12 vértices pero con una circunferencia de 3, generalmente no se considera un snark)
  • Blanuša snarks (dos con 18 vértices; descubierto en 1946)
  • Snark de doble estrella (30 vértices)
  • Szekeres snark (50 vértices; descubierto en 1973)
  • Watkins snark (50 vértices; descubierto en 1989)
  • Descartes snark (210 vértices; descubierto por Bill Tutte en 1948)
  • Flower snark (familia infinita en 20, 28, 36, 44 ... vértices; descubierto en 1975)

Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund y Klas Markström generaron una lista de todos los snarks hasta 36 vértices, excepto aquellos con 36 vértices y circunferencia 4 en 2012. [19]

Referencias [ editar ]

  1. ^ Chladný, Miroslav; Škoviera, Martin (2010), "Factorización de snarks", The Electronic Journal of Combinatorics , 17 : R32, doi : 10.37236 / 304 .
  2. ↑ Tait, Peter Guthrie (1880), "Observaciones sobre la coloración de los mapas", Actas de la Royal Society of Edinburgh , 10 : 729, doi : 10.1017 / S0370164600044643 CS1 maint: parámetro desalentado ( enlace )
  3. ^ Blanuša, Danilo (1946), "Problema četiriju boja", Glasnik Mat. Fiz. Astr. , Serie II, 1 : 31–42
  4. ^ Blanche Descartes, Network-coloreaciones, The Mathematical Gazette (Londres) 32, 67-69, 1948.
  5. ^ Martin Gardner, Las últimas recreaciones: hidras, huevos y otras mistificaciones matemáticas, Springer, 2007, ISBN 0-387-25827-2 , ISBN 978-0-387-25827-0  
  6. ^ Szekeres, George (1973), "Descomposiciones poliédricas de gráficos cúbicos", Boletín de la Sociedad Matemática Australiana , 8 (3): 367–387, doi : 10.1017 / S0004972700042660 . CS1 maint: parámetro desalentado ( enlace )
  7. ^ Isaacs, R. (1975), "Familias infinitas de gráficos trivalentes no triviales que no son coloreables por Tait", American Mathematical Monthly , 82 (3): 221-239, doi : 10.2307 / 2319844 , JSTOR 2319844 
  8. ^ Gardner, Martin (1976), " Juegos matemáticos ", Scientific American , 4 (234): 126-130, Bibcode : 1976SciAm.234d.126G , doi : 10.1038 / scientificamerican0476-126 CS1 maint: parámetro desalentado ( enlace )
  9. ^ Steffen, E. (1998), "Clasificación y caracterizaciones de snarks", Matemáticas discretas , 188 (1-3): 183-203, doi : 10.1016 / S0012-365X (97) 00255-0 , MR 1630478 
  10. ^ Steffen, E. (2001), "Sobre snarks bicríticos", Matemáticas. Eslovaca , 51 (2): 141-150, MR 1841443 
  11. ↑ Skupień, Zdzisław (2007). "Exponencialmente muchos sarcasmos hipohamiltonianos". Notas electrónicas en matemáticas discretas . 6º Simposio Internacional Checo-Eslovaco sobre Combinatoria, Teoría de Grafos, Algoritmos y Aplicaciones. 28 . págs. 417–424. doi : 10.1016 / j.endm.2007.01.059 . CS1 maint: parámetro desalentado ( enlace )
  12. ^ Jaeger, François (1985), "Un estudio de la conjetura de la cubierta doble del ciclo", Annals of Discrete Mathematics 27 - Cycles in Graphs , North-Holland Mathematics Studies, 27 , pp. 1-12, doi : 10.1016 / S0304-0208 (08) 72993-1 , ISBN 978-0-444-87803-8.
  13. ^ Kochol, Martin (1996), "Snarks sin ciclos pequeños", Revista de teoría combinatoria, Serie B , 67 , págs. 34-47.
  14. ^ Kochol, Martin (2009), "Gráficos coloreables de 3 bordes no regulares con incrustaciones poliédricas en superficies orientables", Graph Drawing 2008, Editores: IG Tollis, M. Patrignani , Lecture Notes in Computer Science, 5417 , págs. 319–323.
  15. ^ Kochol, Martin (2009), "Inserciones poliédricas de snarks en superficies orientables", Actas de la American Mathematical Society , 137 , págs. 1613-1619.
  16. ^ Thomas, Robin (1999). "Teoremas menores excluidos recientes para gráficos". Encuestas en combinatoria, 1999 (PDF) . Prensa de la Universidad de Cambridge. págs. 201–222. CS1 maint: parámetro desalentado ( enlace )
  17. ^ belcastro, sarah-marie (2012), "La continua saga de snarks", The College Mathematics Journal , 43 (1): 82–87, doi : 10.4169 / college.math.j.43.1.082 , MR 2875562 , S2CID 118189042  .
  18. ^ "Conjetura de 4 flujos" ., Open Problem Garden.
  19. ^ Brinkmann, Gunnar; Goedgebeur, Jan; Hägglund, Jonas; Markström, Klas (2012), "Generación y propiedades de Snarks", Journal of Combinatorial Theory, Serie B , 103 (4): 468–488, arXiv : 1206.6690 , doi : 10.1016 / j.jctb.2013.05.001 , S2CID 15284747 

Enlaces externos [ editar ]

  • Weisstein, Eric W. "Snark" . MathWorld .
  • Alen Orbanić, Tomaž Pisanski, Milan Randić y Brigite Servatius, " Blanuša Double ", Mathematical Communications 9 (2004), 91-103.