Conway 99 csúcsos gráffeladata

Megoldatlan problémák a matematikában : Van-e erősen szabályos gráf paraméterekkel (99,14,1,2)?

Conway 99 csúcsos gráfproblémája egy megoldatlan probléma, amely azt kérdezi, hogy létezik-e olyan 99 csúcsos irányítatlan gráf , amelyben minden két szomszédos csúcsnak pontosan egy közös szomszédja van, és amelyben két nem szomszédos csúcsnak pontosan két közös szomszédja van. Ezzel egyenértékűen minden élnek egy egyedi háromszög részének kell lennie, és bármely nem szomszédos csúcspárnak egy egyedi 4 ciklus átlóján kell lennie. John Horton Conway 1000 dolláros díjat hirdetett annak, aki megoldotta ezt a problémát [1] .

Tulajdonságok

Ha létezik ilyen gráf, akkor annak lokálisan lineáris , erősen szabályos gráfnak kell lennie (99,14,1,2) paraméterekkel. Az első, harmadik és negyedik paraméter kódolja a problémakifejezést – a gráfnak 99 csúcsból kell állnia, minden szomszédos csúcspárnak 1 közös szomszédnak kell lennie, és minden nem szomszédos csúcsnak 2 közös szomszédnak kell lennie. A második paraméter azt jelenti, hogy a gráf egy reguláris gráf , csúcsonként 14 éllel [2] .

Ha ez a gráf létezik, akkor nincs 11-es rendű szimmetriája, ami azt jelenti, hogy szimmetriái nem vehetnek át egyetlen csúcsot sem másik csúcshoz [3] . A lehetséges szimmetriacsoportokra más korlátozások is vonatkoznak [4] .

Történelem

Az ilyen paraméterekkel rendelkező gráf lehetséges létezését már 1969-ben Norman L. Biggs [5] javasolta, és Conway [3] [6] [7] [8] nyitott létproblémát állított fel többek között . Conway 1975 óta maga is foglalkozik ezzel a problémával [6] , de 2014-ben díjat hirdetett annak, aki megoldja a problémát, a DIMACS Konferencia az Integer Sequence Identification Essential Problems of Integer Sequence Identification című konferenciáján bemutatott problémacsoport részeként. A készlet további problémái közé tartozik a trekle sejtés , a Danzer halmazok legkisebb távolsága és az a kérdés, hogy ki nyer a 16. lépés után az érmejátékban [1] .

Kapcsolódó grafikonok

Általánosságban elmondható, hogy csak öt lehetséges olyan paraméter-kombináció létezik, amelyekre erősen szabályos gráf létezhet azzal a tulajdonsággal, hogy minden él egy egyedi háromszöghez tartozik, és minden nem él (két nem szomszédos csúcs hiányzó éle) egy átlót alkot egyedi négyszög. Csak azt tudjuk, hogy az öt kombináció közül kettővel léteznek gráfok. A két gráf a kilenc csúcsú Paley gráf ( 3-3 duoprizma gráf ) paraméterekkel (9,4,1,2) és a Berlekamp-van Lint-Seidel gráf paraméterekkel (243,22,1,2). A 99 gráfos probléma ezen öt paraméterkombináció közül a legkisebbre kérdez rá, amelyre a gráf létezése ismeretlen [4] .

Jegyzetek

  1. ↑ 12 John H. Conway . Öt 1000 dolláros probléma (2017-es frissítés) . — On-line Encyclopedia of Integer Sequences .
  2. ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Nem Conway 99 gráfos problémája. - 2017. - arXiv : 1707.08047 .
  3. ↑ 1 2 Wilbrink HA A (99,14,1,2) erősen szabályos gráfon // JJ Seidelnek szentelt dolgozatok / de Doelder PJ, de Graaf J., van Lint JH. — Eindhoveni Műszaki Egyetem. - T. 84-WSK-03. – S. 342–355. – (EUT-jelentés).
  4. ↑ 1 2 Makhnev AA, Minakova IM,. Erősen szabályos, paraméteres gráfok automorfizmusairól ,  // Discrete Mathematics and Applications. - 2004. - január ( 14. évf. , 2. szám ). - doi : 10.1515/156939204872374 .
  5. ↑ Norman L. Biggs. Automorfizmusok véges csoportjai: tanfolyam a Southamptoni Egyetemen, 1969. október–december . - London és New York: Cambridge University Press, 1971. - V. 6. - P. 111. - (London Mathematical Society Lecture Note Series).
  6. ↑ 12 Richard K. Guy . Problémák // Proceedings of a Conference held at Michigan State University, East Lansing, Mich., 1974. június 17–19. / Kelly LM. - Berlin, New York: Springer-Verlag, 1975. - T. 490. - S. 233-244. — (Matematikai előadásjegyzetek). - doi : 10.1007/BFb0081147 . . Lásd a 7. problémát (JJ Seidel), pp. 237–238.
  7. ↑ Brouwer AE, Neumaier A. Megjegyzés az 5-ös kerületű részleges lineáris terekhez, erősen szabályos gráfokra való alkalmazással // Combinatorica. - 1988. - T. 8 , sz. 1 . – 57–61 . - doi : 10.1007/BF02122552 .
  8. ↑ Peter J. Cameron. Kombinatorika: témák, technikák, algoritmusok . - Cambridge: Cambridge University Press, 1994. - P. 331. - ISBN 0-521-45133-7 .