A Very Short History of Pseudorandom Cliquefree Graphs

I started writing this blog post some months ago. Occasion was that my paper “A construction for clique-free pseudorandom graphs” (in joint work Anurag Bishnoi and Valentina Pepe) was accepted by Combinatorica with minor revisions. More precisely, one of the referees was unfavorable of publication because he got the impressions that we are simply restating a result by Bannai, Hao and Song. I think that the referee had a point, but for slightly wrong reasons. This triggered me to do two things. First of all, it made me include more history of the construction in our actual paper. Then I wanted to write a blog post about the history of the construction. Sadly, I wanted to include too much history in my first attempt to write this post, so it was very much out of scope. Here now a more concise version of my original plan.

First let us shortly describe the original problem. You can learn the actual construction from Anurag’s more detailed blog post. A graph is $K_k$-free if it does not contain a $K_k$ as a subgraph. Furthermore, a $d$-regular graph on $n$ vertices is (optimally) pseudorandom if the second largest eigenvalue $\lambda$ of its adjacency matrix $A$ satisfies $\lambda =O(\sqrt{d})$ (so it might be more accurate to speak of a family of graphs). It is easy to see that such a graph satisfies

${\displaystyle \frac{d}{n}=O(n^{\frac{-1}{2k-3}}).}$

Except for $k=3$ it is not known if this is the correct upper bound. Alon and Krivelevich gave a construction in 1997 with $d/n=O(n^{\frac{-1}{k-2}})$. Our paper improved this to $d/n=O(n^{\frac{-1}{k-1}})$. The smallest non-trivial example of the new construction is the Petersen graph. Of course it is $K_3$-free:

1. The Graphs

What is our construction? We take a finite field ${\mathbb{F}}_q$ and define a quadratic form $Q:{\mathbb{F}}_q^k\to {\mathbb{F}}_q$ with some particular properties. For this post we stick to $Q(x_1,\dots ,x_n)=\xi x_1^2+x_2^2+x_3^2+\dots +x_k^2$. Now we partition the subspaces of dimension $1$ into the following three sets:

${\displaystyle X_0=\{⟨x⟩\subseteq {\mathbb{F}}_q^k:Q(x)=0\},}$

${\displaystyle X_1=\{⟨x⟩\subseteq {\mathbb{F}}_q^k:Q(x)\text{ is a square in }{\mathbb{F}}_q\setminus \{0\}\},}$

${\displaystyle X_2=\{⟨x⟩\subseteq {\mathbb{F}}_q^k:Q(x)\text{ is a non-square in }{\mathbb{F}}_q\}.}$

We define a graph $\mathrm{\Gamma }$ that has the elements of $X_2$ as vertices and two vertices are adjacent if they are orthogonal, that is whenever $\beta (x,y):=\xi x_1{y}_1+x_2{y}_2+x_3{y}_3+\dots +x_k{y}_k=0$. For $q$ odd, this graph has $n=\mathrm{\Theta }(q^{k-1})$, $d=\mathrm{\Theta }(q^{k-2})$, and $\lambda =\mathrm{\Theta }(\sqrt{d})$. When $\xi$ is chosen correctly, then the graph is also $K_k$-free.

Goal is to provide a short history of this construction. One might argue that this construction was already feasible in the late 19th century, as was my original plan, but this turned out to be an unrealistic goal for this blog post. If anyone is interested in a more in-depth history of geometries over quadratic forms, then I recommend Boekenhout’s “Prehistory and History of Polar Spaces and of Generalized Polygons”. The very short version is that Jordan knew all the necessary tools already in 1870 if we limit ourselves to $q$ a prime number. For now let’s stick to a more feasible goals:

• When was the first time that the graphs in our paper were investigated?
• How did I notice that these graphs work for our problem?

2. Rank $3$ Permutation Groups and Strongly Regular Graphs

A strongly regular graph is a regular graph with constants $c$ and $a$ such that two adjacent vertices have $c$ common neighbors and two non-adjacent vertices have $a$ common neighbors. These graphs were introduced by Bose in 1963. A great source for strongly regular graphs are rank 3 permutation groups. What is that? Suppose that $G$ acts transitively on $\{1,\dots ,v\}$. Let $S$ be the stabilizer of $1$. If $G$ is a rank $3$ permutation group, then $S$ has three orbits. One is of course $\{1\}$, but we have two more, $O_1$ and $O_2$. Now we can say that $O_1$ is the neighborhood of $1$, while $O_2$ is the non-neighborhood, and we obtain a strongly regular graph.

What is the connection to our graphs? For $q=3$, our graphs come from rank 3 permutation groups. In particular, they are listed in this article by Hubaut from 1975 entitled “Strongly Regular Graphs” where he gives a long list of strongly regular graphs from rank $3$ permutation groups. I am sure that latest at this point someone define the graph above as they wanted to know if it is still strongly regular for $q>3$. Sometimes it is for $q=5$, as Willbrink noticed (unpublished, see here), but otherwise it is not.

The work by Bannai, Hao and Song from 1990, which we cite for some properties of our graphs, is a continuation of this work. For larger $q$ the object in question is no longer a strongly regular graph, but a so-called association scheme and they calculated the eigenvalues of the association schemes in which our graphs live.

What I want to emphasize here is that all of this work is very closely connected to the investigation and classification of finite simple groups and design theory.

3. Non-Isomorphy by Clique Sizes

We have established that probably around 1975 someone knew about “our” graphs and understood them probably well enough to write our paper. That is a long time before Alon and Krivelevich published their paper with a very similar, but slightly worse construction, in 1997. Now why did no one make any connection between the two constructions? I honestly don’t know, but I can say how I did.

When I was in Sendai in late 2018, I worked with Akihiro Munemasa on variants of graph switching. I wrote about it here and our results are published in Linear Algebra and its Applications. In particular, we use so-called WQH switching to show that many strongly graphs related to certain quadratic forms are not determined by their parameters. Namely, we modify them slightly so that obtain new strongly regular graphs which have the same parameters as our original graphs.

Among the graphs, which we investigated, were the graphs described above. To show non-isomorphy, I had this trick to show that in the new graph we obtain maximal cliques of sizes which did not occur the original graph. But my argument required that the cliques have at least a certain size. In particular, for $k=6$ I was sloppy and assumed that our graph has a clique of size $6$. Akihiro Munemasa caught my mistake some time in spring 2019 and we corrected it. This meant that the graph only has a clique number of size $5$.

By coincidence, I visited Anurag Bishnoi a few weeks earlier in Berlin, where he mentioned about the problem of construction pseudorandom cliquefree graphs. So when Akihiro Munemasa told me about my mistake, I very quickly realized that this also means that this is a (small) improvement of the construction by Alon and Krivelevich. Hence, this is how the connection was finally made, 20 years too late!

(And it is probably also a bit surprising that the first improvement was for $K_6$-free graphs and not, as one might expect, for $K_3$-, $K_4$-, or even $K_5$-free graphs.)

Follow the blog!