## Wenger graphs

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 $n$-vertex graph $G$ that does not contain any copy of a given graph $H$ as its subgraph. This number is denoted by $ex(n, H)$ and it is called the Turán number of the graph $H$. While the Erdős-Stone theorem has solved this problem asymptotically whenever $H$ is non-bipartite, the case of bipartite graphs is still wide open. For example, when $H$ is isomorphic to the cube graph $Q_3$, all we know is that $c_1 n^{3/2} \leq ex(n, Q_3) \leq c_2 n^{8/5}$, for some constants $c_1, c_2$ and large enough $n$. The two most important cases in this problem are when $H$ 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 $ex(n, C_{2k}) = O(n^{1 + 1/k})$, but this bound is known to be (asymptotically) sharp only for the case of $k = 2, 3$ or $5$; so in particular we do not even know what $ex(n, C_{8})$ is. The sharpness for these cases follows from the existence of finite generalized $n$-gons of order $q$ for every prime power $q$ and $n = 3, 4, 6$. These are point-line geometries introduced by Jacques Tits in $1959$, and an easy graph theoretic definition of these objects is as follows:

A generalized $k$-gon of order $q$, for $k,q \geq 2$, is a point-line geometry whose incidence graph is $(q+1)$-regular, has diameter $k$ and girth $2k$.

One can count the total number of points/lines in a generalized $k$-gon in terms of the parameter $q$, which tells us that the incidence graph has $\Theta(q^{k-1})$ vertices and $\Theta(q^{k})$ edges. Since by definition, such a graph is $C_{2k - 2}$ free, we get examples of $C_{2k - 2}$-free graphs on $n$ vertices with $\Theta(n^{1 + 1/(k-1)})$ edges, whenever such a structure exists. Sadly, it is known that such generalized $k$-gons can only exist for $k \in \{3, 4, 6\}$, and in these cases they are only known to exist when $q$ is a power of a prime. Using the density of prime numbers these objects can be used to prove that $ex(n, 2k) = \Theta(n^{1 + 1/k)})$ for $k = 2, 3, 5$.

The $k = 3$ case is simply a finite projective plane of order $q$, and Tits had already shown the existence (and many examples) for the other cases. Some special cases of generalized $4$-gons and $6$-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 $4$-gons of order $q$ using zeros of a non-degenerate quadratic form in the $4$-dimensional projective space over $\mathbb{F}_q$ (these objects are a special case of polar spaces), the construction of a generalized $6$-gon is quite involved. As an attempt to simplify this situation, in 1991 Wenger constructed a family of bipartite graphs $H_k(q)$ for integers $k \geq 2$ and prime power $q$, with $2q^k$ vertices and $q^{k + 1}$ edges, such that the graphs $H_2(q)$, $H_3(q)$ and $H_5(q)$ did not have any $C_4$, $C_6$ and $C_{10}$, 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 $H_3(q)$ is in fact just an induced subgraph of the incidence graph of a well-known generalized quadrangle (the quadric $Q(4,q)$) and $H_5(q)$ is isomorphic to a homomorphic image of the incidence graph of the only known generalized hexagon of order $q$, the split Cayley hexaon. (From the definition of $H_2(q)$ it will be pretty clear that it is a $q$-regular induced subgraph of the incidence graph of the Desarguesian projective plane.)

In this post, we will see how $H_3(q)$ is directly related to a particular family of generalized quadrangles introduced by Tits (which first appeared in Dembowski, 1968), known as the $T_2(O)$ generalized quadrangles. These quadrangles are in fact isomorphic to $Q(4,q)$ when $q$ is odd, or in general when $O$ 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 $P$ and $L$ be two copies of $\mathbb{F}_q^k$. Then $H_{k}(q)$ is the bipartite graph defined on $P$ and $L$ by making two vertices $p = (p_1, \dots, p_k)$ and $\ell = (\ell_1, \dots, \ell_k)$ adjacent if the following equations are satisfied:

