Snark (teoria dei grafi)
Nel campo matematico della teoria dei grafi, uno snark è un grafo cubico connesso, privo di ponti, con indice cromatico uguale a 4. In altre parole, è un grafo in cui ogni vertice ha tre vicini, e gli spigoli non possono essere colorati solo con tre colori senza che due spigoli dello stesso colore si incontrino in un punto. (Per il teorema di Vizing, l'indice cromatico di un grafo cubico è 3 o 4.) Per evitare casi banali, gli snark sono spesso limitati ai grafi aventi un calibro almeno di 5.
Scrivendo su The Electronic Journal of Combinatorics, Miroslav Chladný afferma che
«Nello studio di vari importanti e difficili problemi della teoria dei grafi (come la congettura sulla copertura del doppio ciclo e la congettura sul 5-flusso), si incontra una varietà di grafi interessante ma in un certo modo misteriosa chiamati snark. Malgrado la loro semplice definizione... e un'indagine lunga oltre un secolo, le loro proprietà e la loro struttura sono in gran parte ignote.[1]»
Storia
[modifica | modifica wikitesto]P. G. Tait iniziò lo studio degli snark nel 1880, quando dimostrò che il teorema dei quattro colori è equivalente all'enunciato che nessuno snark è planare.[2] Il primo snark conosciuto fu il grafo di Petersen, scoperto nel 1898. Nel 1946, il matematico croato Danilo Blanuša scoprì altri due snark, entrambi su 18 vertici, ora chiamati snark di Blanuša.[3] Il quarto snark conosciuto fu trovato due anni dopo da Bill Tutte, sotto lo pseudonimo Blanche Descartes, ed era un grafo di ordine 210.[4][5] Nel 1973, George Szekeres trovò il quinto snark conosciuto — lo snark di Szekeres.[6] Nel 1975, Rufus Isaacs generalizzò il metodo di Blanuša per costruire due famiglie infinite di snark: lo snark a fiore e gli snark di Blanuša-Descartes-Szekeres (Blanuša-Descartes-Szekeres snark, BDS), una famiglia che comprende i due snark di Blanuša, lo snark di Descartes e lo snark di Szekeres.[7] Isaacs scoprì anche uno snark con 30 vertici che non appartiene alla famiglia BDS e che non è uno snark a fiore: lo snark a doppia stella.
Gli snark furono chiamati così dal matematico americano Martin Gardner nel 1976, dal nome del misterioso ed elusivo oggetto del poema La caccia allo Snark (1874) di Lewis Carroll.[8]
Proprietà
[modifica | modifica wikitesto]Tutti gli snark sono non hamiltoniani, e molti snark conosciuti sono ipohamiltoniani: l'eliminazione di un singolo vertice qualsiasi lascia un sottografo hamiltoniano. Uno snark ipohamiltoniano deve essere bicritico: l'eliminazione di due vertici qualsiasi lascia un sottografo 3-colorabile sui vertici.[9][10]
È stato mostrato che il numero di snark per un dato numero pari di vertici è limitato in basso mediante una funzione esponenziale.[11] (Essendo grafi cubici, tutti gli snark devono un numero pari di vertici.) La sequenza OEIS A130315 contiene il numero di snark non banali di 2n vertici per piccoli valori di n.
La congettura sulla copertura del doppio ciclo postula che in ogni grafo privo di ponti si può trovare una collezione di cicli che copre ogni vertice due volte, o in modo equivalente che il grafo può essere incorporato su una superficie in modo tale che tutte le facce dell'incorporazione siano cicli semplici. Gli snark rappresentano il caso difficile per questa congettura: se è vero per gli snark, è vero per tutti i grafi.[12] In questa connessione, Branko Grünbaum congetturò che non era possibile incorporare alcuno snark su una superficie in modo tale che tutte le facce siano cicli semplici e che ogni due facce o sono disgiunte o condividono solo un unico spigolo; tuttavia, un controesempio per la congettura di Grünbaum fu trovato da Martin Kochol.[13][14][15]
Teorema degli snark
[modifica | modifica wikitesto]W. T. Tutte congetturò che ogni snark ha il grafo di Petersen come minore. Cioè, congetturò che il più piccolo snark, il grafo di Petersen, può essere formato da un qualsiasi altro snark contraendo alcuni spigoli e cancellandone altri. Equivalentemente (poiché il grafo di Petersen ha grado massimo tre) ogni snark ha un sottografo che può essere formato dal grafo di Petersen mediante suddividendo alcuni dei suoi spigoli. Questa congettura è una forma rafforzata del teorema dei quattro colori, perché qualsiasi grafo contenente il grafo di Petersen come minore deve essere non planare. Nel 1999, Robertson, Sanders, Seymour e Thomas annunciarono una dimostrazione di questa congettura.[16] Fino al 2012 questa dimostrazione restava in gran parte non pubblicata.[17] Vedi la congettura di Hadwiger per altri problemi e risultati che collegano la colorazione dei grafi ai minori dei grafi.
Tutte congetturò anche una generalizzazione del teorema degli snark ai grafi arbitrari: ogni grafo privo di ponti senza minori di Petersen ha un 4-flusso zero in nessun luogo. Ossia, agli spigoli del grafo possono essere assegnati una direzione e un numero dall'insieme {1, 2, 3}, tale che la somma dei numeri entranti meno la somma dei numeri uscenti in ogni vertice è divisibile per quattro. Come mostrò Tutte, per i grafi cubici tale assegnazione esiste se e solo se gli spigoli possono essere colorati da tre colori, così in questo caso la congettura deriva dal teorema degli snark. Tuttavia, quest congettura rimane aperta per i grafi che non devono essere cubici.[18]
Lista di snark
[modifica | modifica wikitesto]- Grafo di Petersen (10 vertici; scoperto nel 1898)
- Grafo di Tietze (12 vertici ma con un calibro di 3, generalmente non considerato come uno snark)
- Snark di Blanuša (due con 18 vertici; scoperti nel 1946)
- Snark di Descartes (210 vertici; scoperto da Bill Tutte nel 1948)
- Snark a doppia stella (30 vertici)
- Snark di Szekeres (50 vertici; scoperto nel 1973)
- Snark di Watkins (50 vertici; scoperto nel 1989)
- Snark a fiore (famiglia infinita su 20, 28, 36, 44... vertici; scoperto nel 1975)
Una lista di tutti gli snark fino a 36 vertici, eccetto quelli con 36 vertici e calibro 4, fu creata da Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund e Klas Markström nel 2012.[19]
Note
[modifica | modifica wikitesto]- ^ Miroslav Chladný, Martin Škoviera, Factorisation of snarks, in Electronic Journal of Combinatorics, vol. 17, 2010, R32.
- ^ P. G. Tait, Remarks on the colourings of maps, in Proc. R. Soc. Edinburgh, vol. 10, 1880, 729.
- ^ Danilo Blanuša, Problem četiriju boja, in Glasnik Mat. Fiz. Astr. Ser II, vol. 1, 1946, 31-42.
- ^ Blanche Descartes, Network-colourings, «The Mathematical Gazette» (Londra), 32, 67-69, 1948.
- ^ Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ISBN 0-387-25827-2, ISBN 978-0-387-25827-0
- ^ Szekeres, G., Polyhedral decompositions of cubic graphs, in Bull. Austral. Math. Soc., vol. 8, n. 3, 1973, 367-387, DOI:10.1017/S0004972700042660.
- ^ R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait-colorable, in American Mathematical Monthly, vol. 82, n. 3, 1975, 221-239, DOI:10.2307/2319844, JSTOR 2319844.
- ^ Martin Gardner, Mathematical Games, in Scientific American, vol. 4, n. 234, 1976, 126-130. Il termine, coniato da Carroll, deriva probabilmente dalla fusione delle parole snake ("serpente") e shark ("squalo").
- ^ E. Steffen, Classification and characterizations of snarks, in Discrete Mathematics, vol. 188, n. 1-3, 1998, 183-203, DOI:10.1016/S0012-365X(97)00255-0, MR 1630478.
- ^ E. Steffen, On bicritical snarks, in Math. Slovaca, vol. 51, n. 2, 2001, 141-150, MR 1841443.
- ^ Z. Skupień, Exponentially many hypohamiltonian snarks, in 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electronic Notes in Discrete Mathematics, vol. 28, 2007, 417-424, DOI:10.1016/j.endm.2007.01.059.
- ^ F. Jaeger, A survey of the cycle double cover conjecture, in Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, 1985, 1-12, DOI:10.1016/S0304-0208(08)72993-1, ISBN 978-0-444-87803-8.
- ^ Martin Kochol, Snarks without small cycles, in Journal of Combinatorial Theory, Series B, vol. 67, 1996, 34-47.
- ^ Martin Kochol, 3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces, in Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani, Lecture Notes in Computer Science, vol. 5417, 2009, 319-323.
- ^ Martin Kochol, Polyhedral embeddings of snarks in orientable surfaces, in Proceedings of the American Mathematical Society, vol. 137, 2009, 1613-1619.
- ^ Robin Thomas, Recent Excluded Minor Theorems for Graphs (PDF), in Surveys in Combinatorics, 1999, Cambridge University Press, 1999, pp. 201-222. URL consultato il 20 febbraio 2014 (archiviato dall'url originale il 3 agosto 2016).
- ^ sarah-marie belcastro, The continuing saga of snarks, in The College Mathematics Journal, vol. 43, n. 1, 2012, 82-87, DOI:10.4169/college.math.j.43.1.082, MR 2875562..
- ^ 4-flow conjecture, Open Problem Garden.
- ^ Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström, Generation and Properties of Snarks, 2012.
Altri progetti
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sullo snark
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Snark, su MathWorld, Wolfram Research.
- Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (prestampa). "Blanuša Double". Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia, 2004.
