Pseudorandom clique-free graphs

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 $G(n, p)$ , with $p = p(n) \leq 0.99$ , a direct application of Chernoff bound implies that the probability of the following event approaches $1$ as $n$ approaches infinity:

$|e(S, T) - p|S||T|| = O(\sqrt{pn |S||T|})$

where $S,T$ are arbitrary subsets of vertices and $e(S,T)$ denotes the number of edges with one end vertex in $S$ and the other one in $T$ . Note that $p|S||T|$ is the expected number of edges between $S$ and $T$ in this model, and $\sqrt{p(1 - p)|S||T|}$ is the standard deviation. Now let $G$ be a $d$ -regular graph on $n$ -vertices and let $\lambda$ be the second largest eigenvalue of $G$ in absolute value (these are referred to as $(n, d, \lambda)$ -graphs). Then the following is true for any two subsets $S, T$ of vertices:

$|e(S,T) - (d/n) |S||T|| \leq \lambda \sqrt{|S||T|}$ .

where $\lambda$ is the second largest eigenvalue of the adjacency matrix of the graph, in absolute value. Therefore, if $\lambda$ is small, and in particular close to being $O(\sqrt{d})$ , then the graph mimics the behaviour of $G(n, d/n)$ . In fact, for any $(n, d, \lambda)$ -graph, with $d < n/2$ , one can show by looking at the square of the adjacency matrix that $\lambda = \Omega(\sqrt{d})$ . The graphs where $\lambda = \Theta(\sqrt{d})$ are known as optimally pseudorandom.

Pseudorandom graphs have found several applications over the last few decades, and there are many interesting questions about them (see the survey of Krivelevich and Sudakov). In a 1994 paper, Noga Alon constructed a family of optimally pseudorandom triangle free graphs on $n$ -vertices, with $d/n = \Omega(n^{-1/3})$ , that he then used to give explicit bounds on some Ramsey numbers, and to show that the maximum possible Euclidean norm of $n$ unit vectors in $\mathbb{R}^n$ with the property that among any three of them two are orthogonal, is equal to $\Theta(n^{2/3})$ . More applications of this construction can be found in the recent survey paper of Noga based on a talk he gave at the conference celebrating the 70th birthday of László Lovász (which is where I learned about these graphs, and the main topic of this post).

Alon’s construction is in fact optimal in the sense that there existence a constant $C > 0$ , such that any optimally pseudorandom graph on $n$ vertices with $d/n > Cn^{-1/3}$ must contain a triangle. This can be generalised to cliques of size $k$ , where we have a constant $C > 0$ such that any optimally pseudorandom $(n, d, \lambda)$ -graph with $d/n > C n^{-1/(2k - 3)}$ must contain $K_k$ . The proof of this follows from greedily picking common neighbours, using the following lemma (that can be proved using the edge distribution proposition above):

If $S$ is a set of vertices with $|S| \geq 2n\lambda/d$ , then there are at least $d|S|^2/4n$ edges with both end points in $S$ .

The natural question now is to give matching constructions for this bound for all $k > 3$ , or improve the bound. This question has been asked by several people, as it arises naturally in many situations, but it has been open for every $k > 3$ since the past 20 years or so. David Conlon has called it “one of the outstanding open problems about pseudorandom graph” (also check out this video).

The best known construction so far for larger values of $k$ was the construction of Alon and Krivelevich that gives us optimally pseudorandom graphs with edge density $d/n = \Theta(n^{-1/(k - 2)}$ . Note that this starts giving a better construction than Alon’s triangle free graphs at $k = 6$ . In my recent work with Ferdinand Ihringer and Valentina Pepe, we have been able to provide a better construction, that gives a family of graphs with edge density $d/n = \Theta(n^{-1/(k - 1)})$ . The construction is fairly easy to describe, and for a proof you can refer to the paper:

Let $Q(x_1, \dots, x_k) = x_1^2 + \xi x_2^2 + \sum_{i = 3}^k x_k^2$ be a quadratic form over $\mathbb{F}_q$ where $\xi$ is a non-square in $\mathbb{F}_q$ (we assume $q$ to be odd). Define a graph with vertices as the $1$ -dimensional subspaces $x$ of $\mathbb{F}_q^k$ , for which $Q(x)$ is a square, and making two vertices $x$ and $y$ adjacent if they are orthogonal to each other, that is,
$\frac{1}{2}(Q(x + y) - Q(x) - Q(y)) = x_1 y_1 + \xi x_2y_2 + \sum_{i =3}^n x_i y_i = 0$ .

Then this graph is a $K_k$ -free $(n, d, \lambda)$ -graph with $n = (1 + o(1))q^{k-1}/2$ , $d = (1 + o(1))q^{k - 2}/2$ and $\lambda = \Theta(q^{(k - 2)/2})$ .

While we now have slightly better constructions, we are still far away from the conjectured bound. I am hopeful though that finite geometry, and especially the geometries associated with quadratic forms (known as polar spaces), can play an important role in obtaining even better constructions. In fact, there is a construction due to Kopparty for triangle-free graphs matching the parameters of Alon’s construction that essentially comes from a generalized quadrangle (which is a polar space), if you look at it carefully (see my earlier post for hints on that). Moreover, Conlon was able to give an (almost) optimal probabilistic construction which also uses generalized quadrangles. This a strong indication that polar spaces can be useful in general. As a first step, we should perhaps try to obtain optimally pseudorandom $K_4$ -free graphs that have higher edge density than $n^{-1/3}$ .

Edit 04/09/2019: An exciting new result by Mubyai and Verstraete shows that if the main conjecture of this post is true, that is, there exists $K_k$ -free pseudorandom graphs of density $n^{-1/(2k - 3)}$ , then this would asymptotically determine off-diagonal Ramsey numbers $R(k, t)$ , with $k$ fixed and $t \rightarrow \infty$ . In fact, even an improvement of the denominator from $k - 1$ (which is in our construction) to $k + 1$ would be a big development as it’ll improve the current lower bounds on Ramsey numbers. See the first half of this talk of Mubayi.

5 Responses to Pseudorandom clique-free graphs

Ferdinand Ihringer says:

May 15, 2019 at 3:15 pm

Reblogged this on Ratio Bound – A Combinatorics Blog and commented:
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.

Pingback: Ramsey numbers from pseudorandom graphs | Anurag's Math Blog
Pingback: Bound on Ramsey numbers from finite geometry | Anurag's Math Blog
Pingback: Ratio Bound – A Combinatorics Blog
Pingback: Generalized polygons in extremal combinatorics | Anurag's Math Blog