Conway's 99-graph problem

<h2 id="properties">Properties</h2>
If such a graph exists, it would necessarily be a <a href="/facts/Locally_linear_graph/9mLNuC6S">locally linear graph</a> and a <a href="/facts/Strongly_regular_graph/0GbdLwSd">strongly regular graph</a> 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 <a href="/facts/Regular_graph/j9dSoLE6">regular graph</a> with 14 edges per vertex.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
If this graph exists, it cannot have symmetries that take every vertex to every other vertex.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> Additional restrictions on its possible groups of symmetries are known.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="history">History</h2>
The possibility of a graph with these parameters was already suggested in 1969 by <a href="/facts/Norman_L._Biggs/PXXEVgPP">Norman L. Biggs</a>,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
and its existence noted as an open problem by others before Conway.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Conway himself had worked on the problem as early as 1975,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> 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 <a href="/facts/Thrackle/KAGs310p">thrackle conjecture</a>, the minimum spacing of <a href="/facts/Danzer_set/86oEfApl">Danzer sets</a>, and the question of who wins after the move 16 in the game <a href="/facts/Sylver_coinage/tLKAXmwm">sylver coinage</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="related-graphs">Related graphs</h2>
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 <a href="/facts/Paley_graph/SHbT4vj5">Paley graph</a> (the graph of the <a href="/facts/3-3_duoprism/B1dhsgrg">3-3 duoprism</a>) with parameters (9,4,1,2) and the <a href="/facts/Berlekamp%E2%80%93van_Lint%E2%80%93Seidel_graph/rUPKRc8w">Berlekamp–van Lint–Seidel graph</a> with parameters (243,22,1,2). The parameters for which graphs are unknown are: (99,14,1,2), (6273,112,1,2) and (494019,994,1,2). The 99-graph problem describes the smallest of these combinations of parameters for which the existence of a graph is unknown.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Conway, John H., Five $1,000 Problems (Update 2017) (PDF), On-Line Encyclopedia of Integer Sequences, retrieved 2019-02-12. See also OEIS sequence A248380. <a href="/wiki/John_Horton_Conway" target="_blank">/wiki/John_Horton_Conway</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv:1707.08047 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Wilbrink, H. A. (August 1984), "On the (99,14,1,2) strongly regular graph", in de Doelder, P. J.; de Graaf, 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 <a href="https://research.tue.nl/files/2449333/256699.pdf" target="_blank">https://research.tue.nl/files/2449333/256699.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Makhnev, A. A.; Minakova, I. M. (January 2004), "On automorphisms of strongly regular graphs with parameters 
 
 
 
 λ
 =
 1
 
 
 {\displaystyle \lambda =1}
 
, 
 
 
 
 μ
 =
 2
 
 
 {\displaystyle \mu =2}
 
", Discrete Mathematics and Applications, 14 (2), doi:10.1515/156939204872374, MR 2069991, S2CID 118034273 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Behbahani, Majid; Lam, Clement (2011), "Strongly regular graphs with non-trivial automorphisms", Discrete Mathematics, 311 (2–3): 132–144, doi:10.1016/j.disc.2010.10.005, MR 2739917 <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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, ISBN 9780521082150, MR 0327563 <a href="9780521082150" target="_blank">9780521082150</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Wilbrink, H. A. (August 1984), "On the (99,14,1,2) strongly regular graph", in de Doelder, P. J.; de Graaf, 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 <a href="https://research.tue.nl/files/2449333/256699.pdf" target="_blank">https://research.tue.nl/files/2449333/256699.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Guy, Richard K. (1975), "Problems", in Kelly, L. M. (ed.), The Geometry of Metric and Linear Spaces, Lecture Notes in Mathematics, vol. 490, Berlin and New York: Springer-Verlag, pp. 233–244, doi:10.1007/BFb0081147, ISBN 978-3-540-07417-5, MR 0388240. See problem 7 (J. J. Seidel), pp. 237–238. <a href="978-3-540-07417-5" target="_blank">978-3-540-07417-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">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, S2CID 206812356 <a href="/wiki/Andries_Brouwer" target="_blank">/wiki/Andries_Brouwer</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Cameron, Peter J. (1994), Combinatorics: topics, techniques, algorithms, Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR 1311922 <a href="0-521-45133-7" target="_blank">0-521-45133-7</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Guy, Richard K. (1975), "Problems", in Kelly, L. M. (ed.), The Geometry of Metric and Linear Spaces, Lecture Notes in Mathematics, vol. 490, Berlin and New York: Springer-Verlag, pp. 233–244, doi:10.1007/BFb0081147, ISBN 978-3-540-07417-5, MR 0388240. See problem 7 (J. J. Seidel), pp. 237–238. <a href="978-3-540-07417-5" target="_blank">978-3-540-07417-5</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Conway, John H., Five $1,000 Problems (Update 2017) (PDF), On-Line Encyclopedia of Integer Sequences, retrieved 2019-02-12. See also OEIS sequence A248380. <a href="/wiki/John_Horton_Conway" target="_blank">/wiki/John_Horton_Conway</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Makhnev, A. A.; Minakova, I. M. (January 2004), "On automorphisms of strongly regular graphs with parameters 
 
 
 
 λ
 =
 1
 
 
 {\displaystyle \lambda =1}
 
, 
 
 
 
 μ
 =
 2
 
 
 {\displaystyle \mu =2}
 
", Discrete Mathematics and Applications, 14 (2), doi:10.1515/156939204872374, MR 2069991, S2CID 118034273 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Conway's 99-graph problem open-in-new

Conway's 99-graph problem