# polar space # 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.  # Pseudorandom clique-free graphs

Anurag Bishnoi wrote a post about a recently finished preprint on pseudorandom clique-free graphs written by me, Anurag, and Valentina Pepe. We (slightly) improve a construction by Alon and Krivelevich from 1997. Anurag's Math Blog

Pseudorandom graphs are graphs that in some way behaves like a random graph with the same edge density. One way in which this happens is as follows. In the random graph \$latex G(n, p)\$, with \$latex p = p(n) leq 0.99\$, a direct application of Chernoff bound implies that the probability of the following event approaches \$latex 1\$ as \$latex n\$ approaches infinity:

\$latex |e(S, T) – p|S||T|| = O(sqrt{pn |S||T|}\$

where \$latex S,T\$ are arbitrary subsets of vertices and \$latex e(S,T)\$ denotes the number of edges with one end vertex in \$latex S\$ and the other one in \$latex T\$.  Note that \$latex p|S||T|\$ is the expected number of edges between \$latex S\$ and \$latex T\$ in this model, and \$latex sqrt{p(1 – p)|S||T|}\$ is the standard deviation. Now let \$latex G\$ be a \$latex d\$-regular graph on \$latex n\$-vertices and let \$latex lambda\$ be the second largest…

View original post 804 more words