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 Debowski, 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.

 

References and further reading

[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. Cioabă, F. Lazebnik and W. Li, On the spectrum of Wenger graphs.

Advertisements

About Anurag Bishnoi

A mathematician working at FU Berlin as a postdoc. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s