# Geometric constructions of small regular graphs with girth 7

György Kiss111This research was supported in part by the Hungarian National
Research, Development and Innovation Office OTKA grant no. SNN 132625.

###### Abstract

We present simple, geometric constructions for small regular graphs of girth 7
from the incidence graphs of some generalized quadrangles. We obtain infinite
families of $(q-1)$-regular, $q$-regular and $(q+1)$-regular graphs of girth
7, for $q$ a prime power. Some of them have the smallest order known so far.

MSC: 05C035, 51E12
Keywords: cage problem, incidence graph, generalized quadrangle

##  1 Introduction, definitions and basic properties

The cage problem is a classical problem in extremal graph theory. In a regular
graph of degree $k$ and girth $g$ we ask for the minimum number of vertices.
Here we briefly summarize the most important results related to the problem.
For more details on cages we refer to the dynamic survey by Exoo and Jajcay
[11].

A $(k,g)$-graph is a $k$-regular graph with girth $g.$ A _$(k,g)$ -cage_ is a
$(k,g)$-graph of minimum order. It was proved by Erdős and Sachs [10] that
$(k,g)$-cages exist for every $k\geq 2$ and $g\geq 3.$ The order of a
$(k,g)$-cage is denoted by $n(k,g).$ For $k=2,$ the $(2,g)$-graphs are the
$g$-cycles, so $n(2,g)=g.$ From now on, we assume that $k\geq 3.$ A general
lower bound on $n(k,g),$ known as the Moore bound and denoted by $M(k,g)$,
depends on the parity of $g.$ It is obtained by counting the vertices whose
distance from a vertex (if $g$ is odd), or an edge (if $g$ is even) is at most
$\lfloor(g-1)/2\rfloor$.

