Collecting Strongly Regular Graphs

Today I write about a recent hobby of mine: Collecting strongly regular graphs. It started three years ago. You can find my collection on my homepage. I collect many SRGs with known parameters. It started here. This is about size, not quantity, and tries to give an idea how a typical SRG with certain parameters might look like. By now my collection has grown so big that I should advertise and describe it.

At the time of writing, my collections splits into four parts. The first two parts are graphs generated with GM- or WQH-switching. The second two parts are graphs generated with what I call Kantor switching. All the data is provided in graph6 format in a compressed text file. In total something beyond 190 million.

1. WQH Switching

I discussed WQH switching here and I systematically applied WQH switching with partitions of type $ {2,2,n-4}$; $ {3,3,n-6}$; and $ {4,4,n-8}$ to nice representatives of strongly regular graphs of orders between 50 and 99 vertices. Smaller strongly regular graphs you can find on Ted Spence’s homepage. My collection up to $ {99}$ vertices is described in my recent publication in the Australasian Journal of Combinatorics, Vol. 84, entitled Switching for small strongly regular graphs. So I will not say much about that. This is the first part of my collection.

Then I sometimes generate more strongly regular graphs. Usually, I do not remember, why. This is the second part. Currently, this part contains an extension of my collection of strongly regular graphs with parameters $ {(85, 20, 3, 5)}$ (from 237,787 in the paper to 3,565,042 now — this took months), and some strongly regular graphs with parameters $ {(120, 63, 30, 36)}$. I forgot why I did that.

Lastly, if you scroll towards the end of my SRG collection page, you will find the C program which I used. You will have to compile it yourself, but it is quite fast. Also, use it in the Shell on a Unix system. It is a command line tool. My SRG page provides some basic examples. I rarely program in C, so do not judge my code too much.

[Feel welcome to judge my code a little bit. I judge other people’s code all the time. Or people who use Windows. Or people who like Overleaf. Or people who do not use something like nauty-labelg -qt | LC_ALL=C sort -u to remove isomorphic graphs from a long list of graphs. I am a judgemental person.]

2. Kantor Switching

Next comes Kantor switching and is described in Section 7 of my preprint with Andries E. Brouwer and Bill Kantor on the 4-vertex condition. Note that the switching will be renamed Polar switching in the next iteration of the paper. For my homepage, I will stick to Kantor switching.

Kantor switching is about finding a design in a strongly regular graph and replacing it by some other design. This can be the same design, but permuted. E.g. permutate the lines of a Fano plane, a $ {2}$-$ {(7, 3, 1)}$ design. Or just some other design with the same parameters. For instance, replace one $ {2}$-$ {(15, 7, 3)}$ design by one of the other three designs with these parameters. GM- and WQH-switching are closely related. For instance, one might view GM-switching with a partition of type $ {2,2,n-4}$ as permuting the blocks of a $ {2}$-$ {(4, 2, 1)}$ design.

The nontrivial applications of this switching (which I am aware of) are related to strongly regular graphs from polar spaces. In the third part I provide strongly regular graphs obtained from collinearity graphs of symplectic spaces $ {\mathrm{Sp}(2d, q)}$ with $ {(d, q) \in \{ (3, 2), (3, 3), (4, 2) \}}$. Here one uses designs with parameters $ {2}$-$ {(\frac{q^d-1}{q-1}, \frac{q^{d-1}}{q-1}, \frac{q^{d-2}}{q-1})}$. Only for $ {(d, q) = (4, 2)}$ there are other designs. Also, for parabolic spaces $ {O(7, 3)}$. It works for all polar spaces of rank at least 3, but we actually cared about a more particular property in our paper (the 4-vertex property) which the other polar spaces do not satisfy. So no data for the others!

This classification is feasible because it reduces to the enumeration of double cosets in small symmetric groups (see Section 7.2 in the aforementioned paper). For this I have no published code. But it is very easy to code with the permutation group theory software of your choice (which should be GAP or Magma).

Complementary, Edwin van Dam and Krystal Guo observed basically the same thing for $ {\mathrm{Sp}(4, q)}$ and some Hermitian generalized quadrangles using designs of type $ {2}$-$ {(q^2, q, 1)}$, so affine planes. They limit themselves to permutation of the same affine plane, not other designs, but it is easy to see that one can also replace designs as before. Similarly, all the theory from the paper with Brouwer and Kantor carries over, so that the problem reduces to enumerating certain double cosets. As I had the code for this ready, I generated the precisely 632,026 graphs with parameters $ {(85, 20, 3, 5)}$ which one obtains from their construction.

3. Future Updates

I might add more graphs in the future. I also have some graphs lying around somewhere which need to be added. Just check the site from time to time. Also feel free to download my data as a backup. If tomorrow a car runs me over, then all of it might get lost.

[Ok, it is easy to generate. But do you really want to?]