Kopparty’s graph

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 d-regular graphs on n vertices with d = \Theta(n^{2/3}) and the second largest eigenvalue equal to \Theta(n^{1/3}).

Let p \neq 3 be a prime (it will become clear later why we are excluding 3), and let \mathbb{F}_{q} be a finite field of characteristic p, that is q = p^h for some integer h. For a subset S of the vector space V = \mathbb{F}_q^3 we define the Cayley graph G = Cay(V, S) as the graph on V with u \sim v if u - v \in S. This graph is undirected if for every s \in S we have -s \in S and loopless if 0 \not \in S, 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 S. The property of S that ensures that G is triangle-free is that s_1 + s_2 + s_3 \neq 0 for any s_1, s_2, s_3 \in S (not necessarily distinct). This explains why we assume p \neq 3, as otherwise s + s + s = 0 for every s \in S. Consider the following set:

S = \{(xy, xy^2, xy^3) : x \in T, y \in \mathbb{F}_q^{\times}\}

where T is a subset of \mathbb{F}_q with the property that no three elements of T sum to 0, that is, the same property that we wanted from S. Any such T implies triangle-freeness of G: if x_1(y_1, y_1^2, y_1^3) + x_2(y_2, y_2^2, y_2^3) + x_3(y_3, y_3^2, y_3^3) = 0, then either y_1 = y_2 = y_3 and we have a contradiction because of the property of T or we get a non-trivial linear combination of the rows of a Vandermonde matrix equal to 0, which is also a contradiction (note that 0 \not \in T and y_i \neq 0 for all i).

The specific choice of T will soon become clear, but for now let us focus on the degree and eigenvalues of G. The degree is equal to |S| = |T|(q - 1), while the number of vertices is q^3 (thus we would later require |T| = \Theta(q)). 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 a = (a_1, a_2, a_3) \in V, the eigenvalue \lambda_a corresponding to the eigenvector \chi_a : V \rightarrow \mathbb{C} defined by \chi_a(x_1, x_2, x_3) = \omega^{\mathrm{Tr}(a_1 x_1 + a_2 x_2 + a_3 x_3)} satisfies \lambda = \sum_{x \in S} \chi_a(x), where \mathrm{Tr} is the absolute trace function defined by \mathrm{Tr}(\alpha) = \alpha + \alpha^p + \cdots + \alpha^{p^{h - 1}}, and \omega = e^{2 \pi i/p} is a primitive p-th root of unity.

The eigenvalue corresponding to (0, 0, 0) is d = |S|, which is the largest eigenvalue. So let a = (a_1, a_2, a_3) \in V \setminus \{0\}. We have

\lambda_a =  \sum_{y \in \mathbb{F}_q^\times} \sum_{x \in T} \omega^{\mathrm{Tr}(x f(y))},

where f(y) = a_1 y + a_2y^2 + a_3 y^3. We now make the choice of T = \{u \in \mathbb{F}_q : \mathrm{Tr}(u) \in \{-1, 1\}\}. Note that |T| = 2q/p, unless p = 2 when |T| = q/p, T = -T and no three elements of T can sum to 0, as p \neq 3. From the following lemma, whose proof is a fun exercise in algebra, it follows that several of the terms in the expression for \lambda_a are 0.

Lemma. Let z \in \mathbb{F}_q \setminus \mathbb{F}_p. Then for every k \in \mathbb{F}_p we have \sum_{x \in \mathrm{Tr}^{-1}(k)} \omega^{\mathrm{Tr}(x z)} = 0.

Thanks to this Lemma we can write

\lambda_a = \sum_{y \in f^{-1}(\mathbb{F}_p) \setminus \{0\}} \sum_{x \in T} \omega^{\mathrm{Tr}(xf(y))}.

For any fixed k \in \mathbb{F}_p, the number of y for which f(y) = a_1 y + a_2 y^2 + a_3 y^3 = k, is at most 3 since it is an equation of degree at most 3 (and at least $1$) in one variable. Therefore, the number of summands is at most 3p|T|, which implies that |\lambda_a| \leq 3p|T|.

To summarise, we have a triangle-free graph on q^3 vertices which is d-regular with d = 2q(q - 1)/p and has all eigenvalues other than d at most 6 q in absolute value. For fixed p and h \rightarrow \infty, we get the infinite family that we were looking for.

Remark 1: Other choices of T will work as well, for example T = \{u \in \mathbb{F}_q : p/3 < \mathrm{Tr}(u) < 2p/3\}.

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 K_s-free, with s \geq 4, would be very interesting!

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Spectral Graph Theory and tagged , , , , , . Bookmark the permalink.

3 Responses to Kopparty’s graph

  1. Fedor Petrov says:

    Hm, but what if y_3=0 and y_1=y_2?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s