Alon’s construction of optimal pseudorandom graphs from 1994 is useful for obtaining several interesting combinatorial results in various areas of mathematics, some of which are highlighted in this survey of Noga from last year (also see my previous post). In this post I would like to discuss an alternate construction, due to Swastik Kopparty, that has the same properties and thus can be used instead to prove all of these interesting results. It seems like this construction is not so well known (I learned about it from a conversation with Noga), even though it is a bit simpler to describe and in some sense more general. The construction appears in Kopparty’s lecture notes on Cayley Graphs.
What we are looking for is an infinite sequence of triangle-free -regular graphs on vertices with and the second largest eigenvalue equal to .
Let be a prime (it will become clear later why we are excluding ), and let be a finite field of characteristic , that is for some integer . For a subset of the vector space we define the Cayley graph as the graph on with if . This graph is undirected if for every we have and loopless if , both of which we will assume. Kopparty’s construction, much like Alon’s construction, is a Cayley graph of this form for some suitably chosen . The property of that ensures that is triangle-free is that for any (not necessarily distinct). This explains why we assume , as otherwise for every . Consider the following set:
where is a subset of with the property that no three elements of sum to , that is, the same property that we wanted from . Any such implies triangle-freeness of : if , then either and we have a contradiction because of the property of or we get a non-trivial linear combination of the rows of a Vandermonde matrix equal to , which is also a contradiction (note that and for all ).
The specific choice of will soon become clear, but for now let us focus on the degree and eigenvalues of . The degree is equal to , while the number of vertices is (thus we would later require ). The eigenvalues of Cayley graphs, at least for the case of finite abelian groups, are easy to describe. I recommend chapter 5 of the lecture notes of Luca Trevisan for the basic theory. For , the eigenvalue corresponding to the eigenvector defined by satisfies , where is the absolute trace function defined by , and is a primitive -th root of unity.
The eigenvalue corresponding to is , which is the largest eigenvalue. So let . We have
where . We now make the choice of . Note that , unless when , and no three elements of can sum to , as . From the following lemma, whose proof is a fun exercise in algebra, it follows that several of the terms in the expression for are .
Lemma. Let . Then for every we have .
Thanks to this Lemma we can write
For any fixed , the number of for which , is at most since it is an equation of degree at most (and at least $1$) in one variable. Therefore, the number of summands is at most , which implies that .
To summarise, we have a triangle-free graph on vertices which is -regular with and has all eigenvalues other than at most in absolute value. For fixed and , we get the infinite family that we were looking for.
Remark 1: Other choices of will work as well, for example .
Remark 2: This can be generalised to an odd-cycle free construction, just like Alon’s graph can be generalised. Any generalisation to even-cycle free constructions, or to -free, with , would be very interesting!