“Conway's 99-graph problem”的意思、由来-开放百科全书

In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors. Equivalently, every edge should be part of a unique triangle and every non-adjacent pair should be one of the two diagonals of a unique 4-cycle. John Horton Conway has offered a $1000 prize for its solution.{{r|con}}

Properties

If such a graph exists, it would necessarily be a locally linear graph and a strongly regular graph with parameters (99,14,1,2). The first, third, and fourth parameters encode the statement of the problem: the graph should have 99 vertices, every pair of adjacent vertices should have 1 common neighbor, and every pair of non-adjacent vertices should have 2 common neighbors. The second parameter means that the graph is a regular graph with 14 edges per vertex.{{r|zd}}

If this graph exists, it does not have any symmetries of order 11, which implies that its symmetries cannot take every vertex to every other vertex.{{r|wil}} Additional restrictions on its possible groups of symmetries are known.{{r|mm}}

History

The possibility of a graph with these parameters was already suggested in 1969 by Norman L. Biggs,{{r|big}}

and its existence noted as an open problem by others before Conway.{{r|wil|guy|bn|cam}}

Conway himself had worked on the problem as early as 1975,{{r|guy}} but offered the prize in 2014 as part of a set of problems posed in the DIMACS Conference on Challenges of Identifying Integer Sequences.

Other problems in the set include the thrackle conjecture, the minimum spacing of Danzer sets, and the question of who wins after the move 16 in the game sylver coinage.{{r|con}}

Related graphs

More generally, there are only five possible combinations of parameters for which a strongly regular graph could exist with each edge in a unique triangle and each non-edge forming the diagonal of a unique quadrilateral. It is only known that graphs exist with two of these five combinations. These two graphs are the nine-vertex Paley graph (the graph of the 3-3 duoprism) with parameters (9,4,1,2) and the Berlekamp–van Lint–Seidel graph with parameters (243,22,1,2). The 99-graph problem describes the smallest of these five combinations of parameters for which the existence of a graph is unknown.{{r|mm}}

References

1. ^{{citation | last1 = Brouwer | first1 = A. E. | author1-link = Andries Brouwer | last2 = Neumaier | first2 = A. | doi = 10.1007/BF02122552 | issue = 1 | journal = Combinatorica | mr = 951993 | pages = 57–61 | title = A remark on partial linear spaces of girth 5 with an application to strongly regular graphs | volume = 8 | year = 1988}}
2. ^{{citation | last = Cameron | first = Peter J. | authorlink = Peter Cameron (mathematician) | isbn = 0-521-45133-7 | mr = 1311922 | page = 331 | publisher = Cambridge University Press | location = Cambridge | title = Combinatorics: topics, techniques, algorithms | url = https://books.google.com/books?id=_aJIKWcifDwC&pg=PA331 | year = 1994}}
3. ^{{citation | last = Conway | first = John H. | author-link = John Horton Conway | accessdate = 2019-02-12 | publisher = On-Line Encyclopedia of Integer Sequences | title = Five $1,000 Problems (Update 2017) | url = https://oeis.org/A248380/a248380.pdf}}. See also {{OEIS el|A248380}}.
4. ^{{citation | last = Guy | first = Richard K. | authorlink = Richard K. Guy | editor-last = Kelly | editor-first = L. M. | editor-link = Leroy Milton Kelly | contribution = Problems | doi = 10.1007/BFb0081147 | location = Berlin and New York | mr = 0388240 | pages = 233–244 | publisher = Springer-Verlag | series = Lecture Notes in Mathematics | title = Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974 | volume = 490 | year = 1975}}. See problem 7 (J. J. Seidel), pp. 237–238.
5. ^{{citation | last1 = Makhnev | first1 = A. A. | last2 = Minakova | first2 = I. M. | date = January 2004 | doi = 10.1515/156939204872374 | issue = 2 | journal = Discrete Mathematics and Applications | mr = 2069991 | title = On automorphisms of strongly regular graphs with parameters

| volume = 14}}
6. ^{{citation | last = Wilbrink | first = H. A. | editor1-last = de Doelder | editor1-first = P. J. | editor2-last = de Graaf | editor2-first = de, J. | editor3-last = van Lint | editor3-first = J. H. | contribution = On the (99,14,1,2) strongly regular graph | date = August 1984 | pages = 342–355 | publisher = Eindhoven University of Technology | series = EUT Report | title = Papers dedicated to J. J. Seidel | url = https://research.tue.nl/files/2449333/256699.pdf | volume = 84-WSK-03}}
7. ^{{citation | last1 = Zehavi | first1 = Sa'ar | last2 = David de Olivera | first2 = Ivo Fagundes | arxiv = 1707.08047 | title = Not Conway's 99-graph problem | year = 2017}}