Conway's 99-graph problem

Last updated March 27, 2024

Unsolved problem in mathematics:

Does there exist a strongly regular graph with parameters (99,14,1,2)?

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 offered a $1000 prize for its solution.^[1]

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.^[2]

If this graph exists, it cannot have symmetries that take every vertex to every other vertex.^[3] Additional restrictions on its possible groups of symmetries are known.^[4]^[5]

History

The possibility of a graph with these parameters was already suggested in 1969 by Norman L. Biggs,^[6] and its existence noted as an open problem by others before Conway.^[3]^[7]^[8]^[9] Conway himself had worked on the problem as early as 1975,^[7] 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.^[1]

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 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.^[4]

Related Research Articles

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

<span class="mw-page-title-main">Strongly regular graph</span> Concept in graph theory

In graph theory, a strongly regular graph (SRG) is a regular graph $G = (V, E)$ with $v$ vertices and degree $k$ such that for some given integers

In mathematics, a two-graph is a set of (unordered) triples chosen from a finite vertex setX, such that every (unordered) quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Two-graphs have been studied because of their connection with equiangular lines and, for regular two-graphs, strongly regular graphs, and also finite groups because many regular two-graphs have interesting automorphism groups.

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

In mathematics, in graph theory, the Seidel adjacency matrix of a simple undirected graph G is a symmetric matrix with a row and column for each vertex, having 0 on the diagonal, −1 for positions whose rows and columns correspond to adjacent vertices, and +1 for positions corresponding to non-adjacent vertices. It is also called the Seidel matrix or—its original name—the (−1,1,0)-adjacency matrix. It can be interpreted as the result of subtracting the adjacency matrix of G from the adjacency matrix of the complement of G.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.

<span class="mw-page-title-main">Asymmetric graph</span> Undirected graph with no non-trivial symmetries

In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries.

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason, who used it to evaluate the Ramsey number R(3,3,3) = 17.

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20-regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construction is folklore, it was named after Andries Brouwer and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.

In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16-regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8).

In the geometry of 4 dimensions, the 3-3 duoprism or triangular duoprism is a four-dimensional convex polytope. It can be constructed as the Cartesian product of two triangles and is the simplest of an infinite family of four-dimensional polytopes constructed as Cartesian products of two polygons, the duoprisms.

In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

In graph theory, the Berlekamp–Van Lint–Seidel graph is a locally linear strongly regular graph with parameters $. This means that it has 243 vertices, 22 edges per vertex, exactly one shared neighbor per pair of adjacent vertices, and exactly two shared neighbors per pair of non-adjacent vertices. It was constructed by Elwyn Berlekamp, J. H. van Lint, and Johan Jacob Seidel as the coset graph of the ternary Golay code.$

In graph theory, the Games graph is the largest known locally linear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1,20). This means that it has 729 vertices, and 40824 edges. Each edge is in a unique triangle and each non-adjacent pair of vertices have exactly 20 shared neighbors. It is named after Richard A. Games, who suggested its construction in an unpublished communication and wrote about related constructions.

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.

References

1 2 Conway, John H., Five $1,000 Problems (Update 2017) (PDF), On-Line Encyclopedia of Integer Sequences , retrieved 2019-02-12. See also OEIS sequenceA248380.
↑ Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv: 1707.08047
1 2 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
1 2 Makhnev, A. A.; Minakova, I. M. (January 2004), "On automorphisms of strongly regular graphs with parameters $\lambda =1$ , $\mu =2$ ", Discrete Mathematics and Applications, 14 (2), doi:10.1515/156939204872374, MR 2069991, S2CID 118034273
↑ 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
↑ 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
1 2 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, S2CID 206812356
↑ Cameron, Peter J. (1994), Combinatorics: topics, techniques, algorithms, Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR 1311922

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[con-1] 1 2 Conway, John H., Five $1,000 Problems (Update 2017) (PDF), On-Line Encyclopedia of Integer Sequences , retrieved 2019-02-12. See also OEIS sequenceA248380.

[zd-2] Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv: 1707.08047

[wil-3] 1 2 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

[mm-4] 1 2 Makhnev, A. A.; Minakova, I. M. (January 2004), "On automorphisms of strongly regular graphs with parameters $\lambda =1$ , $\mu =2$ ", Discrete Mathematics and Applications, 14 (2), doi:10.1515/156939204872374, MR 2069991, S2CID 118034273

[bl-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

[big-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

[guy-7] 1 2 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.

[bn-8] 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

[cam-9] Cameron, Peter J. (1994), Combinatorics: topics, techniques, algorithms, Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR 1311922

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]