$p_2 + \ell_2 = p_1 \ell_1$
$p_3 + \ell_3 = p_1 \ell_1^2$
$\dots$
$p_k + \ell_k = p_1\ell_1^{k-1}$

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 $(p_1, p_2, \dots, p_k)$, every value of $\ell_1$ uniquely determine the vector $(\ell_2, \dots, \ell_k)$, and vice versa. We can thus conclude that this graph is $q$-regular and thus it was $q^{k + 1}$ edges, since each side of the bipartite graph has size $q^k$. Therefore, if this graph was $C_{2k}$ 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 $k = 2$.

We have $(p_1, p_2) \sim (\ell_1, \ell_2)$ if $p_2 + \ell_2 = p_1 \ell_1$. Therefore, for any fixed $\ell = (\ell_1, \ell_2)$ the set of points adjacent to $\ell$ in $H_2(q)$ are precisely those points which lie on the line $y = \ell_1 p_1 - \ell_2$, i.e., the line of slope $\ell_1$ through the point $(0, -\ell_2)$ in the plane $\mathbb{F}_q^2$. If we identify the elements of $L$ by these non-vertical lines of $\mathbb{F}_q^2$ (and identify $P$ with the points in $\mathbb{F}_q^2$), then we get an isomorphic between $H_2(q)$ and the incidence graph between the points and non-vertical lines of $\mathbb{F}_q^2$. The vertical lines correspond to a point $P_\infty$ on the line $\ell_\infty$ that one can use to obtain the projective completion of the affine space $\mathbb{F}_q^2$. So geometrically, we can also think of $H_2(q)$ as the following graph:

Given the projective plane $\mathrm{PG}(2,q)$, let $\ell$ be a line and $P$ a point on the line $\ell$. Then $H_2(q)$ is the incidence graph between the points not lying on the line $\ell$ and the lines which do not contain the point $P$, i.e., all the lines through the $q$ points in $\ell \setminus \{P\}$

Alternatively, we can use coordinates and get the following description:

Let $P$ be the set of points with (homogeneous) coordinates $(1, p_1, p_2)$ and let $L$ be the set of  all lines through the points with coordinates $(0, 1, \ell_1)$ with $\ell_1 \in \mathbb{F}_q$. Then $H_2(q)$ is the incidence graph between $P$ and $L$

From these geometric descriptions, and the fact that through every two points there is a unique line, it is clear that $H_2(q)$ is $C_4$-free. In fact, we can give a similar geometric description of all $H_k(q)$‘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 $P$ be the set of points in $\mathrm{PG}(k,q)$ with (homogeneous) coordinates $(1, p_1, \dots, p_k)$ and let $L$ be the set of all lines through the points with coordinates $(0, 1, \ell_1, \ell_1^2, \dots, \ell_1^{k-1})$ with $\ell_1 \in \mathbb{F}_q$. Then $H_k(q)$ is the incidence graph between $P$ and $L$

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) $\{(0, \ell_1, \dots, \ell_1^{k-1}) : \ell_1 \in \mathbb{F}_q\} \cup \{(0, 0, \dots, 0, 1)\}$ in the hyperplane defined by the points whose first coordinate is $0$ (we can call it the hyperplane at infinity and the set $P$ as the affine points). The following map gives us the isomorphism between the two descriptions of the Wenger graph:  $(p_1, \dots, p_k) \mapsto (1, p_1, \dots, p_k)$  and $(\ell_1, \dots, \ell_k) \mapsto \{\lambda(1, 0, -\ell_2, -\ell_3, \dots, -\ell_k) + \mu (0, 1, \ell_1, \ell_1^2, \dots, \ell_1^{k-1}) : \lambda, \mu \in \mathbb{F}_q\}$.

The main property that the normal rational curve in $\mathrm{PG}(k - 1, q)$ has, and what we will use to show cycle freeness, is that any $k$ points on it are linearly independent. Or equivalently, any $s$-dimensional (projective) subspace of $\mathrm{PG}(k - 1, q)$ intersects the curve in at most $s + 1$ points, where $1 \leq s \leq k - 2$. The object that abstracts out this property is known as an arc, i.e., a set of points in $\mathrm{PG}(k - 1, q)$ with the property that no $k$ 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 [1] and [2]:

