Sp(6, 2)’s Family, Plots, and Ramsey Numbers

Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36, 10, 4, 2), but there are 32548 non-isomorphic graphs with parameters (36, 15, 6, 6).

Peter Cameron, Random Strongly Regular Graphs?

This a shorter version of this report which I just put on my homepage. But I added more links. I assume that one is familiar with strongly regular graphs (SRGs). One particular SRG, the collinearity graph of [latex]Sp(6, 2)[/latex], has parameters [latex](63, 30, 13, 15)[/latex]. A very simple technique, Godsil-McKay (GM) switching, can generate many non-isomorphic graphs with the same parameters. More specifically, there are probably billions such graphs and I generated 13 505 292 of them. This is the number of graphs which you obtain by applying a certain type of GM switching (i.e. using a bipartition of type 4, 59) at most 5 times to [latex]Sp(6,2)[/latex]. Plots of the number of cliques, cocliques, and the size of the autmorphism group are scattered throughout this post.

You can download the list of all graphs from my Dropbox folder here. Be aware that it is about 2 GB in size (gzip, in graph6 format).

Let us give a short description of the collinearity graph of $ Sp(2d, q)$: Vertices are 1-dimensional subspaces of $ \mathbb{F}_q^{2d}$. Two 1-dimensional subspaces are adjacent if they are perpendicular with respect to the bilinear form $ x_1y_2 – x_2y_1 + \ldots + x_{2d-1}y_{2d} – x_{2d}y_{2d-1}$. For $ (d,q) = (3, 2)$, this graph has 63 vertices, is 30-regular, two adjacent vertices have 13 common neighbors, and two non-adjacent vertices have 15 common neighbors. It is long known that GM switching can produce graphs non-isomorphic to the collinearity graph of $ Sp(2d, 2)$. A variation of it works for $ Sp(2d, q)$ and even in more general settings.

Why do I summarize my computations? The collinearity graph of the polar space $ Sp(6, 2)$ is in many ways the smallest really interesting representative of the family of collinearity graphs coming from finite classical polar spaces. Thus it is a good toy model to investigate general behavior.

Some basic facts about $ Sp(6, 2)$: It has an automorphism group of size $ 1451520$, clique number 7 and coclique number 7. SRGs with the same parameters as $ Sp(6, 2)$ have spectrum $ (30,3^{35},-5^{27})$, clique number at most 7 and coclique number at most 9. The clique and coclique bounds follow from Hoffman’s ratio bound (due to the name of my blog, I have to mention this).

In the following we discuss some questions associated with SRGs with the same parameters as the collinearity graph of $ Sp(6, 2)$ and, more generally, $ Sp(6, q)$.

Anurag Bishnoi, Valentina Pepe and I are implicitly asking if graphs such as the collinearity graph of $ Sp(2d, q)$ can be modified such that they are clique-free. Anurag discusses this here a bit for a special case. A far more specific question is if there exists an SRG with parameters the same as $ Sp(6, q)$ which is $ K_4$-free. If one can show this for infinitely many $ q$, then this essentially determines the asymptotic behavior of the Ramsey number $ r(4, n)$. Again, Anurag discussed this connection in his blog. This is still too general, so we are stuck with the following:

Question 1. Is there a strongly regular graph with parameters $ (63, 30, 13, 15)$ which does not contain a clique of size $ 4$?

Probable answer: no. Even a targeted threshold based computer search could only find
a $ K_6$-free graph. Most SRGs with these parameters seem to be $ I_8$-free. As Anurag Bishnoi pointed out to me, we currently only know that the Ramsey number $ r(4, 8)$ is at least 56. Therefore the following is variation of the question above, even so the answer is still probably no:

Question 2. Is there a strongly regular graph with parameters $ (63, 30, 13, 15)$ which contains no clique of size 4 and no coclique of size 8?

Update (10.04.2020): Alexander Gavrilyuk pointed out to me that Bondarenko, Prymak, and Radchenko showed in 2014 that any SRG with parameters $ (63, 30, 13, 15)$ has at least 2354 cliques of size 4. Therefore, the answer to Question 1 and 2 is now surely no.

Update (12.04.2020): I found a second (embarrisingly easy) argument to show that such an SRG always contains many cliques of size 4. Now I wondering if one can show that it contains a clique of size 5.

I was wondering before if the number of SRGs with the same parameters as the collinearity graph of $ Sp(2d, q)$ growth hyperexponentially (in $ q$ or $ d$, your choice). Similarly, Bill Kantor is interested in questions such as the following, see for instance here: For any given group G, can we find an SRG $ \Gamma$ with the same parameters as the $ Sp(2d, q)$ for some (alternatively: infinitely many) $ (d, q)$ such that $ Aut(\Gamma) = G$? The following question goes into the same direction:

Question 3. Do almost all SRGs with the same parameters as $ Sp(2d, q)$ have a trivial automorphism group?

You can choose what “almost all” means here. In any interpretation, I suspect the answer to be yes.

We used nauty-traces, cliquer, a tiny C program, and standard GNU tools for this small investigation.

Follow the blog!