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 Sp(6, 2), has parameters (63, 30, 13, 15). 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 Sp(6,2). Plots of the number of cliques, cocliques, and the size of the autmorphism group are scattered throughout this post.

size_aut

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.

size_cl

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.

size_cl_log

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).

size_cocl

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.

size_cocl_log

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s