Snark (teoria graficelor)

Snark în teoria grafurilor  este un graf cubic conex fără punți cu indice cromatic 4. Cu alte cuvinte, este un graf în care fiecare vârf are trei vârfuri învecinate și muchiile nu pot fi colorate doar cu trei culori, astfel încât două muchii ale aceleiași culoarea nu converg la un singur vârf. (După teorema lui Vizing , indicele cromatic al unui grafic cubic este 3 sau 4.) Pentru a evita cazurile banale, graficele cu circumferință mai mică de 5 nu sunt adesea considerate snarks.

Se crede că, în ciuda definiției simple și a istoriei lungi de studiu, proprietățile și structura snark-urilor sunt puțin cunoscute [1] .

Istorie

Peter Tat a devenit pentru prima dată interesat de snarks în 1880, când a demonstrat că teorema celor patru culori este echivalentă cu a spune că niciun snark nu este planar [2] . Primul snark cunoscut a fost contele Petersen , găsit în 1898 . În 1946, matematicianul iugoslav Danilo Blanusha a mai găsit două snark-uri, ambele cu 18 vârfuri, numite Blanusha snarks [3] . Al patrulea snark a fost găsit doi ani mai târziu de Tutt , lucrând sub pseudonimul de Blanche Descartes , și era un grafic de ordinul 210 [4] [5] . În 1973, Szekeresh a găsit al cincilea snark, Snark of Szekeresh . [6] În 1975, Isaacs Rufus a generalizat metoda lui Blalushi de a construi două familii infinite de snarks, Flowers și BDS (Blanushi-Descartes-Szekeres Snark), o familie care include doi snarks Blalushi, Descartes' Snark și Szekeres 'Snark [7] . Isaacs a descoperit, de asemenea, un snark cu 30 de vârfuri care nu aparține familiei BDS și nu este o floare - o stea dublă .

Termenul „snark” a fost inventat de Martin Gardner în 1976 după creatura evazivă snark din The Hunting of the Snark a lui Lewis Carroll [8] .

Proprietăți

Toate snark-urile sunt non-Hamiltoniene , iar multe snark-uri cunoscute sunt hipo -  Hamiltoniene - eliminarea oricărui vârf oferă un subgraf hamiltonian. Snark-urile hipohamiltoniene trebuie să fie bicritice  - eliminarea oricăror două vârfuri dă un subgraf care poate fi colorat cu margini cu 3 culori. [9] [10]

S-a demonstrat că numărul de snark-uri pentru un număr dat de vârfuri este limitat de o funcție exponențială [11] . (Fiind grafice cubice, toate snark-urile trebuie să aibă un număr par de vârfuri.) Secvența OEIS A130315 conține numărul de snark-uri non-triviale cu 2n vârfuri pentru valori mici ale lui n [12] .

Conjectura de acoperire cu ciclu dublu afirmă că în orice grafic fără punte se poate găsi un set de cicluri care acoperă fiecare muchie de două ori sau, echivalent, că graficul poate fi încorporat într-o suprafață în așa fel încât toate fețele să fie cicluri simple. Snark-urile formează un caz dificil pentru această presupunere - dacă este adevărat pentru snarks, este adevărat pentru toate graficele [13] . În această privință, Branko Grünbaum a presupus că este imposibil să se încorporeze vreun snark într-o suprafață în așa fel încât toate fețele să fie cicluri simple și, în plus, oricare două fețe fie să nu aibă muchii comune, fie să aibă o muchie comună. Cu toate acestea, Martin Kohol a găsit un contraexemplu pentru această conjectura Grünbaum [14] [15] [16] .

Teorema snark

Tutt a presupus că orice snark are un grafic Petersen ca minor . Astfel, el a presupus că cel mai mic snark, graficul Petersen, poate fi obținut din orice alt snark prin contractarea unor margini și îndepărtarea altora. Ceea ce este echivalent (deoarece graficul Petersen are un grad maxim de trei) cu afirmația că orice snark conține un subgraf care poate fi obținut din graficul Petersen prin împărțirea unor muchii. Această presupunere este o consolidare a teoremei celor patru culori, deoarece orice grafic care conține graficul Petersen ca minor nu poate fi planar. În 1999, Robertson , Sanders , Seymour și Thomas au anunțat dovada conjecturei [17] , dar din 2012, dovada a fost publicată doar parțial [18] .

Tat a propus, de asemenea, ca o presupunere, o teoremă generalizată snark pentru grafuri arbitrare — orice graf fără punte care nu are un graf Petersen ca minor are un flux de 4 nicăieri zero . Ceea ce înseamnă că muchiile graficului pot primi direcții și pot fi etichetate cu numere din mulțimea {1, 2, 3}, astfel încât suma numerelor de intrare minus suma numerelor de ieșire la fiecare vârf să fie divizibilă cu patru. După cum a arătat Tutt, o astfel de atribuire există pentru graficele cubice dacă și numai dacă marginile pot fi colorate cu trei culori, deci în acest caz conjectura decurge din teorema snark. Cu toate acestea, conjectura rămâne deschisă pentru alte grafice (non-cubice) [19] .

