A central (and foundational) question in extremal graph theory is the forbidden subgraph problem of Turán, which asks for the largest number of edges in an -vertex graph that does not contain any copy of a given graph as its subgraph. This number is denoted by and it is called the Turán number of the graph . While the Erdős-Stone theorem has solved this problem asymptotically whenever is non-bipartite, the case of bipartite graphs is still wide open. For example, when is isomorphic to the cube graph , all we know is that , for some constants and large enough . The two most important cases in this problem are when is a complete bipartite graph or an even cycle. In this post we will focus on the latter (see this for a survey), where graphs derived from finite geometries give us the best known extremal constructions for small cycles.
It was proved by Bondy and Simonovits that , but this bound is known to be (asymptotically) sharp only for the case of or ; so in particular we do not even know what is. The sharpness for these cases follows from the existence of finite generalized -gons of order for every prime power and . These are point-line geometries introduced by Jacques Tits in , and an easy graph theoretic definition of these objects is as follows:
A generalized -gon of order , for , is a point-line geometry whose incidence graph is -regular, has diameter and girth .
One can count the total number of points/lines in a generalized -gon in terms of the parameter , which tells us that the incidence graph has vertices and edges. Since by definition, such a graph is free, we get examples of -free graphs on vertices with edges, whenever such a structure exists. Sadly, it is known that such generalized -gons can only exist for , and in these cases they are only known to exist when is a power of a prime. Using the density of prime numbers these objects can be used to prove that for .
The case is simply a finite projective plane of order , and Tits had already shown the existence (and many examples) for the other cases. Some special cases of generalized -gons and -gons were rediscovered by Benson in 1966 (and in the combinatorics community sometimes he’s the one who is cited for constructing these extremal graphs).
While it’s quite easy to construct generalized -gons of order using zeros of a non-degenerate quadratic form in the -dimensional projective space over (these objects are a special case of polar spaces), the construction of a generalized -gon is quite involved. As an attempt to simplify this situation, in 1991 Wenger constructed a family of bipartite graphs for integers and prime power , with vertices and edges, such that the graphs , and did not have any , and , respectively. His construction and the proof of the cycle freeness involved some simple algebra over the finite fields. Later on his graphs were studied extensively, from various perspectives, and it was realised (I am not sure exactly when, but it’s at least mentioned here) that is in fact just an induced subgraph of the incidence graph of a well-known generalized quadrangle (the quadric ) and is isomorphic to a homomorphic image of the incidence graph of the only known generalized hexagon of order , the split Cayley hexaon. (From the definition of it will be pretty clear that it is a -regular induced subgraph of the incidence graph of the Desarguesian projective plane.)
In this post, we will see how is directly related to a particular family of generalized quadrangles introduced by Tits (which first appeared in Dembowski, 1968), known as the generalized quadrangles. These quadrangles are in fact isomorphic to when is odd, or in general when is an irreducible conic (which will be the case corresponding to Wenger graphs). Let’s start with the definition of Wenger graphs.
Construction 1: Let and be two copies of . Then is the bipartite graph defined on and by making two vertices and adjacent if the following equations are satisfied:
The original equations used by Wenger were a bit different, but it can be (and has been) shown that the graph we get is the same. One of the first thing we notice in these defining relations is that once you have fixed , every value of uniquely determine the vector , and vice versa. We can thus conclude that this graph is -regular and thus it was edges, since each side of the bipartite graph has size . Therefore, if this graph was free, then this will be an extremal graph with this property due to the Bondy-Simonovits upper bound. Let’s look at the smallest example .
We have if . Therefore, for any fixed the set of points adjacent to in are precisely those points which lie on the line , i.e., the line of slope through the point in the plane . If we identify the elements of by these non-vertical lines of (and identify with the points in ), then we get an isomorphic between and the incidence graph between the points and non-vertical lines of . The vertical lines correspond to a point on the line that one can use to obtain the projective completion of the affine space . So geometrically, we can also think of as the following graph:
Given the projective plane , let be a line and a point on the line . Then is the incidence graph between the points not lying on the line and the lines which do not contain the point , i.e., all the lines through the points in .
Alternatively, we can use coordinates and get the following description:
Let be the set of points with (homogeneous) coordinates and let be the set of all lines through the points with coordinates with . Then is the incidence graph between and .
From these geometric descriptions, and the fact that through every two points there is a unique line, it is clear that is -free. In fact, we can give a similar geometric description of all ‘s. We first give the description involving coordinates and then take a coordinate-free approach which will in fact give a broader class of graphs.
Let be the set of points in with (homogeneous) coordinates and let be the set of all lines through the points with coordinates with . Then is the incidence graph between and .
Note that the set of points we have used to define the line set is in fact a part of the normal rational curve (a.k.a. moment curve) in the hyperplane defined by the points whose first coordinate is (we can call it the hyperplane at infinity and the set as the affine points). The following map gives us the isomorphism between the two descriptions of the Wenger graph: and .
The main property that the normal rational curve in has, and what we will use to show cycle freeness, is that any points on it are linearly independent. Or equivalently, any -dimensional (projective) subspace of intersects the curve in at most points, where . The object that abstracts out this property is known as an arc, i.e., a set of points in with the property that no points on it lie on a common hyperplane. With this in our hand we get the following coordinate free description of Wenger graphs, which appears in  and :
Construction 2: Let be a hyperlpane in and let be an arc of size in . Define to be the incidence graph between the point set and the set of all lines of that contain a point of .
This is in fact a larger class of graphs than the one described by Wenger since an arc does not have to come from a normal rational curve (there exist several such families of arcs). Now that we have this geometric construction, let’s focus on the graph .
Generalized Quadrangles and the Wenger Graph
Let’s see how is related to generalized -gons in exactly the same as is related to generalized -gons (the projective planes). For all , the graph can be shown to be -free as follows: if there was a then we will have lines in which pairwise intersect each other in and intersect in a point of the set ; but this will be a contradiction to the fact that is an arc since these lines will span a plane which intersects in a line that contains points and of . Alternatively, we can do the same thing as we did before and show that is in fact a latex -regular induced subgraph of the incidence graph of a generalized quadrangle of order .
The generalized quadrangle that we will use to show this is the following one, called , which was originally constructed by Tits in early 1960’s:
Let be a hyperplane in and let be an oval in , i.e., a set of points no three of which are collinear. Define the points as (i) the points of , (ii) the hyperplanes of for which we have , and (iii) one new symbol . Define the lines as (a) lines of through points of which are not contained in and (b) the points of . A point of type (i) is only incidence with lines of type (a), and the incidence is the natural one. A point of type (ii) is incidence with all the lines of type (a) contained in it and with the unique line of type (b) corresponding to the unique element of contained in it. The point is incidence with no lines of type (a) and all lines of type (b).
Now note that if from this generalized quadrangle we remove the point , a line of type (b) (which corresponds to a point of ), and all lines and points which are at distance at most from or in the incidence graph of , then what we are left with is the incidence structure defined on all the points of type (i) and those lines of type (ii) which pass through a point of . This is precisely the description of the Wenger graph !
Now, one might want to find out is related to the more well known generalized quadrangle (which is also the one that was constructed by Benson). This is given by the well known isomorphism between and whenever is an irreducible conic (see Theorem 3.2.2 in ), which by the seminal work of Segre, is always true for odd.
Let’s end this blog post now with a list of questions, challenges and references.
Question 1: The graph is known to be a homomorphic image of a -regular induced subgraph of the split Cayley hexagon . Is there an easy way to see that?
Question 2: If we think of as a point-line geometry, then construction 2 above gives us what is known as a linear representation of the geometry described in construction 1. So is a linear representation of a particular subgeometry of the generalized quadrangle , and is a generalization of that. What are some other interesting subgeometries (perhaps corresponding to regular induced subgraphs) of generalized polygons that can be generalized in this way to give interesting families of bipartite graphs that can be useful in Turán problems?
Question 3: Can be described using some well-studied geometrical structure like the generalized polygons? May be it’s related to some near polygon or a polar space?
Big Challenge: Give a finite geometrical construction of an infinite family of -free graphs which have vertices and edges. For example, these graphs could have and edges.
References and further reading
 P. Cara, S. Rottey and G. Van de Voorde, A construction for infinite families of semisymmetric graphs revealing their full automorphism group.
 K. E. Mellinger and D. Mubayi, Constructions of Bipartite Graphs from Finite Geometries. Constructions of Bipartite Graphs from Finite Geometries.
 S. E. Payne and J. A. Thas, Finite Generalized Quadrangles.
 F. Lazebnik and S. Sun, Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey.
 S. M. Cioabă, F. Lazebnik and W. Li, On the spectrum of Wenger graphs.