Quasirandom Cayley graphs

Quasirandom Cayley graphs, Discrete Analysis 2017:6, 14 pp.

An extremely important phenomenon in extremal combinatorics is that of quasirandomness: for many combinatorial structures, it is possible to identify a list of deterministic properties, each one of which says in one way or another that the structure behaves like a typical random example of that structure, and each of which implies all the others.

The first results of this kind were due to Thomason and to Chung, Graham and Wilson. They identified several equivalent properties of graphs. For example, if $G$ is a graph with $n$ vertices and average degree $\alpha n$, then the following conditions are equivalent.

(1) For any two large subsets $A,B\subset V(G)$ the number of pairs $(x,y)\in A\times B$ such that $xy\in E(G)$ is approximately $\alpha|A||B|$.

(2) The number of labelled 4-cycles $xyzw$ in $G$ is approximately $\alpha^4n^4$.

(3) The largest eigenvalue of the adjacency matrix of $G$ is approximately $\alpha n$ and the second largest eigenvalue is small compared with $\alpha n$.

(4) For almost all pairs of vertices $x,y\in V(G)$ the intersection of their neighbourhoods has size approximately $\alpha^2 n$.

(5) For every graph $H$ with a bounded number of vertices $v_1,\dots,v_k$, if $x_1,\dots,x_k$ are randomly and independently chosen vertices of $G$, then the probability that $x_ix_j\in E(G)$ for all $i,j$ such that $v_iv_j\in E(H)$ is approximately $\alpha^{|E(H)|}$.

Of course, these statements are not precise, but one can make them precise by quantifying the errors, and expressing them as a proportion of the main term. For example, the number of labelled 4-cycles is regarded as being approximately $\alpha^4n^4$ if it differs from $\alpha^4n^4$ by at most $cn^4$ for some small constant $c$. Then to say that one statement implies another is to say that the error in the second statement tends to zero as the error in the first statement tends to zero. Note that this notion of equivalence is a “loose” one, meaning that if one applies one of the implications and then applies the reverse implication, one may not be able to recover the original error estimate, but one still obtains an error estimate that tends to zero as the original error estimate tends to zero.

When it comes to applications, this looseness often does not matter, but sometimes it causes problems. That is particularly the case when $\alpha$ is not a fixed constant but tends to zero as $n$ tends to infinity. That is, it can be problematic for sparse graphs. Moreover, there are examples that show that some of the important implications cannot be improved, so there is a genuine obstacle to the use of quasirandomness in proofs about sparse graphs.

A particularly important implication that does hold for sparse graphs is that (3) implies (1), even when $\alpha=d/n$ for some constant $d$: that is, when $G$ has constant average degree. However, simple examples show that this implication cannot be reversed when $G$ is sparse.

It came as something of a surprise, therefore, when Kohayakawa, Rödl and Schacht proved that if $G$ is a Cayley graph of an Abelian group with respect to some set of generators, then (1) and (3) are equivalent. This is surprising because in many contexts the properties of Cayley graphs are very similar to those of general graphs.

This paper extends the work of Kohayakawa, Rödl and Schacht to the non-Abelian case. Since Cayley graphs of general groups are significantly more diverse than those of Abelian groups, this adds to the surprise of the Abelian case. In order to prove this result, the authors reformulate properties (1) and (3) in terms of two matrix norms, the cut norm and the spectral norm. They then use Grothendieck’s inequality to prove that the cut norm is equivalent to a third norm, which they call the Grothendieck norm. And then a short argument establishes that for adjacency matrices of Cayley graphs the Grothendieck norm is equal to the spectral norm. An alternative argument for the last implication, based on non-Abelian Fourier analysis, is given in an appendix. This alternative argument is a more direct generalization of the proof of Kohayakawa, Rödl and Schacht.