Lista de snarks

O listă cu toate snark-urile cu 36 de vârfuri, excluzând snark-urile cu 36 de vârfuri și circumferința 4, a fost creată de Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund și Claes Markström în 2012 [20] .

Note

  1. ↑ Miroslav Chladny, Martin Skoviera. Factorizarea snark-urilor // The Electronic Journal of Combinatorics . - 2010. - T. 17 . - S. R32 .  — « În studiul diferitelor probleme importante și dificile din teoria grafurilor (cum ar fi conjectura Cycle double cover și 5-Flow Conjecture), se întâlnește o varietate interesantă, dar oarecum misterioasă de grafice numite snarks. În ciuda definiției lor simple... și a investigațiilor de peste un secol, proprietățile și structura lor sunt în mare parte necunoscute. » Traducere: « Când studiem diverse probleme importante și dificile din teoria grafurilor (cum ar fi conjectura de acoperire cu ciclu dublu și conjectura cu 5 fluxuri ), întâlnim grafice interesante, dar oarecum ciudate numite snarks. În ciuda definiției lor simple... și a mai mult de un secol de studiu, proprietățile și structura lor rămân în mare parte necunoscute. »
  2. ↑ P.G. Tait. Observații asupra colorațiilor hărților // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
  3. ↑ Danilo Blanusa. Problem četiriju boja // Glasnik Mat. Fiz. Astr. Ser II. - 1946. - T. 1 . — S. 31–42 .
  4. ↑ Blanche Descartes, Network-colourings, The Mathematical Gazette (Londra) 32, 67-69, 1948.
  5. ↑ Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ISBN 0-387-25827-2 , ISBN 978-0-387-25827-0
  6. ↑ G. Szekeres. Descompuneri poliedrice ale graficelor cubice // Bull. Austral. Matematică. Soc .. - 1973. - V. 8 , nr. 3 . — S. 367–387 . - doi : 10.1017/S0004972700042660 .
  7. ↑ R. Isaacs. Familii infinite de grafice trivalente non-triviale care nu sunt colorabile cu Tait  // American Mathematical Monthly . - 1975. - T. 82 , nr. 3 . — S. 221–239 . - doi : 10.2307/2319844 . — .
  8. ↑ Martin Gardner. Jocuri matematice  // Scientific American . - 1976. - T. 4 , nr. 234 . — S. 126–130 .
  9. ↑ Steffen E. Clasificarea și caracterizarea snark-urilor // Matematică discretă . - 1998. - T. 188 , nr. 1–3 . — S. 183–203 . - doi : 10.1016/S0012-365X(97)00255-0 .
  10. ↑ Steffen E. On bicritical snarks // Math. Slovaca. - 2001. - T. 51 , nr. 2 . — S. 141–150 .
  11. ↑ Z. Skupień. Al 6-lea Simpozion Internațional Ceh-Slovac de combinatorie, teoria grafurilor, algoritmi și aplicații. — Note electronice la matematică discretă. - 2007. - T. 28. - S. 417-424. - doi : 10.1016/j.endm.2007.01.059 .
  12. ↑ Secvența OEIS A130315 _
  13. ↑ F. Jaeger. Analele matematicii discrete 27 - Cicluri în grafice. - 1985. - T. 27. - S. 1–12. — (Studii de matematică din Olanda de Nord). - ISBN 978-0-444-87803-8 . - doi : 10.1016/S0304-0208(08)72993-1 . .
  14. ↑ Martin Kochol. Journal of Combinatorial Theory, Seria B. - 1996. - V. 67 . — p. 34–47 .
  15. ↑ Martin Kochol. Desen grafic 2008, Editori: I. G. Tollis, M. Patrignani. - 2009. - T. 5417 . — S. 319–323 . .
  16. ↑ Martin Kochol. Proceedings of the American Mathematical Society. - 2009. - T. 137 . - S. 1613-1619 .
  17. ↑ Robin Thomas. Surveys in Combinatorics, 1999. Cambridge University Press, 1999. pp. 201–222.
  18. ↑ Sarah-Marie Belcastro. Saga continuă a snark-urilor  // The College Mathematics Journal. - 2012. - T. 43 , nr. 1 . — S. 82–87 . - doi : 10.4169/college.math.j.43.1.082 . . Vezi, de asemenea , conjectura lui Hadwiger și rezultatele legate de colorarea graficului minor.
  19. ↑ 4-flow Conjecture Arhivat 8 februarie 2012 la Wayback Machine , Open Problem Garden.
  20. ↑ Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund și Klas Markström. Generarea și proprietățile Snarks. — 2012.

Link -uri