The cage problem and generalized polygons (part 1)

This post is a continuation of my previous post on the cage problem. Just to recall the main problem, for any given integers $k \geq 2$ and $g \geq 3$ , we want to find the least number of vertices in a simple undirected graph which is $k$ -regular and has girth $g$ . The least number is denoted by $c(k, g)$ and the $(k, g)$ -graphs with $c(k, g)$ vertices are called cages. As we saw before, besides the generalized polygons of order $q$ , for some prime power $q$ , there are no know infinite families of cages (for a list of all known cages, see the survey by Excoo and Jajcay. ). And by the result of Feit and Higman on generalized polygons, we see that these infinite families have $g \in \{6, 8, 12\}$ . It turns out that we know a lot more about $c(k, g)$ for $g \in \{6, 8, 12\}$ than the general case, even when there is no known generalized polygon of order $k - 1$ , i.e., when $k - 1$ is not a prime power.

Let’s start with an example. For every prime power $q$ , we know that $c(q + 1, 6) = 2(q^2 + q + 1)$ by looking at the incidence graph of a finite projective plane (i.e., a generalized $3$ -gon) $\pi$ of order $q$ . Now pick a point $X$ in $\pi$ and a line $\ell$ through $X$ . Then observe that through each point $Y \neq X$ , there are exactly $q$ lines which do not contain $X$ : all the lines through $Y$ except the line $XY$ . Dually, every line $m \neq \ell$ contains exactly $q$ points which do not lie on $\ell$ : all points on $m$ except the intersection point of $\ell$ and $m$ . What this shows is that if we take the subgraph of the incidence graph of $\pi$ induced on the $q^2$ points not contained in $\ell$ and the $q^2$ lines not containing $X$ , then it is a $q$ -regular graph. Moreover, this graph has girth $6$ , which leave as an exercise to the reader. So, we have just constructed a $q$ -regular graph of girth $6$ with $2q^2$ vertices, proving that $\displaystyle c(q, 6) \leq 2q^2$ for all prime power $q$ .

In fact, we can do slightly better if we take $X \not\in \ell$ . We then take all the points distinct from $X$ which are not on $\ell$ , and all the lines distinct from $\ell$ which do not contain $X$ . This gives us a $q$ -regular subgraph on $2(q^2 - 1)$ vertices, proving $c(q, 6) \leq 2(q^2 - 1)$ (not a big improvement, I know). But is this the best that we can do by pursuing this idea of constructing $q$ -regular induced subgraphs?

Interestingly, there is something much better that can be done, if $q$ is a square. We can take the subgraph induced on the points and lines of $\pi$ which are not contained in a Baer subplane of $\pi$ . In the Desarguesian plane $\mathrm{PG}(2,q)$ , we can get a Baer subplane by restricting the co-ordinates of the points and lines to the subfield $\mathbb{F}_{\sqrt{q}}$ (similarly the real projective plane $\mathrm{PG}(2, \mathbb{R})$ is a Baer subplane of the complex projective plane $\mathrm{PG}(2, \mathbb{C})$ ). While every subfield of $\mathbb{F}_q$ gives rise to a subplane of $\mathrm{PG}(2,q)$ , the Baer subplane in particular has the following nice properties:

through every point outside the subplane there is a unique line of the subplane;
every line outside the subplane contains a unique point of the subplane;

In other words, the induced subgraph that we get on the points and lines not contained in the Baer subplane is $q$ -regular. This construction gives us $c(q, 6) \leq 2(q^2 + q + 1 - q - \sqrt{q} - 1) = 2(q^2 - \sqrt{q})$ , which is much better than the previous bound of $2(q^2 - 1)$ . But, this construction only works when $q$ is a square.

So now the natural question arises (as it always should!), is this the best that we can do? Interestingly, now the answer is yes. We have actually reached a theoretical lower bound on the size of a $q$ -regular induced subgraph in a projective plane of order $q$ . This is a consequence of the following result that tells us how small a $k$ -regular induced subgraph of a $d$ -regular bipartite graph be.

Theorem 1. Let $G = (L, R, E)$ be a $d$ -regular bipartite graph and let $\lambda$ be its second largest eigenvalue. Let $H$ be a $k$ -regular induced subgraph of $G$ . Then $|V(H)| \geq (k - \lambda)|V(G)|/(d + \lambda)$ .

Theorem 1 can be proved easily using the expander mixing lemma, which I discussed in a previous post. It is well known, and easy to show, that the second largest eigenvalue of the incidence graph of a generalized $n$ -gon of order $q$ is $\sqrt{q}, \sqrt{2q}$ and $\sqrt{3q}$ for $n = 3, 4$ and $6$ , respectively. The number of vertices in the incidence graphs of a generalized $n$ -gon is $q^2 + q + 1, (q + 1)(q^2 + 1)$ and $(q + 1)(q^4 + q^2 + 1)$ for $n = 3, 4$ and $6$ respectively. If we now substitute these values in Theorem 1, and note the factorisations $q^2 + q + 1 = (q + \sqrt{q} + 1)(q - \sqrt{q} + 1)$ , $q^2 + 1 = (q + \sqrt{2q} + 1)(q - \sqrt{2q} + 1)$ and $q^4 + q^2 + 1 = (q^2 + q + 1)(q + \sqrt{3q} + 1)(q - \sqrt{3q} + 1)$ (thanks Sam!), we get the following result.

Theorem 2. Let $G$ be the incidence graph of a generalized $n$ -gon of order $q$ , and let $H$ be a $(q + 1 - t)$ -regular induced subgraph, for some $t \geq 1$ . Then

$\displaystyle|V(G)| - |V(H)| \geq \begin{cases} 2t(q + \sqrt{q} + 1), & \text{if } n = 3;\\ 2t(q + 1)(q + \sqrt{2q} + 1), & \text{if } n = 4; \\ 2t(q+1)(q^2 + q + 1)(q + \sqrt{3q} + 1), & \text{if } n = 6. \end{cases}$

In particular, for $n = 3$ and $t = 1$ , we get $2(q^2 + q + 1) - |V(H)| \geq 2(q + \sqrt{q} + 1)$ , i.e., $V(H) \leq 2(q^2 - \sqrt{q})$ . Therefore, the construction using the Baer subplane is the best possible. In fact, for $n = 3$ and arbitrary $t$ , we have a construction using $t$ disjoint Baer subplanes (see Construction 3.7 here) which is sharp according to this new bound. So, the problem of looking at regular induced subgraphs is settled for projective planes. For generalized quadrangles and hexagons though, there is a lot more to be said. In collaboration with John Bamberg and Gordon Royle, I have obtained some new finite geometrical constructions which improve the bounds on $c(q, 8)$ and $c(q, 12)$ . We will discuss that in the next post.