I recently finished my research visit to UWA where I worked with John Bamberg and Gordon Royle on some finite geometrical problems related to cages. So this seems like the right time for me to write a blog post about these graphs.
A 
Say 
The argument above generalises to show that for odd 
Using spectral methods, it has been shown that the Moore graphs can only exist in the following cases: (a) 
Since there are very special values of
Find the smallest number of vertices 
The 
Therefore, a natural problem that mathematicians have worked on is to construct small 
For specific values of
Further Reading
[1] Dynamic Cage Survey by Geoffrey Excoo and Robert Jajcay.
[2] The cage problem by Michael Giudici.
[3] Balaban 10-cage | Visual Insight by John Baez.
* A simpler proof using Cayley graphs was later given by Biggs. In both of these proofs we need the fact that for all 
be a semiregular bipartite graph with degrees 
and 
. Let 
and 
such that 
and 
. Define 
. Then we have
,
is the largest eigenvalue of 
is the second largest eigenvalue of 
is the total number of edges in 
(the eigenvalues of a bipartite graph are always symmetric around the origin). And more generally, the eigenvalues of the incidence graph of a 
design are 
. Therefore, applying expander mixing lemma to these graphs can potentially give some nice results in finite geometry. Let’s start with one of the classical results in the area of finite geometry and see how it can be proved using Lemma 1.
of points with the property that for every line 
of the plane we have 
. One of the central problems in the area of finite geometry has been to understand the possible sizes of a minimal blocking set, where a blocking set 
, which we a trivial blocking set. For a non-trivial minimal blocking set 
.
of 
such that 
since otherwise 
will also form a blocking set, contradicting the minimality of 
of lines in the projective plane with the property that (a) 
and (b) the number of edges between the sets 
. The number of points/lines in a projective plane of order 
. By applying Lemma 1, taking 
and defining 
, we get the following:
.
since 
, which helps us remove the mod sign in the inequality. We get
),
.
, we get
. 
-fold minimal blocking in a projective plane of order 
, and (b) through each point 
, there exists a line 
. We will prove that
.
. By getting rid of a few lines we can assume that 
(technically it should be 
, but it can be checked later that this won’t affect the proof). The number of incidences between 
since each line is incident with exactly 
.
.
must lie between the two roots of the quadratic equation 
, which gives us the required bound. 
, let 
be the largest value of 
where 
and 
such that there are no edges between 
and 
in the incidence graph of 
. Then for 
equal to the set of points in the finite projective space 
and 
equal to the set of 
is in fact a 
design with 
.
, has at most 
vertices. The polarity graph is defined by taking the points as vertices and making two points 
adjacent if and only if 
. These graphs were introduced by 
and define 
. Then we have
,
. This result can be proved in several ways (including 
points and 
lines in 
, but 
(1)
, does not really require any property of these planes over finite fields besides the fact that the points and lines form a 
be a 
and number of blocks 
and 
for the affine plane 
also form 
and 
. Let 
is the largest eigenvalue of 
. Note that for Theorem 1 we simply need to plug in the relevant values in Lemma 2 and ignore the 
term on the right hand side. I’ll sketch the proof of Haemers (see also Section 4.9 in 
be a real symmetric matrix with eigenvalues 
, and let 
be an 
real matrix satisfying 
. Let 
be the eigenvalues of the (real symmetric) matrix 
. Then we have 
for all 
.
, we say that the second sequence interlaces the first when 
(sometimes the term interlace is used only in the case of 
). Therefore, Lemma 1 tells us that the eigenvalues of the matrix 
be a partition of its vertices. Define the 
quotient matrix 
of the adjacency matrix 
to be average row sum of the block of 
and 
, i.e., the average number of edges from 
of the bipartite graph 
be the eigenvalues of 
be the eigenvalues of 
and 
. (Note that the eigenvalues of both 
, we get 
. Since 
is equal to the product of the eigenvalues of 
.
. 
, for arbitrary 
and 
containing a subhexagon”,on 
and let 
or its dual 
. Then the following holds for any generalized hexagon 
that contains 
and 
, then 
.
(when 
). But since we are nowhere near classifying finite generalized polygons, this problem seems to be pretty hard in general. Also, existence/non-existence of semi-finite generalized polygons is a major open problem in incidence geometry which has only been resolved for specific cases of generalized quadrangles (when every line has 
points on it). So for now we satisfy ourselves with this small contribution.
contained in a generalized hexagon 
points on it. It directly follows from the axioms of a generalized hexagon that every point of 
from 
points of the third type. Then our lemma says that for any two points 
on 
points. The lemma is proved using a result of Bart (Proposition 4.7 in 
or 
and thus obtain part (2) of our main result. Our check mostly consists of some clever computations in a computer model of these geometries as we do not really understand how semi-singular (or ovoidal) hyperplanes of split Cayley hexagons and their duals behave in general.
(a geometry that has 
points and 
we use the non-existence result proved by me and Ferdinand in a 
. The extra complication here is that 
. Moreover, it has 
and it seems like for larger cases we will need more ideas and a better understanding of these three types of hyperplanes in split Cayley hexagons and their duals. If in general one can prove that every semi-singular hyperplane of 
through a fixed point 
points on each line, containing 
, which arises from the incidence graph of the 
be a finite grid in 
where 
. Let ![f \in \mathbb{F}[t_1, \dots, t_n]](https://s0.wp.com/latex.php?latex=f+%5Cin+%5Cmathbb%7BF%7D%5Bt_1%2C+%5Cdots%2C+t_n%5D&bg=ffffff&fg=333333&s=0 "f \in \mathbb{F}[t_1, \dots, t_n]")
be an 
such that the set 
is nonempty (in other words, 
does not vanish on the entire grid). Then 
. Moreover, the bound is sharp.
denotes the minimum value of the product 
where 
‘s are integers satisfying 
and 
for all 
to be the finite field 
for all 
, see 
. Clearly, the minimum Hamming distance of this linear code is the minimum number of non-zeros a reduced polynomial of degree at most 
where 
, then this minimum is equal to 
, which is what Kasami-Lin-Peterson proved in 1968 (using more technical arguments involving 
in 
. Associate each hyperplane to the linear polynomial that defines it, and take the product of these linear polynomials. Then the set of points covered by the hyperplanes is equal to the set of zeros of this polynomial. If the degree of this polynomial, which is equal to the number of hyperplanes, is less than 
points of the grid which are not covered, a contradiction.
can be obtained from the affine space 
(which is isomorphic to 
be 
as the hyperplane at infinity, we get hyperplanes 
in 
points of 
, then a partial cover of 
has at least 
holes.
hyperplanes of 
.
such that 
. These are known as tangent hyperplanes. How many tangent hyperplanes can be there through an essential point of a blocking set?
tangent hyperplanes through 
.)
is a set 
on the size of a blocking set in an arbitrary projective plane of order 
, then there are at least 
tangent lines through an essential point of 
, then 
as it says that for any three distinct elements 
we have 
for all 
.). The oldest reference that I could find mentioning the term “cap” for such sets is this 1958 paper by Segre: 
, affine caps are related to the game 
of total degree at most 
that satisfy 
for all 
.
denote the set of all polynomials ![\mathbb{F}_q[x_1, \dots, x_n]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_q%5Bx_1%2C+%5Cdots%2C+x_n%5D&bg=ffffff&fg=333333&s=0 "\mathbb{F}_q[x_1, \dots, x_n]")
that satisfy 
and 
for all 
. There is a vector space isomorphism between 
denote the dimension of 
and 
via the bijection 
.
and 
are disjoint as otherwise we will have three distinct elements 
.
be the subspace of 
.
(since 
.
let 
be the intersection of 
is a subspace of 
, or equivalently, 
has at most 
non-zeros in 
via the evaluation isomorphism, has at most 
of 
with the property that every element of 
.
, we get 
.
when 
, which gives us the bound 
(whenever 
is an integer).
is bounded above by 
for some 
whenever 
(see the preprints).
there.
?
be a sequence of integers (not necessarily distinct). Then there exists a subsequence of 
be a sequence of elements of an abelian group 
of order 
. 
, 
, 
, 
. Say none of the 
‘s are zero. Since there are 
non-zero elements in 
for some 
by the pigeonhole principle. Hence 
.
integers, 
be a sequence of elements of an abelian group 
, i.e., 
where 
is the finite field of order ![P_1, \dots, P_r \in \mathbb{F}_q[t_1, \dots, t_n]](https://s0.wp.com/latex.php?latex=P_1%2C+%5Cdots%2C+P_r+%5Cin+%5Cmathbb%7BF%7D_q%5Bt_1%2C+%5Cdots%2C+t_n%5D&bg=ffffff&fg=333333&s=0 "P_1, \dots, P_r \in \mathbb{F}_q[t_1, \dots, t_n]")
. For 
, let 
and put 
. If 
, then 
‘s can’t have a unique common zero in 
. Say all 
. Then 
, so 
. Thus, by Alon-Furedi it has at least 
non-zeros in 
. Let 
be elements of 
and 
be two polynomials in ![\mathbb{F}_p[t_1, \dots, t_{2p-1}]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_p%5Bt_1%2C+%5Cdots%2C+t_%7B2p-1%7D%5D&bg=ffffff&fg=333333&s=0 "\mathbb{F}_p[t_1, \dots, t_{2p-1}]")
. Then 
is a common zero of 
, there exists another common zero 
in 
. Let 
, be all the positions where 
is equal to 
gives us 
and 
gives us 
. Since 
, we must have 
. 
elements of 
that sums up to 
a subgroup of 
satisfy the EGZ property, then 
and 
. Let 
be a sequence of elements of 
of 
are those elements, i.e., 
, or equivalently we have 
. Now look at the first 
elements of the remaining 
elements of 
. We can repeat this procedure till we have 
.
‘s, we have 
. By plugging in the values of 
in terms of the elements of 
elements of 