$n(k,g)\geq
M(k,g)=\left\\{\begin{array}[]{ll}1+\sum_{i=0}^{(g-3)/2}k(k-1)^{i}=\frac{k(k-1)^{(g-1)/2}-2}{k-2},&\text{if
$k$ is odd,}\\\
2\sum_{i=0}^{(g-2)/2}(k-1)^{i}=\frac{2(k-1)^{g/2}-2}{k-2},&\text{if $k$ is
even,}\end{array}\right.$

Graphs attaining this bound are called Moore graphs. For $g=3$ and $4,$ Moore
graphs are the complete, and complete bipartite graphs, respectively. Moore
graphs are rare for $g>4$. When $g$ is even, then there exists a $k$-regular
Moore graph with girth $2r>4$ if and only if there exists a finite generalized
$r$-gon of order $(k-1,k-1),$ and the graphs are the incidence graphs of the
generalized polygons. When $g>4$ odd, then there exist Moore graphs only for
$g=5$ and $k=2,3,7$ and possibly $57.$

Several different constructions of small $(k,g)$-graphs were presented in the
last few decades. In most cases, $g=6,8$ or $12$ and the graph is related to
the incidence graph of a generalized $g/2$-gon. A comprehensive overview of
geometric constructions can be found in the paper by Damásdi, Héger and Szőnyi
[9].

For $g=5,$ some classes of graphs were constructed by careful manipulations of
the incidence graphs of finite projective planes. Some vertices are removed
from these $(q+1,6)$-cages, after that matchings or cycles are added to the
neighbours of the removed vertices to get back regularity. The first
construction due to Brown [8] who proved that if $q\geq 5$ is a prime power,
then $n(q+2,5)\leq 2q^{2}.$ More sophisticated methods were presented by Abreu
et al. [1], and Abajo and her co-authors in a series of papers [3, 4, 5]. The
exact orders of their $(k,5)$-graphs are a bit smaller than $2k^{2}$, but the
magnitude is still $2k^{2}$. Recently, Araujo-Pardo and Leemans [6] and
Araujo-Pardo, Kiss and Porupsánszki [7] presented a very simple geometric
construction for $(q+2,5)$-graphs whose order is $2q^{2}-2$.

For $g=7,$ only three infinite families of $(k,7)$-graphs whose order is
approximately twice the Moore bound (which is $k^{3}-k^{2}+k+1$) were known. A
more general construction of Lazebnik, Ustimenko and Woldar [13] results in
$(q,7)$-graphs of order $2q^{3},$ and $(q-1,7)$-graphs of order
$2q^{3}-2q^{2}$ for each odd prime power $q>3.$ The smallest $(q+1,7)$-graphs
known so far, were presented by Abreu et al. [2]. They proved that

$n(q+1,7)\leq\left\\{\begin{array}[]{ll}2q^{3}+q^{2}+2q,&\text{if $q\geq 4$ is
an even prime power,}\\\ 2q^{3}+2q^{2}-q+1,&\text{if $q\geq 5$ is an odd prime
power.}\end{array}\right.$

In this paper, constructions of $(k,7)$-graph for $k=q-1,q,q+1$ are given for
each prime power $q>3.$ The main idea is the same as described in the previous
paragraph, but our method is purely geometric. We choose a beautiful geometric
substructure of a suitable generalized quadrangle. After that delete the set
of the corresponding vertices from the incidence graph. Finally, again using
the geometric properties, define some new edges. For $k=q-1$ and $k=q$ and
large $q,$ these graphs are the smallest $(k,7)$-graphs known so far.
Comparing the orders of the $(q+1,7)$-graphs presented in Theorems 8 and 11
and those constructed by Abreu et al., they are the same if $q$ is even, and
the orders of the ones we made are slightly larger if $q$ is odd. However, our
construction can be described much more briefly and is much simpler.

For a detailed introduction to generalized polygons and the concepts from
finite geometries we use can be found for example in [12] and [15]. In
particular, for generalized quadrangles we also refer the book [14]. Here we
give only the most necessary definitions.

A finite _generalized quadrangle_ of order $(s,t)$, shortly a $GQ(s,t),$ is a
point-line incidence structure which satisfies the following axioms:

  * •

for any two distinct points, there is at most one line incident with both;

  * •

every line is incident with exactly $s+1$ points;

  * •

every point is incident with exactly $t+1$ lines;

  * •

for every point $P$ and every line $\ell$ not incident with $P$, there is
exactly one line through $P$ which intersects $\ell$.

The _incidence graph_ , also called as the _Levi graph_ , of a point-line
incidence structure is a bipartite graph whose bipartition sets correspond to
the set of points and set of lines, respectively, and there is an edge between
two vertices if and only if the corresponding point is incident with the
corresponding line. Throughout this paper, if $G$ is an incidence graph, then
its vertices will be called points and lines, and the type of a vertex is
either point or line, according to whether they correspond to a point or a
line of the geometric structure.

##  2 The constructions

We use four families of generalized quadrangles. These are $\mathcal{W}(q),$
$\mathcal{T}_{2}(\mathcal{O}),$ $\mathcal{T}_{2}^{*}(\mathcal{H}),$ and
$\mathcal{Q}(4,q)$. Each of them is a so-called projective GQ, which means
that there exists a finite projective space $\mathcal{B}=\mathrm{PG}(d,q)$ for
which the point-set of the GQ is a subset of the set of points of
$\mathcal{B}$, the line-set of the GQ is a subset of the set of lines of
$\mathcal{B}$, and the incidence in the GQ is the one inherited from
$\mathcal{B}.$ We always consider $\mathrm{PG}(d,q)$ as
$\mathrm{AG}(d,q)\cup\Sigma_{\infty}.$ The points of $\mathrm{PG}(d,q)$ are
coordinatized by homogeneous coordinates $(x_{0}:x_{1}:\dots:x_{d})$ in the
usual way. The equation of $\Sigma_{\infty}$ is $X_{0}=0.$ Points and lines in
$\Sigma_{\infty}$ are called points at infinity and lines at infinity,
respectively. If $d=3,$ then in $\mathrm{AG}(3,q)$ we also use the Cartesian
coordinates, $X=X_{1}/X_{0},$ $Y=X_{2}/X_{0}$ and $Z=X_{3}/X_{0}.$ We say that
a line or a plane is horizontal, if it is parallel with the plane $Z=0.$

First, we present some statements that are fulfilled in all GQs.

######  Definition 1.

Let $G=(V,E)$ be a $t$-regular induced subgraph of the Levi graph of a
$GQ(s,s).$ A subset of vertices $W\subset V$ is called _deleteable_ if it has
the following two properties:

  * •

if $W$ contains two intersecting lines whose point at intersection is $P,$
then $W$ contains $P$ and all the $t$ lines through $P;$

  * •

if $W$ contains two collinear points whose joining line is $\ell,$ then $W$
contains $\ell$ and all the $t$ points on the line $\ell.$

The proof of the following proposition is straightforward.

######  Proposition 2.

Let $G=(V,E)$ be a $t$-regular induced subgraph of the Levi graph of a
$GQ(s,s),$ and $W\subset V$ be a deleteable subset. Then the subgraph
$G^{\prime}$ of $G$ induced by the set of vertices $V\setminus W$ contains two
types of vertices. If a vertex has a neighbour in $W,$ then its valency in
$G^{\prime}$ is $t-1$, while if a vertex has no neighbour in $W,$ then its
valency in $G^{\prime}$ is $t.$ If $t$ is odd, then the set of the valency
$t-1$ vertices of $G^{\prime}$ admits perfect matchings such that any new edge
joins either two points on a deleted line, or two lines through a deleted
point.

######  Lemma 3.

Let $G=(V,E)$ be a $t$-regular induced subgraph of the Levi graph of a
$GQ(s,s)$ where $s+1\geq t$ and $t$ is odd. Let $W$ be a deleteable subset of
vertices of $G.$ Let $G^{\prime}$ be the subgraph of $G$ induced by the set of
vertices $V\setminus W.$ Add a perfect matching of the valency $t-1$ vertices
of $G^{\prime}$ such that any new edge joins either two points on a deleted
line, or two lines through a deleted point. Then the new graph $\Gamma$ is
$t$-regular and its girth is at least 6.

Moreover, if $\mathcal{C}$ is a $6$-cycle in $\Gamma,$ then $\mathcal{C}$
contains exactly two new edges and $\mathcal{C}$ can be given either as
$u_{1}v_{2}v_{3}u_{4}v_{5}v_{6}$ or $u_{1}v_{2}v_{3}u_{4}u_{5}v_{6}$ where the
vertices denoted by $u_{i}$ are of the same type and the vertices denoted by
$v_{j}$ are of the other type.

###### Proof.

By Proposition 2, the required perfect matching exists, there is exactly one
new edge through each neighbour of a deleted vertex, hence $\Gamma$ is
$t$-regular.

Suppose that $\Gamma$ contains a cycle $\mathcal{C}$ of length $\ell\leq 6$.
The girth of $G$ is $8,$ so $\mathcal{C}$ must contain some new edges. There
is at most one new edge through any vertex of $\Gamma,$ so $\mathcal{C}$
cannot contain 3 consecutive vertices of the same type.

Hence if $\ell\leq 5,$ then $\mathcal{C}$ contains at most 2 new edges. If
$xy$ is a new edge of $\Gamma,$ then, by definition, there exists a vertex
$z\in W$ such that both $xz$ and $zy$ are edges in $G.$ Changing the the new
edge(s) of $\Gamma$ to path(s) of length 2 in $G,$ the $\ell$-cycle
$\mathcal{C}$ results in a cycle $\mathcal{C}^{\prime}$ of length
$\ell^{\prime}\leq\ell+2\leq 7$ in $G,$ a contradiction.

Now, let $\mathcal{C}=u_{1}v_{2}v_{3}u_{4}w_{5}w_{6}$ be a $6$-cycle in
$\Gamma.$ We may assume without loss of generality that the vertices denoted
by $v_{i}$ are of the same type, hence the vertices denoted by $u_{j}$ are of
the other type. If $w_{5}$ and $u_{4}$ are the same type, then $w_{6}$ must be
other type. So $\mathcal{C}$ contains the two new edges $v_{2}v_{3}$ and
$u_{4}w_{5},$ one of the new edges joins two points, the other joins two
lines. If $w_{5}$ and $u_{4}$ are different types and $w_{6}$ is the same type
as $w_{5},$ then $\mathcal{C}$ contains the two new edges edges $v_{2}v_{3}$
and $w_{5}w_{6}.$ The four vertices on the two new edges are of the same type.
Finally, if $w_{5}$ and $u_{4}$ are of different types and $w_{6}$ is the same
type as $u_{4},$ then $\mathcal{C}$ contains the two new edges edges
$v_{2}v_{3}$ and $w_{6}u_{1}.$ In this case one of the new edges joins two
points, the other joins two lines. ∎

######  Lemma 4.

Let $G$ be a $k$-regular induced subgraph of the Levi graph of a generalized
quadrangle $\mathcal{Q}$ of order $(s,s).$ Suppose that $k\geq 7$ and
$\mathcal{Q}$ contains a $k\times k$ grid $\mathcal{G}.$ Let
$\\{e_{1},e_{2},\dots,e_{k}\\}$ and $\\{f_{1},f_{2},\dots,f_{k}\\}$ denote the
two sets of pairwise non-intersecting lines of $\mathcal{G},$ and let
$P_{i,j}$ be the point of intersection of the lines $e_{i}$ and $f_{j}.$
Delete the $2k$ lines of $\mathcal{G}$ from $G.$ After that add $k\times k$
new edges joining the pairs of points $(P_{i,j},P_{i,j+1})$ and
$(P_{i,k},P_{i,1})$ for all $i=1,2,\dots,k$ and $j=1,2\dots,k-1.$ Denote the
new graph by $\Gamma$. Then $\Gamma$ is $k$-regular and its girth is at least
7.

###### Proof.

The proof is similar to the proof of the previous lemma.

For any fixed $i,$ the new edges among the vertices $P_{i,m}$ form a cycle of
length $k.$ So there are exactly two new edges through each point of
$\mathcal{G},$ hence $\Gamma$ is $k$-regular.

Suppose that $\Gamma$ contains a cycle $\mathcal{C}$ of length $\ell\leq 6$.
The girth of $G$ is $8,$ so $\mathcal{C}$ must contain some new edges. Since
$k>6,$ therefore $\mathcal{C}$ cannot consists of only new edges. If
$u_{1}u_{2}\dots u_{i}$ is the only arc of consecutive new edges in
$\mathcal{C}$, then $u_{1}$ and $u_{i}$ are collinear points in $\mathcal{Q}$,
both are incident with a line $v.$ Thus replacing $u_{1}u_{2}\dots u_{i}$ by
$u_{1}vu_{i}$ in $\mathcal{C}$ results in a cycle $\mathcal{C}^{\prime}$ of
length $\ell^{\prime}\leq\ell+1\leq 7$ in $G,$ a contradiction. Hence
$\mathcal{C}$ must contain at least two non-consecutive new edges. This
implies that $\mathcal{C}$ is a $6$-cycle, and it consists of the vertices
$u_{1}u_{2}v_{3}u_{4}u_{5}v_{6}$ where each $u_{i}$ denotes a point and each
$v_{j}$ denotes a line. So, by the definition of the new edges, $u_{2}$ and
$u_{4}$ are points on two non-intersecting lines of $\mathcal{G}.$ If
$u_{2}=P_{i,m}$ and $u_{4}=P_{j,n},$ with $i\neq j,$ then for $m\neq n$ they
are not collinear in $G$, while for $m=n$ they are on the deleted line
$f_{m}.$ In both cases, they do not have a common neighbour in $\Gamma.$

This contradiction proves the statement. ∎

Let $k>2$ be an even integer and consider the $k\times(k-1)$ part of the plane
lattice of integers

$\mathcal{G}=\\{(i,j)\colon 1\leq i\leq k-1,\,1\leq j\leq k\\}.$

######  Definition 5.

A perfect matching of the set of vertices of $\mathcal{G}$ is _rectangle-
free,_ if the four vertices of no two edges form a rectangle on the plane.

######  Lemma 6.

$\mathcal{G}$ admits a rectangle-free matching.

###### Proof.

Label the vertices of the complete graph $K_{k}$ by the natural numbers
$1,2,\dots,k$ and let $\mathcal{F}=\\{F_{1},F_{2},\dots,F_{k-1}\\}$ be a one-
factorization of $K_{k}$. Define a matching on $\mathcal{G}$ in the following
way. The points $(i_{1},j_{1})$ and $(i_{2},j_{2})$ form a pair if and only if
$i_{1}=i_{2}$ and the edge $j_{1}j_{2}$ of $K_{k}$ belongs to the one-factor
$F_{i_{1}}.$

By definition, this matching contains $k(k-1)/2$ edges, all of them are
vertical. The edges on a fixed vertical line of the lattice (say the line with
equation $X=i$), correspond to the $k/2$ edges contained in a fixed one-factor
of $\mathcal{F}$ (in particular, $F_{i})$. Each one-factor contains all
vertices of $K_{k},$ so the matching is perfect. If there were a rectangle in
the matching, say $(i_{1},j_{1})(i_{1},j_{2})$ and
$(i_{2},j_{1})(i_{2},j_{2}),$ then the edge $j_{1}j_{2}$ of $K_{k}$ would
belong to both one-factors $F_{i_{1}}$ and $F_{i_{2}},$ a contradiction. ∎

######  Lemma 7.

Let $G$ be a $k$-regular induced subgraph of the Levi graph of a generalized
quadrangle $\mathcal{Q}.$ Suppose that $k$ is even and $\mathcal{Q}$ contains
a $k\times(k-1)$ grid. Let $\\{e_{1},e_{2},\dots,e_{k}\\}$ and
$\\{f_{1},f_{2},\dots,f_{k-1}\\}$ denote the two sets of pairwise non-
intersecting lines of $\mathcal{G},$ and let $P_{i,j}$ be the point of
intersection of the lines $e_{i}$ and $f_{j}.$ Delete the $k-1$ pairwise non-
intersecting lines of the grid and let $G^{\prime}$ denote the incidence graph
of the remaining structure. Identify the points $P_{i,j}$ with the lattice
points $(i,j)$ and consider the rectangle-free perfect matching constructed in
Lemma 6. Add the corresponding new edges to $G^{\prime}$. Let $\Gamma$ denote
the graph $G^{\prime}$ extended by these new edges. Then $\Gamma$ is a
$(k,g)$-graph with $g\geq 7.$

###### Proof.

There is one new edge through each point of $G^{\prime}$, so $\Gamma$ is
$k$-regular. Any new edge joins two points on a deleted line, so we can apply
Lemma 3. This gives that the girth of $\Gamma$ is at least 6, and any
$6$-cycle contains two new edges.

Suppose that $\mathcal{C}$ is a $6$-cycle. Both new edges of $\mathcal{C}$
join two points of $G^{\prime}$, so again by Lemma 3,
$\mathcal{C}=(a,B,C,d,E,F)$ where uppercase letters denote points of
$G^{\prime}$. This means that $B,$ $C$, $E$ and $F$ form a rectangle in
$G^{\prime}$, contradicting to the fact that we defined a rectangle-free
matching. ∎

In the following theorems, we construct small regular graphs using the unique,
specific properties of each GQ.

######  Theorem 8.

Let $q\geq 7$ be a prime power. Then

$n(k,7)\leq\left\\{\begin{array}[]{ll}2k^{3}-4k^{2}+2k,&\text{if $k=q+1$,}\\\
2k^{3}-2k,&\text{if $k=q$.}\end{array}\right.$

###### Proof.

The starting point of the construction is a $k$-regular induced subgraph $G$
of the Levi graph of a GQ in both cases. We apply Lemma 4, and show that the
girth of the extended graph $\Gamma$ is exactly $7.$

$(i)$: If $k=q+1$, then take a parabolic quadric $\mathcal{P}$ in
$\mathrm{PG}(4,q).$ The points and lines entirely contained in $\mathcal{P}$
form the classical generalized quadrangle $\mathcal{Q}(4,q)$, whose order is
$(q,q)$. Let $\Sigma$ be a hyperplane such that $\mathcal{P}\cap\Sigma$ is a
hyperbolic quadric $\mathcal{H}$ (e.g: if $\mathcal{P}$ has equation
$X_{0}^{2}+X_{1}X_{2}+X_{3}X_{4}=0,$ then the equation of $\Sigma$ could be
$X_{0}=0$). Then $\mathcal{P}$ contains the $2(q+1)$ lines and $(q+1)^{2}$
points of $\mathcal{H}$, and these points and lines form a $(q+1)\times(q+1)$
grid. Let $G$ be the Levi graph of $\mathcal{Q}(4,q)$, take
$\mathcal{G}=\mathcal{H}$ and apply Lemma 4. The constructed graph $\Gamma$ is
a $(q+1)$-regular graph on

$2q^{3}+2q^{2}=2(q+1)^{3}-4(q+1)^{2}+2(q+1)$

vertices and its girth is at least $7$. The order of $\Gamma$ is less than
$M(q+1,8)=2(q^{3}+q^{2}+q+1),$ so its girth is $7.$

$(ii)$: If $k=q$, then take
$\mathrm{PG}(3,q)=\mathrm{AG}(3,q)\cup\Sigma_{\infty}$ and let $\mathcal{A}$
be a $q$-arc in $\Sigma_{\infty}.$ We define a point-line incidence geometry
$\mathcal{S}=(\mathcal{P},\mathcal{L},\mathrm{I})$ in the following way. The
points of $\mathcal{S}$ are the points of $\mathrm{AG}(3,q),$ the lines of
$\mathcal{S}$ are those affine lines of $\mathrm{PG}(3,q)$ whose point at
infinity belongs to $\mathcal{A},$ and the incidence is the same as in
$\mathrm{AG}(3,q).$ Let $G$ denote the Levi graph of $\mathcal{S}.$

When $q$ is odd, then there exists a point $P$ in $\Sigma_{\infty}$ such that
$\mathcal{O}=\mathcal{A}\cup\\{P\\}$ is an oval. This oval defines the GQ
$\mathcal{T}_{2}(\mathcal{O}),$ and by definion, $G$ is a $q$-regular induced
subgraph of the Levi graph of $\mathcal{T}_{2}(\mathcal{O}).$ Similarly, when
$q$ is even, then there exist two points $P$ and $R$ in $\Sigma_{\infty}$ such
that $\mathcal{H}=\mathcal{A}\cup\\{P,R\\}$ is a hyperoval. This hyperoval
defines the GQ $\mathcal{T}_{2}^{*}(\mathcal{H}),$ and by definion, $G$ is a
$q$-regular induced subgraph of the Levi graph of
$\mathcal{T}_{2}^{*}(\mathcal{H}).$ In both cases, let $AB$ be a secant line
of $\mathcal{A}$ and $\Pi$ be an affine plane whose line at infinity is $AB.$
The $q$ lines of $\mathcal{S}$ through $A$ form a class of parallel lines in
$\Pi,$ and so do the $q$ lines of $\mathcal{S}$ through $B,$ too. Hence the
$2q$ lines of $\mathcal{S}$ in $\Pi$ form a $q\times q$ grid.

We can apply Lemma 4. The constructed graph $\Gamma$ is a $q$-regular graph on
$2q^{3}-2q$ vertices and its girth is at least $7$. We show that $\Gamma$
contains $7$-cycles. Let $C,$ $D,$ $E$ be three distinct points of
$\mathcal{A}\setminus\\{A,B\\}.$ Since $q\geq 7,$ these points exist. Take two
affine points $U_{1}$ and $U_{2}$ on a line through $A.$ Then $C,\,E$ and $D$
are not collinear, hence the plane $\langle U_{1},C,E\rangle$ intersects the
line $U_{2}D$ in a single point $U_{4}.$ The lines $U_{1}C$ and $U_{4}E$ are
coplanar, so they have a unique affine point of intersection, $U_{6}.$ Let
$u_{i}$ denote the vertex in $\Gamma$ that corresponds to the point $U_{i},$
and let $v_{3},\,v_{5}$ and $v_{7}$ be the vertices corresponding to the lines
$U_{2}U_{4},\,U_{4}U_{6}$ and $U_{6}U_{1},$ respectively. Then, by definition,
$u_{1}u_{2}v_{3}u_{4}v_{5}u_{6}v_{7}$ is a $7$-cycle in $\Gamma.$ ∎

We can combine Part $(i)$ of the previous theorem and Lemma 7. This results in
larger graphs than the previous theorem, but it works also for $q=3$ and $5.$

######  Theorem 9.

Let $q\geq 3$ be an odd prime power. Then

$n(q+1,7)\leq 2q^{3}+2q^{2}+q+2.$

###### Proof.

Let $\mathcal{P},$ $Q(4,q),$ $\mathcal{H}$ and $G$ be the same as in the proof
of Theorem 8. Let $\ell$ be a line that is contained in $\mathcal{H}$. Then
the lines of $\mathcal{H}$ except $\ell$ form a $(q+1)\times q$ grid
$\mathcal{G}.$ Now, apply Lemma 7. The constructed graph $\Gamma$ is a
$(q+1)$-regular graph on $2q^{3}+2q^{2}+q+2$ vertices and its girth is at
least $7$. The order of $\Gamma$ is less than $M(q+1,8)=2(q^{3}+q^{2}+q+1),$
so its girth is $7.$ ∎

The construction given in Part $(iii)$ of Theorem 8 can be extended from $q-1$
to all even numbers $k<q.$ This gives a slight improvement on the general
upper bound of Lazebnik, Ustimenko and Woldar [13].

######  Theorem 10.

Let $k\geq 4$ be an even integer and let $q$ denote the smallest prime power
for which $k\leq q.$ Then

$n(k,7)\leq 2kq^{2}-q.$

In particular, if $q$ is odd, then

$n(q-1,7)\leq 2q^{3}-2q^{2}-q=2(q-1)^{3}+4(q-1)^{2}+(q-1)-1.$

###### Proof.

The construction is similar to the one presented in the proof of Theorem 8,
Part $(ii).$ Consider $\mathrm{PG}(3,q)$ as
$\mathrm{AG}(3,q)\cup\Sigma_{\infty}.$ Take an oval $\mathcal{O}$ in
$\Sigma_{\infty}$. If $q$ is even, then extend it to a hyperoval
$\mathcal{H}=\mathcal{O}\cup\\{N\\}$ where $N$ denotes the nucleus of
$\mathcal{O}.$ Choose a line $e$ in $\Sigma_{\infty}$ that is external to
$\mathcal{O},$ and does not contain $N$ if $q$ is even. Pick up four points
$C,\,D,\,M_{1},\,M_{2}$ of $\mathcal{O}.$ Take a line $\ell$ through $C$ and
two affine points $U_{1},\,U_{2}$ on $\ell.$ For $i=1,2$ let $f_{i}$ denote
the line $U_{i}M_{i}.$ Then $f_{1}$ and $f_{2}$ are skew lines in
$\mathrm{PG}(3,q)$ and none of them contains $C.$ Let $g$ be the line of
intersection of the two planes $\langle f_{i},C\rangle.$ Then $g$ and $f_{i}$
are coplanar, so there exists the affine point of intersection
$R_{i}=f_{i}\cap g.$ Choose $q-k$ parallel affine planes
$\Sigma_{1},\Sigma_{2},\dots,\Sigma_{q-k}$ such that for all $j=1,2,\dots,q-k$
the line at infinity of $\Sigma_{j}$ is $e,$ and
$\Sigma_{j}\cap\\{U_{1},U_{2},R_{1},R_{2}\\}=\emptyset.$ Then each affine line
whose point at infinity belongs to $\mathcal{O}$ intersects $\Sigma_{j}$ in a
unique affine point. For $q$ even, it is also true for the affine lines whose
point at infinity is $N.$ Finally, choose $q+1-k$ points
$F_{1},F_{2},\dots,F_{q+1-k}$ points of
$\mathcal{O}\setminus\\{C,D,M_{1},M_{2}\\}.$ Since $4\leq k<q,$ the planes
$\Sigma_{j}$ and the points $F_{j}$ exist.

Change the definition of $\mathcal{S}$ such that the set of its points
consists of the $kq^{2}$ points of

$\mathrm{AG}(3,q)\setminus\left(\bigcup_{j=1}^{q-k}\Sigma_{j}\right),$

and the lines of $\mathcal{S}$ are those affine lines whose point at infinity
belongs to the set

$\mathcal{O}\setminus\\{F_{1},F_{2},\dots,F_{q+1-k}\\}.$

Then the Levi graph $G$ of $\mathcal{S}$ is a $k$-regular induced subgraph of
the Levi graph of $\mathcal{T}_{2}(\mathcal{O})$ or
$\mathcal{T}_{2}^{*}(\mathcal{H}),$ according to whether $q$ is odd or even.

Let $c$ be the tangent to $\mathcal{O}$ at $C,$ and $\Pi$ be an affine plane
whose line at infinity is $c.$ Then there are $q$ lines of $\mathcal{S}$ in
$\Pi,$ they form a parallel class. Hence the corresponding set of vertices in
$G$ is a deleteable set, $W.$ We can apply Lemma 3 to $G$ and $W.$. The
constructed graph $\Gamma$ is a $k$-regular graph on

$kq^{2}+(kq^{2}-q)=2kq^{2}-q$

vertices.

Suppose that $\mathcal{C}$ is a $6$-cycle in $\Gamma.$ Then $\mathcal{C}$
contains two new edges, both of them join two points of $G$, because there is
no new edge among the lines. So $\mathcal{C}=(E,F,v,J,K,w),$ where the capital
letters denote points of $G$, and $v$ and $w$ denote lines. Hence $F$ and $J$
are collinear points of $\mathcal{S}$. The lines $EF$ and $JK$ pass on $C,$ so
the line joining the points $F$ and $J$ in $\mathrm{PG}(3,q)$ does not contain
$C.$ This implies that $U=FJ\cap\Sigma_{\infty}$ is a point of
$\mathcal{O}\setminus\\{C,F_{1},F_{2},\dots,F_{q+1-k}\\}.$ This is a
contradiction, because $U$ is on the line $c=\Pi\cap\Sigma_{\infty},$ and $c$
is the tangent to $\mathcal{O}$ at $C$. So the girth of $\Gamma$ is at least
$7.$

Finally, by definition, the vertices corresponding to the points and lines
$(U_{1},U_{2},f_{2},R_{2},g,R_{1},f_{1})$ form a $7$-cycle in $\Gamma$. This
completes the proof. ∎

The following theorem was first proved by Abreu et al. [2]. They used
$\mathcal{Q}(4,q)$ for their construction. Now, we present a much simpler
proof, which is based on exploiting the geometric properties of
${\mathcal{W}}(q)$. Note that $\mathcal{Q}(4,q)$ and ${\mathcal{W}}(q)$ are
isomorphic if $q$ is even.

######  Theorem 11.

Let $q\geq 4$ be an even prime power. Then

$n(q+1,7)\leq 2q^{3}+q^{2}+2q.$

###### Proof.

The classical generalized quadrangle ${\mathcal{W}}(q)$ of order $(q,q)$
arises from a null-polarity $\pi$ in $\mathrm{PG}(3,q)$, i.e., a polarity
given by the standard form $X_{1}Y_{0}-X_{0}Y_{1}+X_{3}Y_{2}-X_{2}Y_{3}=0$.
All points of PG$(3,q)$ are points of ${\mathcal{W}}(q)$. The lines of
${\mathcal{W}}(q)$ are the self-conjugate lines of $\mathrm{PG}(3,q)$ with
respect to the null-polarity $\pi$. The line joining the points
$A=(a_{0}:a_{1}:a_{2}:a_{3})$ and $B=(b_{0}:b_{1}:b_{2}:b_{3})$ is self-
conjugate if and only if $a_{1}b_{0}-a_{0}b_{1}+a_{3}b_{2}-a_{2}b_{3}=0$. The
polar plane $A^{\pi}$ of the point $A$ has equation
$a_{1}X_{0}-a_{0}X_{1}+a_{3}X_{2}-a_{2}X_{3}=0$, while the pole of the plane
having equation $c_{0}X_{0}+c_{1}X_{1}+c_{2}X_{2}+c_{3}X_{3}=0$ is the point
$(c_{1}:-c_{0}:c_{3}:-c_{2}).$ The self-conjugate lines through the point $A$
form a pencil of lines in the plane $A^{\pi}.$ For $q$ even, the equations are
simpler, because in this case $-1=1.$

Let $G=(V,E)$ be the Levi graph of ${\mathcal{W}}(q)$. Take the subset
$W\subset V$ that consists of the following vertices: the line
$X_{0}=X_{3}=0$, all of its points, and all self-conjugate lines through the
$q-1$ points $\\{(0:1:t:0)\colon 0\neq t\in\mathrm{GF}(q)\\}.$ By definition,
$W$ is a deleteable subset. Let $G^{\prime}$ be subgraph of $G$ induced by the
set of vertices $V\setminus W.$ Then the order of $G$ is

$2q^{3}+2q^{2}+2q+2-\left((1+(q+1)+(q-1)q\right)=2q^{3}+q^{2}+2q.$

The polar plane of the point $E_{1}$ is $\Sigma_{\infty}.$ Let
$\ell_{\infty,t}$ denote the line with set of equations
$\\{X_{0}=0,\,X_{2}=tX_{3}\\}$. Then the set of the non-deleted self-conjugate
lines through $E_{1}$ is

$\mathcal{L}_{1}=\\{\ell_{\infty,t}\colon t\in\mathrm{GF}(q)\\}.$

Similarly, the polar plane of the point $E_{2}$ is the plane
$E_{2}^{\pi}\colon X_{3}=0.$ If $\ell_{t,\infty}$ denote the line with set of
equations $\\{X_{3}=0,\,X_{1}=tX_{0}\\},$ then the set of the non-deleted
self-conjugate lines through $E_{2}$ is

$\mathcal{L}_{2}=\\{\ell_{t,\infty}\colon t\in\mathrm{GF}(q)\\}.$

We define a matching of the elements of $\mathcal{L}_{1}$ as
$\ell_{\infty,t}\Longleftrightarrow\ell_{\infty,t+1},$ and a matching of the
elements of $\mathcal{L}_{2}$ as
$\ell_{t,\infty}\Longleftrightarrow\ell_{t+1,\infty}.$

Now, we define matchings of the non-deleted affine points on the deleted
affine lines. If $t\neq 0,$ then the equation of $(0:1:t:0)^{\pi}$ is
$X_{0}+tX_{3}=0,$ it intersect $\mathrm{AG}(3,q)$ in a horizontal plane
$\mathcal{H}_{1/t}$ with equation $Z=1/t.$ The self-conjugate lines in
$\mathcal{H}_{1/t}$ have point at infinity $(0:1:t:0)^{\pi},$ so the equations
of the deleted lines in $\mathcal{H}_{1/t}$ can be written as
$\ell_{t,k}\colon Y=tX+k$ where $k$ runs on the elements of $\mathrm{GF}(q).$
For a fixed pair $(t,k)$ we define the matching of the $q$ affine points on
$\ell_{t,k}$ in the following way:

$P\colon\left(p,tp+k,\frac{1}{t}\right)\Longleftrightarrow
P^{\prime}\colon\left(p+1,tp+t+k,\frac{1}{t}\right).$

Apply Lemma 3 to the graph $G$ and the matchings defined in the previous two
paragraphs. The extended graph $\Gamma$ is $(q+1)$-regular and its girth is at
least $6.$

Suppose that $\mathcal{C}$ is a $6$-cycle in $\Gamma.$ Then, by Lemma 3, there
are three possibilities:

  1. 1.

$\mathcal{C}=(A,b,c,D,e,f)$,

  2. 2.

$\mathcal{C}=(A,b,c,D,E,f)$,

  3. 3.

$\mathcal{C}=(a,B,C,d,E,F)$,

where uppercase letters denote points and lowercase letters denote lines of
$\mathcal{W}(q).$

In Case 1, the lines $b$ and $c$ belong to $\mathcal{L}_{1}$ or
$\mathcal{L}_{2}.$ In the former case, $A$ and $D$ are points of
$\Sigma_{\infty},$ hence the lines $e$ and $f$ also belong to
$\mathcal{L}_{1}.$ In the latter case, $A$ and $D$ are points of
$E_{2}^{\pi},$ hence the lines $e$ and $f$ also belong to $\mathcal{L}_{2}.$
In both cases, there were two lines of $\mathcal{L}_{i}$ through the point
$A,$ a contradiction.

In Case 2, the line $c$ belongs to $\mathcal{L}_{1}$ or $\mathcal{L}_{2}.$
Hence the point $D$ is either in $\Sigma_{\infty}$ or in $E_{2}^{\pi},$ and
$DE$ is a new edge through $D.$ This is a contradiction again, because there
are no new edges through the points of the planes $\Sigma_{\infty}$ and
$E_{2}^{\pi}.$

Finally, in Case 3, $BC$ and $EF$ are new edges, so none of these four points
are in $\Sigma_{\infty}\cup E_{2}^{\pi}.$ The line $d$ joins $C$ and $E,$ and
$d$ is a non-deleted self-conjugate line, hence it is not horizontal. This
implies that $C$ and $E$ are in different horizontal planes, thus without loss
of generality we may assume that $C=(a,ta+k,\frac{1}{t})$ and
$E=(b,sb+m,\frac{1}{s})$ where $s\neq t.$ Then $B=(a+1,ta+t+k,\frac{1}{t})$
and $F=(b+1,sb+s+m,\frac{1}{s}),$ because $BC$ and $EF$ are new edges. The
line $d$ is self-conjugate if and only if

$a+b+\frac{ta+k}{s}+\frac{sb+m}{t}=0,$

while the line $a$ joins $B$ and $F,$ so it is self-conjugate if and only if

$a+1+b+1+\frac{ta+t+k}{s}+\frac{sb+s+m}{t}=0.$

If both lines were self-conjugate, then the two equations would imply

$\frac{t}{s}+\frac{s}{t}=0,\text{ hence }s=t,$

a contradiction again.

Hence there is no $6$-cycle in $\Gamma.$ The order of $\Gamma$ is less than
$M(q+1,8),$ so its girth is $7.$ The proof is complete. ∎

As a final note, we should mention that using similar methods, we can
construct relatively small $(q,11)$-graphs and $(q+1,11)$-graphs from the Levi
graph of the split Cayley generalized hexagon of order $(q,q).$ However, this
will be the subject of a subsequent paper.

## References

  * [1] M. Abreu, G. Araujo–Pardo, C. Balbuena and D. Labbate, Families of Small Regular Graphs of Girth 5, _Discrete Math._ 312 (2012), 2832–-2842.
DOI: 10.1016/j.disc.2012.05.020

  * [2] M. Abreu, G. Araujo–Pardo, C. Balbuena, D. Labbate and J. Salas, Small Regular Graphs of Girth 7, _Electron. J. Combin.._ 22 (2015), # P3.5.
DOI: 10.37236/4205

  * [3] E. Abajo G. Araujo, C. Balbuena and M. Bendala, New small regular graphs of girth 5, _Discrete Math._ 340 (2017), 1878–-1888.
DOI: 10.1016/j.disc.2017.03-020

  * [4] E. Abajo, C. Balbuena, M. Bendala and X. Marcote, Improving bounds on the order of regular graphs of girth 5, _Discrete Math._ 342 (2019), 2900–2910.
DOI: 10.1016/j.disc.2019.02.007

  * [5] E. Abajo and M. Bendala, Regular graphs of girth 5 from elliptic semiplanes of type C, _Discrete Math._ 344 (2021), paper 112343.
DOI: 10.1016/j.disc.2012.

  * [6] G. Araujo-Pardo and D. Leemans, Edge-girth-regular graphs arising from biaffine planes and Suzuki groups, _Discrete Math._ 345 (2022), Paper 112991.
  * [7] G. Araujo-Pardo, Gy. Kiss and I. Porupsánszki, On extremal (almost) edge-girth-regular graphs, submitted.
  * [8] W. G. Brown, On the non-existence of a type of regular graphs of girth 5, _Canad. J. Math._ 19 (1967), 644–648.
  * [9] G. Damásdi, T. Héger and T. Szőnyi, The Zarankiewicz problem, cages, and geometries, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 56 (2013) 3-37.
  * [10] P. Erdős and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.)  12 (1963) 251-257.
  * [11] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin., Dynamic Survey 16 (2008).
DOI: 10.37236/37

  * [12] Gy. Kiss and T. Szőnyi, _Finite Geometries,_ CRC Press, Taylor & Francis Group, 2019.
  * [13] F. Lazebnik, V. A. Ustimenko and A. J. Woldar, New upper bounds on the order of cages, _Electron. J. Combin_ 4 (1997), no. 2, # R13.
DOI: 10.37236/1328

  * [14] S. E. Payne and J. A. Thas, _Finite Generalized Quadrangles_ , Second Ed., EMS Publishing House, 2009.
  * [15] H. Van Maldeghem, Generalized Polygons, Birkhäuser, Springer, Basel (1998).

György Kiss: Department of Geometry and HUN-REN-ELTE Geometric and Algebraic
Combinatorics Research Group, Eötvös Loránd University, 1117 Budapest, Pázmány
s. 1/c, Hungary; and Faculty of Mathematics, Natural Sciences and Information
Technologies, University of Primorska, Glagoljaška 8, 6000 Koper, Slovenia;
e-mail<EMAIL_ADDRESS>


3. 3.

Let $j^{*}_{\min}$ be the smallest index such that
$\min\limits_{j\in[n]}g(j)=g(j^{*}_{\min})$. Then

$\displaystyle\tau_{j^{*}_{\min}}<\min_{j\in[n]}g(j).$

  4. 4.

Let $j^{*}$ be any index such that $\min\limits_{j\in[n]}g(j)=g(j^{*}).$ Then

$\displaystyle\tau_{j^{*}}\leq\min_{j\in[n]}g(j).$

###### Proof.

We first prove the first inequality. Suppose that $j^{*}_{\max}<n$. Then
$g(j^{*}_{\max})<g(j^{*}_{\max}+1)$, meaning that

$\displaystyle\left(\sum_{i=1}^{j^{*}_{\max}}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\max}\right)<\left(\sum_{i=1}^{j^{*}_{\max}+1}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\max}+1\right).$

This implies the following series of inequalities:

$\displaystyle\left(\sum_{i=1}^{j^{*}_{\max}+1}\frac{1}{\tau_{i}}\right)\left(S+j^{*}_{\max}\right)<\left(\sum_{i=1}^{j^{*}_{\max}}\frac{1}{\tau_{i}}\right)\left(S+j^{*}_{\max}+1\right)$
$\displaystyle\Leftrightarrow\quad\frac{1}{\tau_{(j^{*}_{\max}+1)}}\left(S+j^{*}_{\max}\right)<\sum_{i=1}^{j^{*}_{\max}}\frac{1}{\tau_{i}}$
$\displaystyle\Leftrightarrow\quad\tau_{(j^{*}_{\max}+1)}>\left(\sum_{i=1}^{j^{*}_{\max}}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\max}\right)=g(j^{*}_{\max})=\min_{j\in[n]}g(j).$

