Games graph

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 (112 per vertex). Each edge is in a unique triangle (it is a locally linear graph) 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^[1] and wrote about related constructions.^[2]

Construction

The construction of this graph involves the unique (up to symmetry) 56-point cap set (a subset of points with no three in line) in $PG(5,3)$ , the five-dimensional projective geometry over a three-element field.^[3] The six-dimensional projective geometry, $PG(6,3)$ , can be partitioned into a six-dimensional affine space $AG(6,3)$ and a copy of $PG(5,3)$ (the points at infinity with respect to the affine space). The Games graph has as its vertices the 729 points of the affine space $AG(6,3)$ . Each line in the affine space goes through three of these points, and through a fourth point at infinity. The graph contains a triangle for every line of three affine points that passes through a point of the cap set.^[1]

Properties

Several of the graph's properties follow immediately from this construction. It has $729=3^{6}$ vertices, because the number of points in an affine space is the size of the base field to the power of the dimension. For each affine point, there are 56 lines through cap set points, 56 triangles containing the corresponding vertex, and $112=56\times 2$ neighbors of the vertex. And there can be no triangles other than the ones coming from the construction, because any other triangle would have to come from three different lines meeting in a common plane of $PG(6,3)$ , and the three cap set points of the three lines would all lie on the intersection of this plane with $PG(5,3)$ , which is a line. But this would violate the defining property of a cap set that it has no three points on a line, so no such extra triangle can exist. The remaining property of strongly regular graphs, that all non-adjacent pairs of points have the same number of shared neighbors, depends on the specific properties of the 5-dimensional cap set.

Related graphs

With the $3\times 3$ Rook's graph and the Brouwer–Haemers graph, the Games graph is one of only three possible strongly regular graphs whose parameters have the form ${\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}$ .^[4]

The same properties that produce a strongly regular graph from a cap set can also be used with an 11-point cap set in $PG(4,3)$ , producing a smaller strongly regular graph with parameters (243,22,1,2).^[5] This graph is the Berlekamp–van Lint–Seidel graph.^[6]

References

^ ^a ^b van Lint, J. H.; Brouwer, A. E. (1984), "Strongly regular graphs and partial geometries" (PDF), in Jackson, David M.; Vanstone, Scott A. (eds.), Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982, London: Academic Press, pp. 85–122, MR 0782310. See in particular pp. 114–115.
^ Games, Richard A. (1983), "The packing problem for projective geometries over GF(3) with dimension greater than five", Journal of Combinatorial Theory, Series A, 35 (2): 126–144, doi:10.1016/0097-3165(83)90002-X, MR 0712100. See in particular Table VII, p. 139, entry for $r=5$ and $d=3$ .
^ Hill, Raymond (1978), "Caps and codes", Discrete Mathematics, 22 (2): 111–137, doi:10.1016/0012-365X(78)90120-6, MR 0523299
^ Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with $\lambda =1$ ", Journal of Combinatorial Theory, Series B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016/j.jctb.2013.05.005, MR 3071380
^ Cameron, Peter J. (1975), "Partial quadrangles", The Quarterly Journal of Mathematics, Second Series, 26: 61–73, doi:10.1093/qmath/26.1.61, MR 0366702
^ Berlekamp, E. R.; van Lint, J. H.; Seidel, J. J. (1973), "A strongly regular graph derived from the perfect ternary Golay code", A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Amsterdam: North-Holland: 25–30, doi:10.1016/B978-0-7204-2262-7.50008-9, MR 0364015

[vlb-1] van Lint, J. H.; Brouwer, A. E. (1984), "Strongly regular graphs and partial geometries" (PDF), in Jackson, David M.; Vanstone, Scott A. (eds.), Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982, London: Academic Press, pp. 85–122, MR 0782310. See in particular pp. 114–115.

[g-2] Games, Richard A. (1983), "The packing problem for projective geometries over GF(3) with dimension greater than five", Journal of Combinatorial Theory, Series A, 35 (2): 126–144, doi:10.1016/0097-3165(83)90002-X, MR 0712100. See in particular Table VII, p. 139, entry for $r=5$ and $d=3$ .

[h-3] Hill, Raymond (1978), "Caps and codes", Discrete Mathematics, 22 (2): 111–137, doi:10.1016/0012-365X(78)90120-6, MR 0523299

[br-4] Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with $\lambda =1$ ", Journal of Combinatorial Theory, Series B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016/j.jctb.2013.05.005, MR 3071380

[c-5] Cameron, Peter J. (1975), "Partial quadrangles", The Quarterly Journal of Mathematics, Second Series, 26: 61–73, doi:10.1093/qmath/26.1.61, MR 0366702

[bvls-6] Berlekamp, E. R.; van Lint, J. H.; Seidel, J. J. (1973), "A strongly regular graph derived from the perfect ternary Golay code", A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Amsterdam: North-Holland: 25–30, doi:10.1016/B978-0-7204-2262-7.50008-9, MR 0364015

[1]

[2]

[3]

[4]

[5]

[6]