Construction 2: Let $H_\infty \cong \mathrm{PG}(k - 1, q)$ be a hyperlpane in $\mathrm{PG}(k, q)$ and let $S$ be an arc of size $q$ in $H_\infty$. Define $H_k(q)$ to be the incidence graph between the point set $\mathrm{PG}(k, q) \setminus H_\infty$ and the set of all lines of $\mathrm{PG}(k, q)$ that contain a point of $S$

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 $H_3(q)$.

Generalized Quadrangles and the Wenger Graph

Let’s see how $H_3(q)$ is related to generalized $4$-gons in exactly the same as $H_2(q)$ is related to generalized $3$-gons (the projective planes). For all $k \geq 3$, the graph $H_k(q)$ can be shown to be $C_6$-free as follows: if there was a $C_6$ then we will have $3$ lines $\ell_1, \ell_2, \ell_3$ in $\mathrm{PG}(k, q)$ which pairwise intersect each other in $\mathrm{PG}(k, q) \setminus H_\infty$ and intersect $H_\infty$ in a point of the set $S$; but this will be a contradiction to the fact that $S$ is an arc since these lines will span a plane which intersects $H_\infty$ in a line that contains $3$ points $\ell_1 \cap H_\infty, \ell_2 \cap H_\infty$ and $\ell_3 \cap H_\infty$ of $S$. Alternatively, we can do the same thing as we did before and show that $H_3(q)$ is in fact a latex $q$-regular induced subgraph of the incidence graph of a generalized quadrangle of order $q$.

The generalized quadrangle that we will use to show this is the following one, called $T_2(O)$, which was originally constructed by Tits in early 1960’s:

Let $H \cong \mathrm{PG}(2, q)$ be a hyperplane in $\mathrm{PG}(3,q)$ and let $O$ be an oval in $H$, i.e., a set of $q + 1$ points no three of which are collinear. Define the points as (i) the points of $\mathrm{PG}(3,q) \setminus H$, (ii) the hyperplanes $X$ of $\mathrm{PG}(3,q)$ for which we have $|X \cap O| = 1$, and (iii) one new symbol $(\infty)$. Define the lines as (a) lines of $\mathrm{PG}(3,q)$ through points of $O$ which are not contained in $H$ and (b) the points of $O$. 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 $O$ contained in it. The point $(\infty)$ 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 $(\infty)$, a line $\ell$ of type (b) (which corresponds to a point $P$ of $O$), and all lines and points which are at distance at most $2$ from $(\infty)$ or $\ell$ in the incidence graph of $T_2(O)$, 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 $S = O \setminus \{P\}$This is precisely the description of the Wenger graph $H_3(q)$!

Now, one might want to find out $H_3(q)$ is related to the more well known generalized quadrangle $Q(4,q)$ (which is also the one that was constructed by Benson). This is given by the well known isomorphism between $T_2(O)$ and $Q(4,q)$ whenever $O$ is an irreducible conic (see Theorem 3.2.2 in [3]), which by the seminal work of Segre, is always true for $q$ odd.

Let’s end this blog post now with a list of questions, challenges and references.

Question 1: The graph $H_5(q)$ is known to be a homomorphic image of a $q$-regular induced subgraph of the split Cayley hexagon $H(q)$. Is there an easy way to see that?

Question 2: If we think of $H_k(q)$ 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 $H_3(q)$ is a linear representation of a particular subgeometry of the generalized quadrangle $T_2(O)$, and $H_k(q)$ 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 $H_4(q)$ 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 $C_8$-free graphs which have $n$ vertices and $\Theta(n^{5/4})$ edges. For example, these graphs could have $\Theta(q^4)$ and $\Theta(q^5)$ edges.

[1] P. Cara, S. Rottey and G. Van de Voorde, A construction for infinite families of semisymmetric graphs revealing their full automorphism group.
[2] K. E. Mellinger and D. Mubayi, Constructions of Bipartite Graphs from Finite Geometries. Constructions of Bipartite Graphs from Finite Geometries.
[3] S. E. Payne and J. A. Thas, Finite Generalized Quadrangles.
[4] F. Lazebnik and S. Sun, Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey.
[5] S. M. Cioabă, F. Lazebnik and W. Li, On the spectrum of Wenger graphs.