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 , with , a direct application of Chernoff bound implies that the probability of the following event approaches as approaches infinity:
where are arbitrary subsets of vertices and denotes the number of edges with one end vertex in and the other one in . Note that is the expected number of edges between and in this model, and is the standard deviation. Now let be a -regular graph on -vertices and let be the second largest eigenvalue of in absolute value (these are referred to as -graphs). Then the following is true for any two subsets of vertices:
where is the second largest eigenvalue of the adjacency matrix of the graph, in absolute value. Therefore, if is small, and in particular close to being , then the graph mimics the behaviour of . In fact, for any -graph, with , one can show by looking at the square of the adjacency matrix that . The graphs where 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 -vertices, with , that he then used to give explicit bounds on some Ramsey numbers, and to show that the maximum possible Euclidean norm of unit vectors in with the property that among any three of them two are orthogonal, is equal to . 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 , such that any optimally pseudorandom graph on vertices with must contain a triangle. This can be generalised to cliques of size , where we have a constant such that any optimally pseudorandom -graph with must contain . 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 is a set of vertices with , then there are at least edges with both end points in .
The natural question now is to give matching constructions for this bound for all , 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 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 was the construction of Alon and Krivelevich that gives us optimally pseudorandom graphs with edge density . Note that this starts giving a better construction than Alon’s triangle free graphs at . 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 . The construction is fairly easy to describe, and for a proof you can refer to the paper:
Let be a quadratic form over where is a non-square in (we assume to be odd). Define a graph with vertices as the -dimensional subspaces of , for which is a square, and making two vertices and adjacent if they are orthogonal to each other, that is,
Then this graph is a -free -graph with , and .
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 -free graphs that have higher edge density than .
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 -free pseudorandom graphs of density , then this would asymptotically determine off-diagonal Ramsey numbers , with fixed and . In fact, even an improvement of the denominator from (which is in our construction) to 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.