Problema graficului cu 99 de vârfuri a lui Conway

Problema grafului cu 99 de vârfuri a lui Conway este o problemă nerezolvată care întreabă dacă există un graf nedirecționat cu 99 de vârfuri în care fiecare două vârfuri adiacente au exact un vecin comun și în care două vârfuri neadiacente au exact doi vecini comuni. În mod echivalent, orice muchie trebuie să facă parte dintr-un triunghi unic și orice pereche de vârfuri neadiacente trebuie să fie pe diagonala unui ciclu unic de 4. John Horton Conway a anunțat un premiu de 1.000 de dolari pentru cine a rezolvat această problemă [1] .

Proprietăți

Dacă există un astfel de grafic, va trebui să fie un grafic local liniar puternic regulat cu parametri (99,14,1,2). Primul, al treilea și al patrulea parametri codifică declarația problemei — graficul trebuie să aibă 99 de vârfuri, fiecare pereche de vârfuri adiacente trebuie să aibă 1 vecin comun și orice vârfuri neadiacente trebuie să aibă 2 vecini comuni. Al doilea parametru înseamnă că graficul este un grafic obișnuit cu 14 muchii pe vârf [2] .

Dacă acest grafic există, nu are nicio simetrie de ordinul 11, ceea ce înseamnă că simetriile sale nu pot duce niciun vârf la niciun alt vârf [3] . Există și alte restricții asupra posibilelor grupuri de simetrie [4] .

Istorie

Posibila existență a unui graf cu astfel de parametri a fost sugerată deja în 1969 de Norman L. Biggs [5] , iar Conway [3] [6] [7] [8] a pus, printre altele, o problemă deschisă a existenței . Conway lucrează el însuși la această problemă din 1975 [6] , dar a anunțat un premiu în 2014 oricui rezolvă problema, ca parte a unui set de probleme prezentate la Conferința DIMACS privind problemele esențiale de identificare a secvenței întregi. Alte probleme din acest set includ conjectura trekle , cea mai mică distanță de seturi Danzer și întrebarea cine câștigă după mutarea 16 în jocul de monede [1] .

Grafice înrudite

Mai general, există doar cinci combinații posibile de parametri pentru care poate exista un grafic puternic regulat, cu proprietatea că fiecare muchie aparține unui triunghi unic și fiecare non-margine (muchia lipsă a două vârfuri neadiacente) formează o diagonală a unei patrulater unic. Știm doar că graficele există cu două dintre aceste cinci combinații. Cele două grafice sunt graficul Paley cu nouă vârfuri (graficul duoprism 3-3 ) cu parametri (9,4,1,2) și graficul Berlekamp-van Lint-Seidel cu parametri (243,22,1,2). Problema cu 99 de graf se întreabă despre cea mai mică dintre aceste cinci combinații de parametri pentru care existența unui graf este necunoscută [4] .

Note

1. ↑ 12 John H. Conway . Cinci probleme de 1.000 USD (Actualizare 2017) . — Enciclopedia on-line a secvențelor întregi .
2. ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Nu problema lui Conway cu 99 de grafice. - 2017. - arXiv : 1707.08047 .
3. ↑ 1 2 Wilbrink HA Pe graficul (99,14,1,2) puternic regulat // Lucrări dedicate lui JJ Seidel / de Doelder PJ, de Graaf J., van Lint JH. — Universitatea de Tehnologie Eindhoven. - T. 84-WSK-03. — S. 342–355. — (Raport EUT).
4. ↑ 1 2 Makhnev AA, Minakova IM,. Despre automorfisme ale graficelor puternic regulate cu parametri ,  // Matematică discretă și aplicații. - 2004. - ianuarie ( vol. 14 , numărul 2 ). - doi : 10.1515/156939204872374 .
5. ↑ Norman L. Biggs. Grupuri finite de automorfisme: curs dat la Universitatea din Southampton, octombrie–decembrie 1969 . - Londra și New York: Cambridge University Press, 1971. - V. 6. - P. 111. - (London Mathematical Society Lecture Note Series).
6. ↑ 12 Richard K. Guy . Probleme // Proceedings of a Conference ținut la Michigan State University, East Lansing, Michigan, 17–19 iunie 1974 / Kelly LM. - Berlin, New York: Springer-Verlag, 1975. - T. 490. - S. 233-244. — (Note de curs la matematică). - doi : 10.1007/BFb0081147 . . Vezi problema 7 (JJ Seidel), pp. 237–238.
7. ↑ Brouwer AE, Neumaier A. O remarcă asupra spațiilor liniare parțiale de circumferință 5 cu o aplicație la grafice puternic regulate // Combinatorică. - 1988. - T. 8 , nr. 1 . — p. 57–61 . - doi : 10.1007/BF02122552 .
8. ↑ Peter J. Cameron. Combinatorică: subiecte, tehnici, algoritmi . - Cambridge: Cambridge University Press, 1994. - P. 331. - ISBN 0-521-45133-7 .