The proof of the second inequality is the same, but with non-strict
inequalities. To prove the third inequality, first suppose that
$j^{*}_{\min}=1$. Then
$g(j^{*}_{\min})=\tau_{j^{*}_{\min}}\left(S+1\right)>\tau_{j^{*}_{\min}}$ as
needed. On the other hand, $j^{*}_{\min}>1$ implies

$\displaystyle g(j^{*}_{\min})<g(j^{*}_{\min}-1)$
$\displaystyle\Leftrightarrow\left(\sum_{i=1}^{j^{*}_{\min}}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\min}\right)<\left(\sum_{i=1}^{j^{*}_{\min}-1}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\min}-1\right)$
$\displaystyle\Leftrightarrow\quad\left(\sum_{i=1}^{j^{*}_{\min}-1}\frac{1}{\tau_{i}}\right)\left(S+j^{*}_{\min}\right)<\left(\sum_{i=1}^{j^{*}_{\min}}\frac{1}{\tau_{i}}\right)\left(S+j^{*}_{\min}-1\right)$
$\displaystyle\Leftrightarrow\quad\sum_{i=1}^{j^{*}_{\min}}\frac{1}{\tau_{i}}<\frac{1}{\tau_{j^{*}_{\min}}}\left(S+j^{*}_{\min}\right)$
$\displaystyle\Leftrightarrow\quad\tau_{j^{*}_{\min}}<\left(\sum_{i=1}^{j^{*}_{\min}}\frac{1}{\tau_{i}}\right)^{-1}\left(S+j^{*}_{\min}\right)=\min_{j\in[n]}g(j).$

The proof of the fourth inequality is the same, but with non-strict
inequalities. ∎