Conway's 99-graph problem
In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists a 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.[1]
If such a graph exists, it would necessarily be a locally linear 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 two adjacent vertices should have 1 common neighbor, and every two non-adjacent vertices should have two common neighbors. The second parameter means that the graph is a regular graph with 14 edges per vertex.[2]
The possibility of a graph with these parameters was already suggested in 1969 by Norman L. Biggs,[3] and its existence noted as an open problem by others before Conway.[4][5][6][7] 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.[4]
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, and it is only known that graphs exist with two of these five combinations. These two graphs are the nine-vertex Paley graph 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 unknown case in the list of these graphs.[8]
References
- ^ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
- ^ Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv:1707.08047
- ^ Biggs, Norman (1971), Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969, London Mathematical Society Lecture Note Series, vol. 6, London and New York: Cambridge University Press, p. 111, MR 0327563
- ^ a b Wilbrink, H. A. (August 1984), "On the (99,14,1,2) strongly regular graph", in de Doelder, P. J.; de Graaf, de, J.; van Lint, J. H. (eds.), Papers dedicated to J. J. Seidel (PDF), EUT Report, vol. 84-WSK-03, Eindhoven University of Technology, pp. 342–355
{{citation}}: CS1 maint: multiple names: editors list (link) - ^ Guy, Richard K. (1975), "Problems", in Kelly, L. M. (ed.), Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974, Lecture Notes in Mathematics, vol. 490, Berlin and New York: Springer-Verlag, pp. 233–244, doi:10.1007/BFb0081147, MR 0388240. See problem 7 (J. J. Seidel), pp. 237–238.
- ^ Brouwer, A. E.; Neumaier, A. (1988), "A remark on partial linear spaces of girth 5 with an application to strongly regular graphs", Combinatorica, 8 (1): 57–61, doi:10.1007/BF02122552, MR 0951993
- ^ Cameron, Peter J. (1994), Combinatorics: topics, techniques, algorithms, Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR 1311922
- ^ Makhnev, A. A.; Minakova, I. M. (January 2004), "On automorphisms of strongly regular graphs with parameters , ", Discrete Mathematics and Applications, 14 (2), doi:10.1515/156939204872374, MR 2069991
