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.

size_aut

(more…)

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