Conways grafproblem med 99 vertex

Conways grafproblem med 99 vertex är ett olöst problem som frågar om det finns en 99 - hörn oriktad graf där varannan angränsande hörn har exakt en gemensam granne och där två icke-intilliggande hörn har exakt två gemensamma grannar. På motsvarande sätt måste vilken kant som helst vara en del av en unik triangel, och alla par av icke-angränsande hörn måste vara på diagonalen av en unik 4-cykel. John Horton Conway tillkännagav ett pris på $1 000 för den som löste detta problem [1] .

Egenskaper

Om en sådan graf finns måste den vara en lokalt linjär starkt regelbunden graf med parametrar (99,14,1,2). De första, tredje och fjärde parametrarna kodar problemformuleringen – grafen måste ha 99 hörn, varje par av angränsande hörn måste ha 1 gemensam granne och alla icke intilliggande hörn måste ha 2 gemensamma grannar. Den andra parametern innebär att grafen är en vanlig graf med 14 kanter per vertex [2] .

Om denna graf finns har den inga symmetrier av ordning 11, vilket betyder att dess symmetrier inte kan ta någon vertex till någon annan vertex [3] . Det finns andra begränsningar för möjliga symmetrigrupper [4] .

Historik

Den möjliga existensen av en graf med sådana parametrar föreslogs redan 1969 av Norman L. Biggs [5] , och Conway [3] [6] [7] [8] framställde bland annat som ett öppet existensproblem . Conway har själv arbetat med detta problem sedan 1975 [6] , men tillkännagav ett pris 2014 till den som löser problemet, som en del av en uppsättning problem som presenterades på DIMACS-konferensen om väsentliga problem med heltalssekvensidentifikation. Andra problem i denna uppsättning inkluderar trekle-förmodan , det minsta avståndet av Danzer- set och frågan om vem som vinner efter drag 16 i myntspelet [1] .

Relaterade grafer

Mer generellt finns det bara fem möjliga kombinationer av parametrar för vilka en starkt regelbunden graf kan existera med egenskapen att varje kant tillhör en unik triangel, och varje icke-kant (den saknade kanten av två icke-angränsande hörn) bildar en diagonal av en unik fyrhörning. Vi vet bara att det finns grafer med två av dessa fem kombinationer. De två graferna är Paley -grafen med nio hörn ( 3-3 duoprism -graf ) med parametrar (9,4,1,2) och Berlekamp-van Lint-Seidel-grafen med parametrar (243,22,1,2). 99-grafproblemet frågar om den minsta av dessa fem parameterkombinationer för vilka existensen av en graf är okänd [4] .

Anteckningar

1. ↑ 12 John H. Conway . Fem $1 000-problem (uppdatering 2017) . — On-Line Encyclopedia of Integer Sequences .
2. ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Inte Conways 99-grafproblem. - 2017. - arXiv : 1707.08047 .
3. ↑ 1 2 Wilbrink HA På den (99,14,1,2) starkt regelbundna grafen // Paper dedicated to JJ Seidel / de Doelder PJ, de Graaf J., van Lint JH. — Eindhovens tekniska universitet. - T. 84-WSK-03. — S. 342–355. — (EUT-rapport).
4. ↑ 1 2 Makhnev AA, Minakova IM,. Om automorfismer av starkt regelbundna grafer med parametrar ,  // Diskret matematik och applikationer. - 2004. - Januari ( vol. 14 , nummer 2 ). - doi : 10.1515/156939204872374 .
5. ↑ Norman L. Biggs. Finita grupper av automorfismer: Kurs ges vid University of Southampton, oktober–december 1969 . - London och New York: Cambridge University Press, 1971. - V. 6. - S. 111. - (London Mathematical Society Lecture Note Series).
6. ↑ 12 Richard K. Guy . Problem // Proceedings of a Conference som hölls vid Michigan State University, East Lansing, Mich., 17–19 juni 1974 / Kelly LM. - Berlin, New York: Springer-Verlag, 1975. - T. 490. - S. 233-244. — (Föreläsningsanteckningar i matematik). - doi : 10.1007/BFb0081147 . . Se problem 7 (JJ Seidel), s. 237–238.
7. ↑ Brouwer AE, Neumaier A. En anmärkning om partiella linjära rum med omkrets 5 med en tillämpning på starkt regelbundna grafer // Combinatorica. - 1988. - T. 8 , nr. 1 . — s. 57–61 . - doi : 10.1007/BF02122552 .
8. ↑ Peter J. Cameron. Kombinatorik: ämnen, tekniker, algoritmer . - Cambridge: Cambridge University Press, 1994. - S. 331. - ISBN 0-521-45133-7 .