# Counting substructures in finite geometries

Sam Mattheus, Geertrui Van de Voorde

###### Abstract

We use techniques from algebraic and extremal combinatorics to derive upper
bounds on the number of independent sets in several (hyper)graphs arising from
finite geometry. In this way, we obtain asymptotically sharp upper bounds for
partial ovoids and EKR-sets of flags in polar spaces, line spreads in
$\mathrm{PG}(2r-1,q)$ and plane spreads in $\mathrm{PG}(5,q)$, and caps in
$\mathrm{PG}(3,q)$. The latter result extends work due to Roche-Newton and
Warren [25] and Bhowmick and Roche-Newton [9].
Finally, we investigate caps in $p$-random subsets of $\mathrm{PG}(r,q)$,
which parallels recent work for arcs in projective planes by Bhowmick and
Roche-Newton, and Roche-Newton and Warren [9, 25], and arcs in projective
spaces by Chen, Liu, Nie and Zeng [11].

##  1 Introduction

A classical problem in finite geometry is the study of interesting
substructures such as arcs, caps, spreads, etc. Traditionally, the focus of
this research is on constructing, characterising and classifying those
objects. Less attention is paid to counting the number of such substructures.
There are a few such results known though: an example of research in this
direction is Kantor’s count of commutative semifield planes of even order. It
should be noted that in this result, the number of such spreads are counted up
to isomorphism. The main result shows that (under some mild hypotheses on $q$
and $m$) the number of such planes of even order $q^{m}$ is at least
$(q^{m(\phi(m)-1)})/(m\log(q))^{2})$, which indicates that their
classification is a hopeless task.

On the other hand, finding upper bounds on the number of certain substructures
of (hyper)graphs is a very common theme in the area of extremal combinatorics.
Recently, techniques from extremal combinatorics have been employed to count
arcs in projective planes and higher-dimensional spaces. This problem was
addressed in [9, 11, 23, 25]. Note that in this case, arcs are not counted up
to isomorphism, but are considered different if their point sets are
different. More precisely, the result of Bhowmick and Roche-Newton [9] in the
plane states the following.

######  Theorem 1.1.

The number of arcs in $\mathbb{F}_{q}^{2}$ is at most $2^{(1+o(1))q}$.

Observe that this asymptotically matches the trivial lower bound $2^{q+1}$,
obtained by considering all possible subsets of an arc of size $q+1$, such as
a non-degenerate conic. It is worth noting that the arguments of [9] to derive
Theorem 1.1 are valid for general (Desarguesian and non-Desarguesian) affine
and projective planes. With the same techniques, they can also show that the
number of arcs of a fixed size $m$ in $\mathbb{F}_{q}^{2}$ is at most
${(1+o(1))q\choose m}$ for $m\in[q^{2/3+o(1)},q]$, which again matches the
trivial lower bound ${q+1\choose m}$ asymptotically. Both of these results
were recently extended to arcs in higher dimensions by Chen, Liu, Nie and Zeng
[11].

In this paper, we will show results in the same vein for substructures
different from arcs. To this end, we will apply the container method, a method
developed for counting independent sets in hypergraphs.

Recall that a hypergraph consists of a set of vertices and a set of
hyperedges, where hyperedges are subsets of vertices. A hypergraph is
$k$-uniform if every hyperedge has the same number $k$ of vertices; when
$k=2$, a hypergraph is called a graph. An independent set in a hypergraph is a
set of vertices such that no hyperedge is contained in it. The independence
number of a hypergraph is the size of its largest independent set.

Many of the interesting substructures within finite geometries can be phrased
as independent sets of a certain (hyper)graph. For example, ovoids and spreads
of polar spaces are known to be independent sets in the collinearity graph or
the dual polar graph of the polar space respectively. Similarly, one can
observe that caps in $\mathrm{PG}(n,q)$ are independent sets in the
$3$-uniform hypergraph whose edges are all collinear triples. These objects
generalise arcs in the projective plane in a different direction as the one
considered in [11].

To the best of our knowledge, this question has not been considered for any
other objects in projective or polar spaces other than arcs as mentioned
above. We do not aim to give a systematic treatment of every possible
substructure of projective or polar spaces that has been defined in the
literature, but rather show the strength of the container method for a select
few instances. The main difficulty in the settings that we consider is that
the largest independent sets are vanishingly small with respect to the number
of vertices of the (hyper)graph under consideration. While this is easily
overcome in the graph setting, as we will see in Section 2, we have to be more
careful in the hypergraph setting in Section 3 in order to get optimal
results. For this reason, we will use a rather technical version of the
container lemma, as stated by Saxton and Morris [27]. This lemma allows us to
prove our results in a more straightforward way, as opposed to [9, 11, 25],
where the iteration of the container lemma has to be set up every time again.

A subset of an independent set remains independent, and many interesting
substructures are closed under taking subsets: we can talk about partial
ovoids, partial spreads, etc. Intuitively, we would like to state a result on
the number of substructures (arcs, partial spreads, etc..) as follows: let $C$
be a substructure of the largest possible size, then the number of
substructures of size $t$ is at most $\binom{(1+\gamma)|C|}{t}$, where
$\gamma$ is small, that is, $\gamma=o(1)$ as $q\rightarrow\infty$. These
numbers should be considered as functions in terms of $q$: both the number of
substructures and the (rounded) binomial coefficient are polynomials in $q$ of
a certain degree, and we aim to show that the highest degree of the former is
at most the highest degree of the latter. Also recall that we are not counting
the number of non-isomorphic independent sets. It thus makes sense to allow
the correction factor $1+\gamma$, as we have to take into account the number
of substructures of maximum size. Such a result translates to saying the
number of substructures of maximum size is of a lower order than the total
number of substructures of size $t$ we can construct as subsets of a fixed one
of largest possible size. These counts should be considered asymptotically,
and we do not round numbers that are supposed to be integers either up or down
(omitting the floor or ceiling functions). This is justified since these
rounding errors are negligible to the asymptotic calculations we make.

Finally, the authors of [9, 11, 25] also investigate the problem of finding
the largest arcs in random subsets of points. To be precise, one samples
points independently and uniformly at random with fixed probability $p$ and
investigates how the size of the maximum arc varies as $p$ changes. This is
part of a more general theme in combinatorics where classical combinatorial
results are extended to sparse random settings. Such questions have received a
lot of attention in the past years, with notable breakthrough results by
Conlon and Gowers [12] and Schacht [28]. The hypergraph container method has
been highly influential with regards to this problem as well, as can already
be seen from the pioneering papers by Balogh, Morris and Samotij, and Saxton
and Thomason independently [7, 26].

This is no surprise as this problem is intimately related to counting
independent sets by using the first moment method. For instance, if we can
count the number of arcs of size $m$ in projective space, we can immediately
apply the union bound and see if any survive in expectation after we sample
points with probability $p$. For arcs in the projective plane in particular,
we have results that are tight up to powers of logarithms for the whole range
of $p$ by results of [9, 11].

#### Organisation of the paper and main results

This paper is organised as follows. In Section 2 we introduce the container
method for graphs and use it to give an asymptotically sharp count for:

  * •

partial ovoids in polar spaces (2.7);

  * •

EKR-sets of flags in polar spaces (2.9);

  * •

partial line spreads in $\mathrm{PG}(r-1,q)$ (2.10) and partial plane spreads
in $\mathrm{PG}(5,q)$ (Corollary 2.12).

In Section 3 we discuss the container method for 3-uniform hypergraphs which
we use to investigate the number of caps in $\mathrm{PG}(r,q)$. Our two main
results are:

  * •

bounds on the size of the largest caps in a $p$-random subsets of
$\mathrm{PG}(r,q)$ (Theorem 3.7),

  * •

an asymptotically sharp count for the number of caps in $\mathrm{PG}(3,q)$
(Corollary 3.10).

##  2 The container method for graphs

The container method for graphs dates back to the 1980s [20] and was extended
to hypergraphs independently by Balogh, Morris and Samotij [7] and Saxton and
Thomason [26]. These results heavily influenced the field of combinatorics;
the aforementioned analogues of classical combinatorial results in random
settings are nowadays mainly proved using this method. In short, the container
method can be used to bound the number of independent sets in a hypergraph.
The container lemma ensures that, under certain conditions, there exists a
relatively small collection of containers: this family of vertex subsets have
the property that every independent set of the graph is contained in one of
the containers. Moreover, for every container, the induced subgraph on this
set has a relatively small number of edges. As such, the number of independent
sets of a certain size $m$ in the hypergraph is at most the number of
containers given by the container lemma times the number of subsets of size
$m$ in a container; the goal is to derive suitable choices for the parameters
occuring in the conditions of the container lemma in order to find a good
upper bound on the number of containers and the number of vertices in one
container.

The container lemma for ordinary graphs reads as follows, where we use the
notation $e(S)$ for the number of edges whose vertices are contained in $S$.

######  Lemma 2.1.

(The container lemma for graphs) [21, Lemma 3.1] Let $G$ be a graph on $n$
vertices, let $f$ be an integer and let $R,\beta$ be real numbers where
$0<\beta<1$. Then, provided that

$\displaystyle e^{-\beta f}n\leq R,$ (1)

and, for every subset $S\subset V(G)$ of at least $R$ vertices, we have

$\displaystyle 2e(S)\geq\beta|S|^{2},$ (2)

the number of independent sets of size $m\geq f$, is at most

$\binom{n}{f}\binom{R}{m-f}.$

The main hurdle in applying the container lemma is the condition given by
Equation 2. Typically, we will want to choose the parameter $R$ not too be
much larger than $\alpha(G)$, the independence number of $G$.

We know that as soon as a vertex set is larger than $\alpha(G)$, the induced
subgraph contains at least one edge. However, it turns out that as soon as the
size of a subset $S$ crosses the threshold of $\alpha(G)$, the number of edges
in the induced subgraph is relatively large; we can write this number as some
fixed positive proportion $\beta$ of the total number $\binom{|S|}{2}$ of
possible edges of that set. In the literature, this phenomenon is often
referred to as a supersaturation result.

It is known that in the case of $d$-regular graphs, we can apply Cauchy
eigenvalue interlacing [17], or equivalently the expander mixing lemma [2], to
prove such supersaturation statements. We will derive this result in Corollary
2.3.

######  Lemma 2.2.

Let $G$ be a $d$-regular graph on $n$ vertices and with eigenvalues (of its
adjacency matrix) $d=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}$. Then
for any subset $S\subset V(G)$ we have

$2e(S)\geq\frac{d-\lambda_{n}}{n}|S|^{2}+\lambda_{n}|S|.$

###### Proof.

The proof is based on eigenvalue interlacing, where we only need the following
result: if $V(G)$ is partitioned as $X_{1}\cup X_{2}$ then we can define a
quotient matrix $Q$ indexed by these two parts, where $Q_{ij}$ equals the
average degree from $X_{i}$ to $X_{j}$. The smallest eigenvalue $\mu$ of $Q$
then satisfies $\lambda_{2}\geq\mu\geq\lambda_{n}$. Recall that
$\lambda_{n}<0$. We refer the reader to [17] for more details on the technique
of interlacing.

Partition the vertex set $V(G)$ as $S\cup(V(G)\setminus S)$. Then the average
degree in $S$, $d(S,S)$, equals $2e(S)/|S|$. By recalling that $G$ is
$d$-regular, we obtain that the average degree from $S$ to
$V(G)\setminus\\{S\\}$, is

$d(S,V(G)\setminus\\{S\\})=d-\frac{2e(S)}{|S|}.$

Since

$|S|d(S,V(G)\setminus\\{S\\})=(n-|S|)d(V(G)\setminus\\{S\\},S),$

we find that
$d(V(G)\setminus\\{S\\},S)=\frac{|S|}{n-|S|}\left(d-\frac{2e(S)}{|S|}\right)$,
and finally that
$d(V(G)\setminus\\{S\\},V(G)\setminus\\{S\\})=d-\frac{|S|}{n-|S|}\left(d-\frac{2e(S)}{|S|}\right)$.

This gives us the following quotient matrix with respect to the partition
$\\{S,V(G)\setminus S\\}$:

$\begin{pmatrix}\frac{2e(S)}{|S|}&d-\frac{2e(S)}{|S|}\\\
\frac{|S|}{n-|S|}\left(d-\frac{2e(S)}{|S|}\right)&d-\frac{|S|}{n-|S|}\left(d-\frac{2e(S)}{|S|}\right)\end{pmatrix}.$

Since the row sums equal $d$, we see that this matrix has eigenvalue $d$. Its
other eigenvalue, say $\mu$, can be computed by observing that the trace of
the matrix equals $d+\mu$. We find that

$\displaystyle\mu=\frac{2e(S)}{|S|}-\frac{|S|}{n-|S|}(d-\frac{2e(s)}{|S|}).$
(3)

On the other hand, by interlacing we know that

$\lambda_{2}\geq\mu\geq\lambda_{n}.$

Using the second inequality in combination with the expression for $\mu$ found
in (3), we obtain the stated inequality. ∎

We remark that putting $e(S)=0$ in Lemma 2.2, we retrieve the well-known
Delsarte-Hoffman bound for the independence number $\alpha(G)$ in a regular
graph (see e.g. [18] for an overview of this bound and its history):

$\displaystyle\alpha(G)\leq\frac{-\lambda_{n}}{d-\lambda_{n}}n.$ (4)

######  Corollary 2.3.

Let $G$ be a $d$-regular graph on $n$ vertices with smallest eigenvalue
$\lambda$. For all $\varepsilon>0$, any set $S\subseteq V(G)$ of size at least
$(1+\varepsilon)\frac{-n\lambda}{d-\lambda}$ satisfies

$2e(S)\geq\left(\frac{\varepsilon}{1+\varepsilon}\right)\frac{(d-\lambda)}{n}|S|^{2}.$

###### Proof.

We can rewrite Lemma 2.2 with $\lambda_{n}=\lambda$ as

$\displaystyle 2e(S)$
$\displaystyle\geq|S|^{2}\left(\frac{d-\lambda}{n}+\frac{\lambda}{|S|}\right)$
$\displaystyle\geq|S|^{2}\left(\frac{d-\lambda}{n}-\frac{1}{1+\varepsilon}\frac{d-\lambda}{n}\right),$

where we used that $\lambda$ is negative and
$\frac{1}{|S|}\leq\frac{1}{1+\varepsilon}\frac{d-\lambda}{-n\lambda}$. The
lemma follows. ∎

We are now ready to state a general theorem on the number of independent sets
in a $d$-regular graph. We note that similar results are known in the
literature, by Alon-Rödl via the theory of pseudorandom graphs [3] or
similarly via containers by Alon-Balogh-Morris-Samotij [1], but none of them
seem readily applicable to obtain bounds of the form
$\binom{(1+o(1))\alpha(G)}{m}$ for the number of independent sets of size $m$,
where $m$ only depends on $q$.

######  Theorem 2.4.

Let $G$ be a $d$-regular graph on $n$ vertices and with smallest eigenvalue
$\lambda$. For all $0<\varepsilon\leq n/d$, let
$f=\left(1+\frac{1}{\varepsilon}\right)\frac{n}{d-\lambda}\ln\left(\left(\frac{1}{1+\varepsilon}\right)\frac{d-\lambda}{-\lambda}\right)$
and $\alpha=\frac{-n\lambda}{d-\lambda}$. The number of independent sets of
size $m\geq f$ is at most

$\displaystyle\binom{n}{f}\binom{(1+\varepsilon)\alpha}{m-f}.$ (5)

###### Proof.

We will apply Lemma 2.1 to $G$. Define

$R=(1+\varepsilon)\frac{-n\lambda}{d-\lambda}=(1+\varepsilon)\alpha\hskip
28.45274pt\beta=\frac{\varepsilon}{1+\varepsilon}\frac{d-\lambda}{n}.$

We see that
$\beta=\frac{\varepsilon}{1+\varepsilon}\frac{d-\lambda}{n}\leq\frac{\varepsilon}{1+\varepsilon}\frac{d+n}{n}<1$
since
$1+\frac{d}{n}<\frac{1+\varepsilon}{\varepsilon}=1+\frac{1}{\varepsilon}$.

The condition $e^{-\beta f}n\leq R$ is readily verified with these expressions
for $R,\beta,f$ and the condition $2e(S)\geq\beta|S|^{2}$ for all sets $S$ of
size at least $R$ holds by Corollary 2.3. ∎

Recall that by the Delsarte-Hoffman bound (4), an independent set in a
$d$-regular graph $G$ with smallest eigenvalue $\lambda$ has size at most
$\frac{-n\lambda}{d-\lambda}$. In graphs arising from finite geometry, this
bound is often sharp and the maximal independent sets are of great interest.
Examples include ovoids and spreads in polar spaces. Theorem 2.4 can thus be
interpreted as saying that almost all sufficiently large independent sets are
subsets of maximal independent sets, and moreover that the overall number of
maximal independent sets is not too large.

We will now apply Theorem 2.4 to some particular families of graphs arising
from finite geometries defined over a finite field $\mathbb{F}_{q}$. Our goal
for each of these cases is to upper bound the number of independent sets of
size $m$ by $\binom{(1+o(1))\alpha}{m}$ as $q\to\infty$, where
$\alpha=-n\lambda/(d-\lambda)$. Of course, $m$ will need to be sufficiently
large to obtain such a result, since a greedy approach shows that the number
of independent sets of size $m=\frac{n}{2(d+1)}$ is at least

$\frac{n(n-(d+1))(n-2(d+1))\dots(n-(m-1)(d+1))}{m!}>\left(\frac{n}{2m}\right)^{m}=(d+1)^{m},$

which can be much larger than $\binom{(1+o(1))\alpha}{m}$.

The next result shows that in the finite geometries we consider, we can
require $m$ to only be slightly larger than $n/d$, being a factor of a power
of $\ln n$ away from it. However, we expend no effort in optimising the
exponent of this factor.

######  Corollary 2.5.

Let ${\cal G}_{q}$ be a family of $d$-regular graphs on $n$ vertices and with
smallest eigenvalue $\lambda$ defined for infinitely many prime powers $q$,
where $n,d,\lambda\to\infty$ as $q\to\infty$.

Let $\alpha:=\frac{-\lambda n}{d-\lambda}$ as before, then the number of
independent sets of size $m\geq 2\frac{n}{d}\ln^{4}n$, is at most
$\binom{(1+o(1))\alpha}{m}$ as $q\to\infty$.

###### Proof.

The crux of the proof lies in showing that the second factor in (5) dominates
the first for suitably large values of $m$. Let $0<\varepsilon\leq n/d$ and
$f$ be as in Theorem 2.4 and suppose $m\geq f\left(\frac{\ln
n}{\ln(1+\varepsilon)}+1\right)$. Then by Theorem 2.4, the number of
independent sets of size $m\geq f\left(\frac{\ln
n}{\ln(1+\varepsilon)}+1\right)$ is at most
$\binom{n}{f}\binom{(1+\varepsilon)\alpha}{m-f}$.

Since $m\geq f\left(\frac{\ln n}{\ln(1+\varepsilon)}+1\right)$, we have that
$f\left(\ln n+\ln(1+\varepsilon)\right)\leq m\ln(1+\varepsilon)$, which
implies that $f\ln n\leq(m-f)\ln(1+\varepsilon)$ and hence
$n^{f}\leq(1+\varepsilon)^{m-f}$. We see that

$\displaystyle\binom{n}{f}\binom{(1+\varepsilon)\alpha}{m-f}$
$\displaystyle\leq n^{f}\cdot\binom{(1+\varepsilon)\alpha}{m-f}$
$\displaystyle\leq(1+\varepsilon)^{m-f}\cdot\binom{(1+\varepsilon)\alpha}{m-f}$
$\displaystyle\leq\binom{(1+\varepsilon)^{2}\alpha}{m-f},$

where we used $\binom{a}{b}\leq a^{b}$ and
$c^{m-f}\binom{a}{m-f}\leq\binom{ca}{m-f}$ for $c>1$.

Moreover if $m\leq(1+\varepsilon)^{2}\alpha/2$, we immediately find
$\binom{(1+\varepsilon)^{2}\alpha}{m-f}\leq\binom{(1+\varepsilon)^{2}\alpha}{m}$.
When $m\geq\alpha/2$, we can see that $m/(m-f)<1+\varepsilon$ for sufficiently
large $q$ since $f=o(\alpha)$ and hence $f=o(m)$. Using
$\binom{ca}{cb}>\binom{a}{b}$ for $c>1$, it then follows that

$\binom{(1+\varepsilon)^{2}\alpha}{m-f}<\binom{\frac{m}{m-f}(1+\varepsilon)^{2}\alpha}{m}<\binom{(1+\varepsilon)^{3}\alpha}{m}.$

Now we will estimate the expression $f\cdot\left(\frac{\ln
n}{\ln(1+\varepsilon)}+1\right)=\left(1+\frac{1}{\varepsilon}\right)\frac{n}{d-\lambda}\ln\left(\left(\frac{1}{1+\varepsilon}\right)\frac{d-\lambda}{-\lambda}\right)\cdot\left(\frac{\ln
n}{\ln(1+\varepsilon)}+1\right)$ and set $\varepsilon=(\ln n-1)^{-1}$. We will
use the following inequalities for each of the respective factors:

$1+\frac{1}{\varepsilon}=\ln n,\hskip
14.22636pt\frac{n}{d-\lambda}\leq\frac{n}{d},\hskip
14.22636pt\frac{1}{1+\varepsilon}<1,\hskip
14.22636pt\frac{d-\lambda}{-\lambda}\leq n,\hskip 14.22636pt\frac{\ln
n}{\ln(1+\varepsilon)}+1\leq 2\ln^{2n},$

where we respectively used the expression for $\varepsilon$, $\lambda<0$,
$\varepsilon>0$, the fact that $1\leq\alpha(G)\leq\alpha$ and
$x/2\leq\ln(1+x)$ for $0<x<1$. We can combine this to find

$\displaystyle\left(1+\frac{1}{\varepsilon}\right)\frac{n}{d-\lambda}\ln\left(\left(\frac{1}{1+\varepsilon}\right)\frac{d-\lambda}{-\lambda}\right)\cdot\left(\frac{\ln
n}{\ln(1+\varepsilon)}+1\right)$ $\displaystyle\leq\ln
n\cdot\frac{n}{d}\cdot\ln n\cdot 2\ln^{2}n$
$\displaystyle=2\cdot\frac{n}{d}\cdot\ln^{4}n.$

∎

Note that the same argument can be made for
$m\geq\frac{n}{d}\ln^{2}n\omega^{2}(n)$, where $\omega(n)$ is any function
tending to infinity when $n\to\infty$, by setting
$\varepsilon=(\omega(n))^{-1}$.

###  2.1 Partial ovoids in polar spaces

We will only consider polar spaces which are embedded in a projective space. A
polar space $\mathcal{P}$ can be thought of as a point-line incidence geometry
where the rank of this geometry is the (vector) dimension of the largest
subspace totally contained in the point set of $\mathcal{P}$. Subspaces of
maximal rank contained in $\mathcal{P}$ are called generators. Consider a
subspace $\pi$ of next-to-maximal rank contained in $\mathcal{P}$, and let
$s+1$ be the number of generators through $\pi$. The number $s+1$ is
independent of the choice of $\pi$ and $s$ is called the type of the polar
space. If $\mathcal{P}$ is embedded in a projective space of order $q$, the
type $s$ of $\mathcal{P}$ is of the form $q^{t}$ where
$t\in\\{0,1/2,1,3/2,2\\}$.

We let $\mathrm{PS}(r,t,q)$ denote a polar space of rank $r\geq 2$, type
$q^{t}$ and defined over a finite field of order $q$. The first graph we will
consider is the collinearity graph of $\mathrm{PS}(r,t,q)$. The vertices of
this graph are given by the points of the polar space, and two vertices are
adjacent if and only if the corresponding points are collinear. The
collinearity graphs of polar spaces are well-known to be strongly regular.

The parameters of the collinearity graph are as follows (see e.g. [10, Theorem
2.2.12]).

$n=\frac{q^{r}-1}{q-1}\left(q^{r+t-1}+1\right),\hskip
28.45274ptd=\frac{q^{r}-q}{q-1}\left(q^{r+t-2}+1\right),\hskip
28.45274pt\lambda=-q^{r+t-2}-1.$

A partial ovoid in a polar space $\mathcal{P}$ is a set of points
$\mathcal{O}$ such that no generator contains more than one point of
$\mathcal{O}$. Since every line contained in $\mathcal{P}$ is contained in (at
least) a generator, it follows that no two points of a partial ovoid are
collinear (i.e. contained in a line of $\mathcal{P}$). Vice versa, a set
$\mathcal{O}$ of mutually non-collinear points will have the property that no
generator contains more than one point of $\mathcal{O}$. In other words,
partial ovoids are exactly the independent sets in the collinearity graph of
the polar space.

A direct application of the Delsarte-Hoffman bound (4) gives the following
well-known upper bound on the size of a partial ovoids:

######  Corollary 2.6.

Let $\mathcal{O}$ be a partial ovoid of $\mathrm{PS}(r,t,q)$, then

$|\mathcal{O}|\leq q^{r+t-1}+1.$

Moreover, partial ovoids attaining this upper bound (which are also called
ovoids) are only known to exist for small $r$ (see e.g. [13, Section 3.1]). If
for a polar space $\mathcal{P}$, ovoids do exist, then the number of partial
ovoids in $\mathcal{P}$ of size $m$ is clearly at least
$\binom{q^{r+t-1}+1}{m}$. We will now prove an asymptotically matching upper
bound using Theorem 2.4 for sufficiently large $m$.

######  Proposition 2.7.

Let $\mathrm{PS}(r,t,q)$ be a polar space, then the number of partial ovoids
of size $m\geq c_{r,t}q\ln^{4}q$, is at most

$\binom{(1+o(1))(q^{r+t-1}+1)}{m},$

where $c_{r,t}$ is a constant only depending on $r$ and $t$ and can be taken
to be $4(2r+t-1)^{4}$.

###### Proof.

We have that

$\displaystyle 2\cdot\frac{n}{d}\cdot\ln^{4}n$
$\displaystyle=2\cdot\frac{\frac{q^{r}-1}{q-1}(q^{r+t-1}+1)}{\frac{q^{r}-q}{q-1}(q^{r+t-2}+1)}\cdot\ln^{4}\left(\frac{q^{r}-1}{q-1}(q^{r+t-1}+1)\right)$
$\displaystyle\leq 4q\ln^{4}(q^{2r+t-1})$
$\displaystyle=4(2r+t-1)^{4}q\ln^{4}q,$

where we have used that
$\frac{\frac{q^{r}-1}{q-1}(q^{r+t-1}+1)}{\frac{q^{r}-q}{q-1}(q^{r+t-2}+1)}<2q$
for sufficiently large $q$. The proposition now follows from Corollary 2.5.

∎

###  2.2 EKR-sets of flags in polar spaces

Our next example will come from independent sets in oppositeness graphs in
polar spaces. These have been studied in [14] in the context of Erdős-Ko-Rado
results in polar spaces. Their definition is as follows. A flag $\cal F$ in a
polar space $\mathcal{P}$ is a set of subspaces ${\cal
F}=\\{F_{1},\dots,F_{k}\\}$ such that $F_{i}\lneq F_{i+1}$ for
$i=1,\dots,k-1$. The type of a subspace of $\mathcal{P}$ is its vector
dimension, and the type of a flag is the set of types of the subspaces it
contains. Two subspaces in $\mathcal{P}$ are opposite if no point in the first
is collinear to all points of the latter and vice versa. Two flags of the same
type in $\mathcal{P}$ are opposite if all pairs of subspaces of the same type
are opposite.

######  Definition 2.8.

Consider $\mathcal{P}=\mathrm{PS}(r,t,q)$ and let $J\subseteq[r]$, then the
oppositeness graph $G_{J}$ has all flags in $\mathcal{P}$ of type $J$ as
vertices and two vertices are adjacent if the corresponding flags are
opposite.

For simplicity we will only consider maximal flags, i.e. flags of type $[r]$
in a polar space $\mathrm{PS}(r,t,q)$, but analogous results can be deduced
for any possible type. The parameters of the oppositeness graph on maximal
flags have been computed [14] and are

$n=\prod_{i=1}^{r}(q^{r+t-i}+1)\left[{{i}\atop 1}\right]_{q},\hskip
28.45274ptd=q^{r(r+t-1)}\hskip
28.45274pt\lambda=\min\\{-q^{(r-1)(r+t-1)},(-1)^{n}q^{r(r-1)}\\}.$

Independent sets in this graph are sets of pairwise non-opposite flags. They
are called Erdős-Ko-Rado sets of flags inspired by the famous result due to
Erdős, Ko and Rado [16] on intersecting families of subsets. If $t\geq 1$ or
$n$ is even, we find by the Delsarte-Hoffman bound (4) that for an EKR-set of
flags $C$ we have

$|C|\leq\left[{{r}\atop
1}\right]_{q}\prod_{i=1}^{r-1}(q^{r+t-i}+1)\left[{{i}\atop
1}\right]_{q}=:\alpha_{\rm{EKR}},$

and this is sharp as shown by the set of maximal flags whose generators all
contain a fixed point.

When $t=1/2$ and $r$ is odd, it is not known whether the bound, using
$\lambda=-q^{r(r-1)}$, is sharp. For $t=0$ and $r$ odd, one can compute the
bound and see that it is also sharp, we refer the interested reader to [14]
for more information. We conclude that in the majority of the cases, we can
find a lower bound $\binom{\alpha_{\rm EKR}}{m}$ for the number of independent
sets of size $m$ in the oppositeness graph. We will now show that this bound
is asymptotically sharp, whenever $t\geq 1$ or $r$ is even.

######  Proposition 2.9.

Let $\mathrm{PS}(r,t,q)$ be a polar space, where $t\geq 1$ or $n$ even, then
the number of EKR-sets of maximal flags of size $m\geq c_{r,t}\ln^{4}q$, is at
most

$\binom{(1+o(1))\alpha_{\rm{EKR}}}{m},$

where $c_{r,t}$ is a constant depending only on $r$ and $t$ and can be taken
to be $64r^{4}(r+t-1)^{4}$.

###### Proof.

As before, we have that for sufficiently large $q$

$\displaystyle 2\cdot\frac{n}{d}\cdot\ln^{4}n$ $\displaystyle\leq
2\cdot\frac{2q^{r(r+t-1)}}{q^{r(r+t-1)}}\cdot\ln^{4}\left(2q^{r(r+t-1)}\right)$
$\displaystyle\leq 4\cdot 2^{4}r^{4}(r+t-1)^{4}\ln^{4}q,$

using $\ln(2q^{r(r+t-1)})\leq 2\ln(q^{r(r+t-1)})$. The proposition now follows
again from Corollary 2.5.

∎

###  2.3 Partial spreads in projective spaces

A partial spread in a projective space $\mathrm{PG}(r-1,q)$ is a set of
pairwise disjoint $k-1$-dimensional spaces. A spread is a partial spread that
moreover partitions the point set of $\mathrm{PG}(r-1,q)$. It is known that
spreads exist if and only if $k$ divides $r$ and clearly they have size
$({q^{r}-1})/({q^{k}-1})$. When $k=2$, we can deduce the number of partial
line spreads from our previous results. For in this case, the graph whose
vertices are the lines of $\mathrm{PG}(r-1,q)$, two lines adjacent whenever
they intersect, is a strongly regular graph whose eigenvalues are well-
understood [10, Section 1.2.4]. For this graph we have

$n=\left[{{r}\atop 2}\right]_{q},\hskip
28.45274ptd=(q+1)\left(\left[{{r-1}\atop 1}\right]_{q}-1\right),\hskip
28.45274pt\lambda=-q-1.$

The Delsarte-Hoffman bound thus gives $\alpha=(q^{r}-1)/(q^{2}-1)$, which is
indeed attained by line spreads whenever $r$ is even. For odd $r$, the results
of [24] show the existence of partial spreads of size $(1+o(1))q^{r-2}$. The
upper bound in the following proposition is hence asymptotically sharp for
both even and odd $r$.

######  Proposition 2.10.

For all $r\geq 4$, the number of partial line spreads in $\mathrm{PG}(r-1,q)$
of size $m\geq c_{r}q^{r-3}\ln^{4}q$ is at most

$\binom{(1+o(1))\frac{q^{r}-1}{q^{2}-1}}{m},$

where $c_{r}$ can be taken to be $2^{10}(r-2)^{4}$.

###### Proof.

As before, we have that for sufficiently large $q$

$\displaystyle 2\cdot\frac{n}{d}\cdot\ln^{4}n$ $\displaystyle\leq
2\cdot\frac{2q^{2r-4}}{q^{r-1}}\cdot\ln^{4}\left(2q^{2r-4}\right)$
$\displaystyle\leq 4\cdot q^{r-3}\cdot 4^{4}(r-2)^{4}\ln^{4}q,$

using $\ln(2q^{2r-4})\leq 2\ln(q^{2r-4})$. The proposition now follows again
from Corollary 2.5. ∎

When $k>2$, the same estimate does not follow as easily: the graph $G$ with
vertices $(k-1)$-spaces where $(k-1)$-spaces are adjacent when they have a
non-empty intersection is no longer strongly regular and the eigenvalues do
not provide the answer. For example when $r=6$ and $k=3$, partial plane
spreads in $\mathrm{PG}(5,q)$ have size at most $q^{3}+1$. However, when we
look at the eigenvalues, the results are far worse. The eigenvalues of the
complement graph have been studied [15] and are

$\mu_{1}=q^{9},\hskip 28.45274pt\mu_{2}=q^{4},\hskip
28.45274pt\mu_{3}=-q^{3},\hskip 28.45274pt\mu_{4}=-q^{6}.$

This means that for the graph $G$ we have

$n=\left[{{6}\atop 3}\right]_{q}\sim q^{9},\hskip 28.45274ptd=\left[{{6}\atop
3}\right]_{q}-q^{9}-1\sim q^{8},\hskip 28.45274pt\lambda=-q^{4}-1,$

so that the Delsarte-Hoffman bound gives $\alpha(G)\lesssim q^{5}$, which is
far worse than the upper bound $q^{3}+1$ . We can therefore also not deduce
any reasonable supersaturation from the eigenvalues.

Nevertheless, we can still prove supersaturation combinatorially, but the
results we obtain are not optimal.

######  Lemma 2.11.

For all $\varepsilon>0$, let $S$ be a set of planes of size
$(1+\varepsilon)(q^{3}+1)$. Then there are at least
$\varepsilon(q^{4}+q^{2}+1)$ pairs of intersecting planes.

###### Proof.

Counting with multiplicity, the set $S$ covers
$(1+\varepsilon)\frac{q^{6}-1}{q-1}$ points so that there are
$\varepsilon\frac{q^{6}-1}{q-1}$ points (again counted with multiplicity)
where two distinct planes meet. Since two planes meet in at most a line, i.e.
$q+1$ points, this implies that there must be at least
$\varepsilon\frac{q^{6}-1}{q^{2}-1}=\varepsilon(q^{4}+q^{2}+1)$ pairs of
intersecting planes. ∎

In other words, if $G$ denotes the graph on the planes in $\mathrm{PG}(5,q)$,
two planes adjacent whenever they intersect non-trivially, we see that for all
$S\subset V(G)$ such that $|S|=(1+\varepsilon)(q^{3}+1)$ we have

$2e(S)\geq\varepsilon(q^{4}+q^{2}+1)\geq\frac{\varepsilon}{(1+\varepsilon)^{2}}\frac{1}{q^{2}}|S|^{2}.$

######  Corollary 2.12.

The number of partial plane spreads in $\mathrm{PG}(5,q)$ of size $m\geq
28q^{2}\ln^{4}q$ is at most

$\binom{(1+o(1))(q^{3}+1)}{m}.$

###### Proof.

For any $\varepsilon>0$, we can use Lemma 2.1 directly with
$R=(1+\varepsilon)(q^{3}+1)$,
$\beta=\frac{\varepsilon}{(1+\varepsilon)^{2}q^{2}}$ and hence

$f=\frac{1}{\beta}\ln\left(\frac{n}{R}\right)=\frac{(1+\varepsilon)^{2}q^{2}}{\varepsilon}\ln\left(\frac{\left[{{6}\atop
3}\right]_{q}}{(1+\varepsilon)(q^{3}+1)}\right)$

suffices. We conclude that the number of independent sets of size $m\geq f$ is
at most

$\binom{\left[{{6}\atop
3}\right]_{q}}{f}\binom{(1+\varepsilon)(q^{3}+1)}{m-f}.$

Now set $\varepsilon=(\ln q)^{-1}$ so that

$\displaystyle f$ $\displaystyle\leq 4q^{2}\ln q\cdot\ln\left(2q^{6}\right)$
$\displaystyle\leq 28q^{2}\ln^{2}q,$

where we used that $1<1+\varepsilon\leq 2$ and $\ln(2q^{6})\leq 7\ln q$. When
$m\geq 28q^{2}\ln^{4}q$, we have $m\geq f\ln^{2}q$ and so

$\displaystyle\binom{(1+\varepsilon)R}{m-f}\leq\binom{\frac{m}{m-f}(1+\varepsilon)R}{m}\leq\binom{(1+\varepsilon)^{2}R}{m},$

using again $\binom{a}{b}<\binom{ca}{cb}$ for $c>1$ and the fact that
$m/(m-f)\leq 1+\varepsilon$ for $q$ large enough. We conclude that the number
of independent sets of size $m\geq 28q^{2}\ln^{4}q$ is at most

$\displaystyle\binom{\left[{{6}\atop
3}\right]_{q}}{f}\binom{(1+\varepsilon)^{2}R}{m}$
$\displaystyle\leq\left[{{6}\atop
3}\right]_{q}^{f}\binom{(1+\varepsilon)^{2}R}{m}$
$\displaystyle\leq(2q^{9})^{m/\ln^{2}q}\binom{(1+\varepsilon)^{2}R}{m}$
$\displaystyle\leq\binom{(1+20\varepsilon)(1+\varepsilon)^{2}R}{m},$

where we used that

$(2q^{9})^{1/\ln^{2}q}\leq(q^{10})^{1/\ln^{2}q}=e^{10/\ln q}\leq
1+\frac{20}{\ln q},$

as $e^{x}\leq 1+2x$ for sufficiently small $x$. Finally as $\varepsilon=(\ln
q)^{-1}$, it follows that
$(1+20\varepsilon)(1+\varepsilon)^{3}(q^{3}+1)=(1+o(1))(q^{3}+1)$ as
$q\to\infty$. ∎

##  3 The container method for caps

As mentioned in the introduction, the container method for hypergraphs was
developed by Balogh, Morris and Samotij [7] and Saxton and Thomason [26]. As
far as we are aware, the only application in finite geometry of this method
has been to count arcs in the plane by Roche-Newton and Warren [25], see also
subsequent results by Bhowmick and Roche-Newton [9], and to count arcs in
higher dimensional spaces by Chen, Liu, Nie and Zeng[11].

Many objects in finite geometry can be phrased as independent sets in
appropriate graphs, whereas objects corresponding to independent sets in
hypergraphs of higher uniformity are more rare. Arcs and caps are instances of
such objects.

A cap in $\mathrm{PG}(r,q)$ is a set of points, no three of which are
collinear. Elementary counting arguments show that a cap in $\mathrm{PG}(2,q)$
has at most $q+1$ points when $q$ is odd, and at most $q+2$ points when $q$ is
even. A cap in $\mathrm{PG}(3,q)$ has at most $q^{2}+1$ points; these are the
only known sharp bounds for the size of a cap in $\mathrm{PG}(r,q)$. When
$r\geq 4$, the situation is different. In this case, an elementary argument
shows that a cap can have at most $\left[{{r}\atop
1}\right]_{q}+1=(1+o(1))q^{r-1}$ points, but it is a long-standing open
problem to determine the (non)-existence of caps in $\mathrm{PG}(r,q)$ of size
$\Omega(q^{r-1})$.

In this section, we will use the hypergraph $\mathcal{H}_{q}$ whose vertices
are the points of $\mathrm{PG}(r,q)$, $r\geq 3$, and whose hyperedges are
given by collinear triples. Then $\mathcal{H}_{q}$ is a $3$-uniform hypergraph
on $\left[{{r+1}\atop 1}\right]_{q}$ vertices and has
$\frac{1}{6}\left[{{r+1}\atop 1}\right]_{q}\cdot(\left[{{r+1}\atop
1}\right]_{q}-1)\cdot(q-1)=\Theta(q^{2r+1})$ hyperedges. It should be clear
that an independent set in $\mathcal{H}_{q}$ corresponds to a cap of
$\mathrm{PG}(r,q)$ and vice versa.

Notation. We denote by $V(\mathcal{H})$ and $E(\mathcal{H})$ the vertex and
edge set of a hypergraph $\mathcal{H}$ respectively, and $v(\mathcal{H})$ and
$e(\mathcal{H})$ their respective sizes. Moreover we denote by
$\Delta_{\ell}(\mathcal{H})$ the maximum degree of a set of $\ell$ vertices of
$\mathcal{H}$, that is,

$\Delta_{\ell}(\mathcal{H})=\max\\{d_{\mathcal{H}}(A):A\subset
V(\mathcal{H}),|A|=\ell\\},$

where $d_{\mathcal{H}}(A)=|\\{B\in E(\mathcal{H}):A\subset B\\}|$. The average
degree is denoted by $d(\mathcal{H})$ and the subhypergraph of $\mathcal{H}$
induced by a $S\subset V(\mathcal{H})$ is denoted by $\mathcal{H}[S]$. If $A$
is a set, then $\mathcal{P}(A)$ denotes its power set.

The following container theorem is due to Saxton and Thomason [27, Theorem
5.1], which we only state for $3$-uniform hypergraphs in order to reduce the
complexity.

######  Theorem 3.1.

Let $\mathcal{H}$ be a $3$-uniform hypergraph on $n$ vertices and let
$e_{0}\leq e(\mathcal{H})$. Let
$\tau:\mathcal{P}(V(\mathcal{H}))\mapsto\mathbb{R}$ be a function satisfying
for each $U\subset V(\mathcal{H})$ with $e(\mathcal{H}[U])\geq e_{0}$, that
$\tau(U)<1/2$ and moreover

$\displaystyle\frac{\Delta_{2}(\mathcal{H}[U])}{d(\mathcal{H}[U])\cdot\tau(U)}+\frac{1}{2d(\mathcal{H}[U])\cdot\tau(U)^{2}}\leq\frac{1}{288}.$
(6)

For $e_{0}\leq m\leq e(\mathcal{H})$ define

$\displaystyle f(m)$
$\displaystyle=\max\\{|U|\tau(U)\ln(1/\tau(U))\,:\,U\subset
V(\mathcal{H}),e(\mathcal{H}[U])\geq m\\}$ $\displaystyle\tau^{*}$
$\displaystyle=\max\\{\tau(U)\,:\,U\subset
V(\mathcal{H}),e(\mathcal{H}[U])\geq e_{0}\\}.$

Let $s=\ln(e(\mathcal{H})/e_{0})/\ln(12/11)$. Then there exists a collection
$\mathcal{C}\subset\mathcal{P}(V(\mathcal{H}))$, a function
$b:\mathcal{P}(V(\mathcal{H}))\mapsto\mathcal{C}$ and a constant $c$ such that

  1. 1.

for every independent set $I$ there exists $F\subset I$ with $I\subset
b(F)\in\mathcal{C}$ and $|F|\leq c(s+1)\tau^{*}n$,

  2. 2.

$e(\mathcal{H}[C])\leq e_{0}$ for all $C\in\mathcal{C}$,

  3. 3.

$\ln|\mathcal{C}|\leq c\sum_{0\leq i<s}f((12/11)^{i}e_{0}))$.

######  Remark 3.2.

A few remarks are in order.

  1. 1.

The elements of $\mathcal{C}$ are the containers, whereas the sets $F$ are
informally referred to as the fingerprints, since any independent set contains
a unique fingerprint111This is in fact only true after we fix an ordering of
the vertices of $\mathcal{H}$, which is necessary for the proof of the
container theorem. which determines the container it is contained in.
Moreover, the containers only depend on the fingerprints, and not on the
actual independent sets they came from.

  2. 2.

The constant $c$ appearing in the statement of the theorem can be taken to be
$c=62208$, but the precise value of the constant in the conclusion will not
matter, only that it is independent of the parameters of $\mathcal{H}$. The
same goes for the constant $11/12$ appearing in the statement.

  3. 3.

This version of the container lemma is rather technical, but the need for
containers of size $o(v(\mathcal{H}))$ necessitates this. The original
container theorems on the other hand (see [26, Theorem 3.4] or [7, Theorem
2.2]), provide containers whose size is a constant proportion of
$v(\mathcal{H})$. The key insight is that after one application of these
theorems, we obtain a set of containers $\mathcal{C}_{1}$ and then we iterate
the argument again on $\mathcal{H}[C]$ for all $C\in\mathcal{C}_{1}$. In this
way, after an appropriate number of iterations, we will in fact be able to
obtain containers in $\mathcal{H}_{q}$ of size $\Theta(q^{r-1})$. Remark that
also [26, Corollary 3.6] is designed for a constant number of iterations and
works optimally when the ‘shrinkage factor’ is constant. This means that the
results one obtains from applying this theorem directly to $\mathcal{H}_{q}$
(without iteration) are suboptimal. The reason is that the behaviour of the
parameters $\Delta_{\ell}(\mathcal{H}_{q}[C])$ changes as as $C$ becomes
increasingly smaller, and this needs to be taken into account.

  4. 4.

We will couple the second item in the conclusion, giving an upper bound on the
number of edges within a container, with a supersaturation result to obtain an
upper bound on the sizes of the containers. This will immediately imply an
upper bound on the total number of independent sets of sufficiently large size
$m$: for if $|C|\leq\alpha$ for all $C\in\mathcal{C}$, then this number is at
most $|\mathcal{C}|\binom{\alpha}{m}$.

Lemma 3.4, whose proof is similar to [9, Lemma 2.2], will provide the required
supersaturation result. We first show the following:

######  Lemma 3.3.

Let $s,y$ be a positive integers and let $w_{1},\ldots,w_{s}$ be positive real
numbers with $\sum_{i=1}^{s}w_{i}=sy-1$. Then

$\displaystyle\sum_{i=1}^{s}\binom{w_{i}}{2}\geq(s-1)\binom{y}{2}+\binom{y-1}{2}.$
(7)

###### Proof.

Consider the function
$f:\mathbb{R}\to\mathbb{R}:x\mapsto\binom{x}{2}=\frac{x(x-1)}{2}$, then $f$ is
convex, and Jensen’s inequality states

$\sum_{i=1}^{s}\binom{w_{i}}{2}\geq s\binom{\frac{sy-1}{s}}{2}.$

The left hand side is an integer, therefore,
$\sum_{i=1}^{s}\binom{w_{i}}{2}\geq\lceil s\binom{\frac{sy-1}{s}}{2}\rceil$.
It is easy to check that
$s\binom{\frac{sy-1}{s}}{2}=\frac{s(y-1/s)(y-1-1/s)}{2}>(s-1)\frac{y(y-1)}{2}+\frac{(y-1)(y-2)}{2}-1$,
so $\lceil s\binom{\frac{sy-1}{s}}{2}\rceil=(s-1)\binom{y}{2}+\binom{y-1}{2}$
and the statement follows. ∎

######  Lemma 3.4.

Let $\mathcal{P}$ be a set of points in $\mathrm{PG}(r,q)$ of size
$k\left[{{r}\atop 1}\right]_{q}$ for some constant $k>1$. Then we have

$e(\mathcal{H})\geq\frac{k^{2}(k-1)}{6}\left[{{r}\atop
1}\right]_{q}^{2}-\frac{k(k-1)}{3}\left[{{r}\atop 1}\right]_{q}.$

Furthermore, if $|\mathcal{P}|\geq 2\left[{{r}\atop 1}\right]_{q}$ then
$e(\mathcal{H}_{q}(\mathcal{P}))\geq\frac{|\mathcal{P}|^{3}}{15\left[{{r}\atop
1}\right]_{q}}$.

###### Proof.

Recall that every point $Q$ of $\mathrm{PG}(r,q)$ lies on $\left[{{r}\atop
1}\right]_{q}$ lines. We will label the lines through $Q$ as
$\ell^{Q}_{1},\ell^{Q}_{2},\ldots$. Now let $Q\in\mathcal{P}$. Denoting the
number of points $R\neq Q$ of $\mathcal{P}$ on the line $\ell_{i}^{Q}$ by
$w_{j}^{Q}$, we give the point $Q$ weight

$w(Q)=\frac{1}{3}\sum_{i=1}^{\left[{{r}\atop 1}\right]_{q}}{w_{i}^{Q}\choose
2}.$

We see that $3w(Q)$ is the number of collinear triples in $\mathcal{P}$
containing $Q$, and hence, double counting the set
$\\{(Q,t)\,:\,Q\in\mathcal{P}\cap t,\,t\in\mathcal{T}\\}$, we find that

$3\mathcal{T}=\sum_{Q\in\mathcal{P}}3w(Q),$

or equivalently,

$\mathcal{T}=\sum_{Q\in\mathcal{P}}w(Q).$

Note that

$\displaystyle\sum_{j=1}^{\left[{{r}\atop 1}\right]_{q}}w_{j}^{Q}$
$\displaystyle=\sum_{j=1}^{\left[{{r}\atop
1}\right]_{q}}(|\ell_{j}^{Q}\cap\mathcal{P}|-1)=|\mathcal{P}|-1,$

which is independent of the choice of $Q\in\mathcal{P}$.

Using Lemma 3.3, with $s=\left[{{r}\atop 1}\right]_{q}$ and $y=k$, we find
that

$\mathcal{T}=\sum_{Q\in\mathcal{P}}w(Q)=\sum_{Q\in\mathcal{P}}\left(\frac{1}{3}\sum_{i=1}^{\left[{{r}\atop
1}\right]_{q}}{w_{i}^{Q}\choose
2}\right)\geq|\mathcal{P}|\cdot\frac{1}{3}\left(\frac{k(k-1)}{2}\left[{{r}\atop
1}\right]_{q}-(k-1)\right).$

For the last part, we need to check that $\frac{1}{3}k\left[{{r}\atop
1}\right]_{q}\left(\frac{k(k-1)}{2}\left[{{r}\atop
1}\right]_{q}-(k-1)\right)\geq k^{3}\left[{{r}\atop 1}\right]_{q}^{2}/15$. It
is not too hard to check that this is equivalent too

$(3k^{2}-5k)\left[{{r}\atop 1}\right]_{q}-10k+10\geq 2$

which is satisfied if $k\geq 2$. ∎

######  Corollary 3.5.

Let $C\subset V(\mathcal{H}_{q})$ be such that
$e(\mathcal{H}_{q}[C])\leq\frac{k^{2}(k-1)}{6}\left[{{r}\atop
1}\right]_{q}^{2}-\frac{k(k-1)}{3}\left[{{r}\atop 1}\right]_{q}$ for some
$k>1$, then $|C|\leq k\left[{{r}\atop 1}\right]_{q}$. In particular, if
$C\subset V(\mathcal{H}_{q})$ be such that $e(\mathcal{H}_{q}[C])\leq
4\left[{{r}\atop 1}\right]_{q}^{2}$, then $|C|\leq 4\left[{{r}\atop
1}\right]_{q}$.

We are now in the position to build our family of containers, restricting
ourselves to the case $r\geq 3$ as $r=2$ was handled in [9, 25]. Our goal will
be to end up with containers of size at most $(1+\gamma)\left[{{r}\atop
1}\right]_{q}$ for some $\gamma>0$. Depending on the application, we will
choose $\gamma$ to be constant or $\gamma=o(1)$. The latter is in general best
possible since for $r=3$ there are independent sets of size $q^{r-1}+1$ in
$\mathcal{H}_{q}$. The proof below is heavily inspired by [27, Theorem 1.10].

######  Theorem 3.6.

Let $r\geq 3$ and $\mathcal{H}_{q}$ be the 3-uniform hypergraph as defined
before. For all sufficiently large $q$, there exists a collection
$\mathcal{C}\subset\mathcal{P}(V(\mathcal{H}_{q}))$, a function
$b:\mathcal{P}(V(\mathcal{H}_{q}))\to\mathcal{C}$, and absolute constants
$c_{1},c_{2}$ such that

  1. 1.

for every independent set $I$ in $\mathcal{H}_{q}$ there exists $F\subset I$
with $I\subset b(F)\in\mathcal{C}$ and $|F|\leq c_{1}q^{(r-1)/2}\ln q$,

  2. 2.

$e(\mathcal{H}_{q}[C])\leq 4\left[{{r}\atop 1}\right]_{q}^{2}$ for all
$C\in\mathcal{C}$,

  3. 3.

$\ln|\mathcal{C}|\leq c_{2}q^{(r-1)/2}\ln^{2}q$.

###### Proof.

We will apply Theorem 3.1 to $\mathcal{H}_{q}$ with $e_{0}=4\left[{{r}\atop
1}\right]_{q}^{2}$. So let $U\subset V(\mathcal{H}_{q})$ with
$e(\mathcal{H}_{q}[U])=:m\geq e_{0}$ and denote $|U|=u$. By Lemma 3.4 we see
that if $u\geq 2\left[{{r}\atop 1}\right]_{q}$ then $m\geq
u^{3}/15\left[{{r}\atop 1}\right]_{q}$ or equivalently
$u\leq(15\left[{{r}\atop 1}\right]_{q}m)^{1/3}$. In the other case we have

$u\leq 2\left[{{r}\atop 1}\right]_{q}=\left(8\left[{{r}\atop
1}\right]_{q}^{3}\right)^{1/3}\leq\left(15\left[{{r}\atop
1}\right]_{q}m\right)^{1/3},$

and so the inequality holds in either case.

Now our objective is to find suitable $\tau(U)$ such that (6) holds. Since
$\Delta_{2}(\mathcal{H}[U])\leq q$ for any $U\subset V(\mathcal{H}_{q})$ this
condition is

$\displaystyle\frac{qu}{m\cdot\tau(U)}+\frac{u}{2m\cdot\tau(U)^{2}}\leq\frac{1}{288}.$

This inequality is satisfied if we set

$\tau(U)=\max\left\\{576\frac{qu}{m},18\left(\frac{u}{m}\right)^{1/2}\right\\},$

as the left-hand side can then be bounded using both lower bounds for
$\tau(U)$:

$\displaystyle\frac{qu}{m\cdot\tau(U)}+\frac{u}{2m\cdot\tau(U)^{2}}\leq\frac{1}{576}+\frac{1}{648}<\frac{1}{288}.$

This definition of $\tau(U)$ makes checking the condition easy, and it is
clear that the left hand side of the inequality will only decrease when we
increase any of the constants $576$ and $18$ in the definition of $\tau(U)$.
In fact, we will see that by appropriately increasing the second constant, the
maximum will always be attained in the second expression. So replacing the
constant $18$ by $18c_{1}$, $c_{1}\geq 1$, we can rewrite the condition that
the second expression is the largest:

$\displaystyle 576\frac{qu}{m}\leq 18c_{1}\left(\frac{u}{m}\right)^{1/2}$
$\displaystyle\iff 32q\left(\frac{u}{m}\right)^{1/2}\leq c_{1}$
$\displaystyle\iff 1024q^{2}u\leq c_{1}^{2}m.$ (8)

Using $u\leq(15\left[{{r}\atop 1}\right]_{q}m)^{1/3}$ a sufficient condition
for (8) to be satisfied is that

$\displaystyle 1024q^{2}(15\left[{{r}\atop 1}\right]_{q}m)^{1/3}\leq
c_{1}^{2}m$ $\displaystyle\iff 15\cdot 2^{30}q^{6}\left[{{r}\atop
1}\right]_{q}\leq c_{1}^{6}m^{2},$

which in its turn would be satisfied, using $m\geq e_{0}=4\left[{{r}\atop
1}\right]_{q}^{2}$, if

$\displaystyle 15\cdot 2^{30}q^{6}\leq 16c_{1}^{6}\left[{{r}\atop
1}\right]_{q}^{3}.$

Since $q^{6}\leq\left[{{r}\atop 1}\right]_{q}^{3}$, using $r\geq 3$, clearly
$c_{1}=2^{5}$ suffices. In conclusion, we can set
$\tau(U)=c_{2}\left(\frac{u}{m}\right)^{1/2}$ for some large constant $c_{2}$
(e.g. $18\cdot 32$) and (6) will be satisfied.

Morever, $(u/m)^{3}\leq 15\left[{{r}\atop
1}\right]_{q}/m^{2}\leq(15/16)\cdot\left[{{r}\atop 1}\right]_{q}^{-3}$ can be
made arbitrarily small by choosing sufficiently large $q$, so in particular
$\tau(U)<1/2$ for sufficiently large $q$. The conditions of Theorem 3.1 are
hence satisfied, and we obtain a constant $c$ and a set of containers
$\mathcal{C}$ with the properties mentioned in the conclusion of the theorem.
We will now calculate what these parameters are.

First of all,

$\displaystyle u\tau(U)\ln(1/\tau(U))$ $\displaystyle\leq
c_{2}\frac{u^{3/2}}{m^{1/2}}\ln\left(\frac{m^{1/2}}{c_{2}u^{1/2}}\right)$
$\displaystyle\leq c_{2}\frac{(15\left[{{r}\atop
1}\right]_{q}m)^{1/2}}{m^{1/2}}\ln\left(\frac{m^{1/2}}{c_{2}(15\left[{{r}\atop
1}\right]_{q}m)^{1/6}}\right)$ $\displaystyle\leq
c_{3}q^{(r-1)/2}\ln\left(m^{1/3}q^{-(r-1)}\right)=:f(m),$

for sufficiently large $q$, where the first inequality holds since
$\tau\ln(1/\tau)$ is an increasing function of $\tau$ when $\tau<1/e$, the
second inequality holds since $u^{3/2}\ln(m^{1/2}/cu^{1/2})$ is an increasing
function of $u$ when $u<m/c^{2}e^{2/3}$,

and the third inequality holds for a sufficiently large constant $c_{3}$. We
can then compute the parameter $s$:

$\displaystyle s=c_{4}\ln\left(\frac{e(\mathcal{H}_{q})}{e_{0}}\right)\leq
c_{4}\ln\left(\frac{q^{2r+1}}{q^{2r-2}}\right)\leq c_{5}\ln q,$

for some constant $c_{5}$ and sufficiently large $q$.

It follows that, setting $\alpha=12/11$,

$\displaystyle\ln|\mathcal{C}|$
$\displaystyle\leq\sum_{i=0}^{s}f(\alpha^{i}e_{0})$ $\displaystyle\leq
c_{3}q^{(r-1)/2}\sum_{i=0}^{s}\ln\left(\alpha^{i/3}e_{0}^{1/3}q^{-(r-1)}\right)$
$\displaystyle\leq c_{6}q^{(r-1)/2}\ln^{2}q,$

for some constant $c_{6}$, where we used that both $s$ and the terms appearing
in the sum are at most a constant times $\ln q$. This proves the bound on the
number of containers.

Finally, using the remark after the Theorem 3.1 on the size of the
fingerprints, we can also bound the size of the fingerprints:

$\displaystyle|U|\tau(U)$
$\displaystyle=c_{2}\left(\frac{u^{3}}{m}\right)^{1/2}$ $\displaystyle\leq
c_{2}\left(\frac{15\left[{{r}\atop 1}\right]_{q}m}{m}\right)^{1/2}$
$\displaystyle\leq c_{7}q^{(r-1)/2},$

for some constant $c_{7}$, so that $g(m)\leq c_{7}q^{(r-1)/2}$ for all $m\geq
e_{0}$. It follows that

$\displaystyle|F|$ $\displaystyle\leq c\sum_{0\leq i<s}g((12/11)^{i}e_{0})$
$\displaystyle\leq c\cdot s\cdot c_{7}q^{(r-1)/2}$ $\displaystyle\leq
c_{8}q^{(r-1)/2}\ln q,$

for some constant $c_{8}$ as $s=O(\ln q)$. ∎

###  3.1 First application: caps in random subsets of $\mathrm{PG}(r,q)$

A very influential research line in the last few years has been the study of
random Turán numbers. The problem generalises the classical Turán problem
which asks for the maximal number of edges in an $H$-free subgraph of $K_{n}$,
for some fixed graph $H$. Instead, we change the host graph to be the binomial
random graph $G(n,p)$. Initial groundbreaking results in this setting have
been obtained by Conlon and Gowers [12] and Schacht [28] independently. It was
later shown that the same results could be obtained by the container method
[7, 26], which was one of the major driving factors behind its development.
Since then, this problem and generalisations in different settings have been
studied extensively, typically stating the problem as finding sharp bounds for
the largest independent set in a random sub(hyper)graph of a given
(hyper)graph. One such example which is relevant to our work includes the size
of the largest arc in a random subset of $\mathrm{PG}(r,q)$ [11].

The problem statement in the case of caps in $\mathrm{PG}(r,q)$ is the
following: denote by $\mathcal{H}_{q}(p)$ the random subhypergraph of
$\mathcal{H}_{q}$, obtained by sampling every point in $\mathrm{PG}(r,q)$
(i.e. every vertex in $\mathcal{H}_{q}$) independently and uniformly with
probability $p$. What is then the behaviour of the independence number
$\alpha(\mathcal{H}_{q}(p))$ as $p=p(q)$ varies? With the help of Theorem 3.6,
we can obtain good bounds.

We will make use of the following results. First, the following tools from the
probabilistic method will be used throughout, see [4] for a reference.

Chernoff Bound If $X$ is a binomial random variable and $0<c\leq 1$, then

$\mathrm{Pr}\left(|X-\mathbb{E}(X)|\geq c\,\mathbb{E}(X)\right)\leq
2\exp\left(\frac{-c^{2}\,\mathbb{E}(X)}{3}\right).$

Markov’s inequality If $X$ is a non-negative random variable and $a>0$ then

$\mathrm{Pr}(X\geq a)\leq\frac{\mathbb{E}(X)}{a}.$

Before we state the result, observe that we can obviously expect
$\alpha(\mathcal{H}_{q}(p))$ to vary as $p$ changes. When $p$ is small, we
expect to see few collinear triples since $\mathcal{H}_{q}(p)$ is sparse and
hence close to an empty hypergraph. On the other hand, when $p$ is large, the
hypergraph $\mathcal{H}_{q}(p)$ resembles the original hypergraph
$\mathcal{H}_{q}$ closely and so we expect $\alpha(\mathcal{H}_{q}(p))$ to be
the same as $\alpha(\mathcal{H}_{q})$, appropriately scaled by $p$.
Interestingly enough, there is a ‘flat’ range where
$\alpha(\mathcal{H}_{q}(p))=\widetilde{\Theta}(q^{(r-1)/2})$, suppressing
powers of logarithms, where the answer seems to be independent of $p$. This
phenomenon has been observed in other related problems as well [11, 29]. We
write $f\ll g$ for two real non-negative functions if $f=o(g)$.

######  Theorem 3.7.

Asymptotically almost surely (a.a.s.), that is, with probability tending to
$1$ as $q\to\infty$, we have

$\displaystyle\alpha(\mathcal{H}_{q}(p))=\begin{cases}(1+o(1))pq^{r}&q^{-r}\ll
p\ll q^{-(r+1)/2}\\\ O(q^{(r-1)/2}\ln^{2}q)&q^{-(r+1)/2}\leq p\leq
q^{-(r-1)/2}\ln^{2}q\\\ O(pq^{r-1})&q^{-(r-1)/2}\ln^{2}q\leq p\leq
1.\end{cases}$

Moreover, we have a.a.s. lower bounds

$\displaystyle\alpha(\mathcal{H}_{q}(p))=\begin{cases}\Omega(q^{(r-1)/2}/\ln
q)&q^{-(r+1)/2}/\ln q\leq p\leq 1,\\\ \Omega(pq^{r-1})&q^{-(r-1)/2}\ln q\ll
p\leq 1\text{ when }r\in\\{2,3\\}.\end{cases}$

###### Proof.

Bounds for small $p$. Clearly $\alpha(\mathcal{H}_{q}(p))\leq
v(\mathcal{H}_{q}(p))$ always holds. Moreover, if we delete one vertex from
every edge of $\mathcal{H}_{q}(p)$, we get an independent set. Hence, if $X$
is the random variable $e(\mathcal{H}_{q}(p))$, i.e. the number of edges of
$\mathcal{H}_{q}(p)$ then $\alpha(\mathcal{H}_{q}(p))\geq
v(\mathcal{H}_{q}(p))-X$. It remains to show that a.a.s.
$v(\mathcal{H}_{q}(p))=(1+o(1))pq^{r}$ and $X=o(pq^{r})$.

Observe that $\mathbb{E}(v(\mathcal{H}_{q}(p)))=p\left[{{r+1}\atop
1}\right]_{q}=(1+o(1))pq^{r}$ and since $p\gg q^{-r}$, it follows by
Chernoff’s bound that a.a.s. $v(\mathcal{H}_{q}(p))=(1+o(1))pq^{r}$. On the
other hand
$\mathbb{E}(X)=p^{3}e(\mathcal{H}_{q})=(1+o(1))p^{3}q^{2r+1}=o(pq^{r})$, as
$p\ll q^{-(r+1)/2}$. Hence for every $\varepsilon>0$ we have by Markov’s
inequality

$\mathrm{Pr}(X\geq\varepsilon
pq^{r})\leq\frac{(1+o(1))p^{3}q^{2r+1}}{\varepsilon pq^{r}}\rightarrow 0\text{
as }q\to\infty.$

And hence we conclude that $X=o(pq^{r})$.

Upper bound for large $p$. Let $\mathcal{C}$ be the family of containers
obtained in Theorem 3.6, so that $\ln|\mathcal{C}|\leq
c_{2}q^{(r-1)/2}\ln^{2}q$ for some constant $c_{2}$. Using Corollary 3.5, we
see that $|C|\leq 4\left[{{r}\atop 1}\right]_{q}$ for all $C\in\mathcal{C}$.
Denote by $X_{i}(p)$ the random variable that counts the number of independent
sets of size $i$ in $\mathcal{H}_{q}(p)$, and set $m=C_{0}pq^{r-1}$ for some
constant $C_{0}$ to be determined later. Since every independent set is
contained in some element of $\mathcal{C}$, we find by Markov’s inequality
that

$\displaystyle\mathrm{Pr}(X_{m}(p)\geq 1)\leq\mathbb{E}(X_{m}(p))$
$\displaystyle\leq\sum_{C\in\mathcal{C}}p^{m}\binom{|C|}{m}$
$\displaystyle\leq|\mathcal{C}|p^{m}\binom{8q^{r-1}}{m}$
$\displaystyle\leq\exp(c_{2}q^{(r-1)/2}\ln^{2}q)\left(\frac{8epq^{r-1}}{m}\right)^{m},$

where we used $4\left[{{r}\atop 1}\right]_{q}\leq 8q^{r-1}$ for $q$ large
enough in the second inequality, and $\binom{a}{b}\leq(ea/b)^{b}$ in the
third. Substituting $m=C_{0}pq^{r-1}$ and using $q^{-(r-1)/2}\ln^{2}q\leq p$,
we conclude that for sufficiently large $C_{0}$ we have
$\mathrm{Pr}(X_{m}(p)\geq 1)\rightarrow 0$ as $q\rightarrow\infty$.

Upper bound for medium $p$. Now suppose that $q^{-(r+1)/2}\leq p\leq
q^{-(r-1)/2}\ln^{2}q$, and let $m:=C_{0}q^{(r-1)/2}\ln^{2}q$ for some constant
$C_{0}$ to be determined later. By Markov’s inequality and the fact that
$\mathbb{E}(X_{m}(p))$ is non-decreasing in $p$, we find that

$\displaystyle\mathrm{Pr}(X_{m}(p)\geq
1)\leq\mathbb{E}(X_{m}(p))\leq\mathbb{E}(X_{m}(q^{-(r-1)/2}\ln^{2}q)).$

With the same calculation as before, but now for these values of $m$ and $p$,
we find again that $\mathrm{Pr}(X_{m}(p)\geq 1)\to 0$ as $q\to\infty$ in this
range for $p$.

Lower bound for medium-large $p$.

From the monotonicity of $\alpha(\mathcal{H}_{q}(p))$ we find for the range
$q^{-(r+1)/2}/\ln q\leq p\leq 1$ that a.a.s.

$\alpha(\mathcal{H}_{q}(p))\geq\alpha(\mathcal{H}_{q}(q^{-(r+1)/2}/\ln
q))=(1+o(1))q^{(r-1)/2}/\ln q,$

as we already deduced that $\alpha(\mathcal{H}_{q}(p))=(1+o(1))pq^{r}$ a.a.s.
for $p=q^{-(r+1)/2}/\ln q$.

In the special case when $r\in\\{2,3\\}$, we have that
$\alpha(\mathcal{H}_{q})=\Theta(q^{r-1})$. Sampling from an independent set of
largest possible size, we see that by the Chernoff bound it follows that
a.a.s. $\alpha(\mathcal{H}_{q}(p))=\Omega(pq^{r-1})$. ∎

###  3.2 Second application: the number of caps in $\mathrm{PG}(3,q)$

As a second application of the hypergraph container lemma, we will count the
number of caps of size $m$ in $\mathrm{PG}(3,q)$ for sufficiently large $m$. A
similar count in $\mathrm{PG}(2,q)$ was obtained before [9, 25]. Even though
the method works in general dimension, we focus on the case $r=3$ since this
is the only known dimension, other than $r=2$, for which we have an
asymptotically matching lower bound. As mentioned earlier, it is a major open
problem to prove or disprove the existence of caps of size $\Omega(q^{r-1})$
in $\mathrm{PG}(r,q)$ for $r\geq 4$.

In order to obtain precise bounds of the form $\binom{(1+o(1))q^{2}}{m}$ for
sufficiently large $m$, we will need to further reduce the size of the
containers in Theorem 3.6. Fortunately, we only need a constant number of
iterations to do this, so we do not need the full strength of the iterated
container theorem (Theorem 3.1). Instead, we will use [27, Corollary 1.3],
which we again state only for $3$-uniform hypergraphs.

######  Theorem 3.8.

Let $\mathcal{H}$ be a hypergraph on $n$ vertices of average degree
$d(\mathcal{H})$ and $\varepsilon>0$. Then there is a constant
$c=c(\varepsilon)$ for which the following holds. Let $0<\tau\leq 1$ be chosen
so that

$\Delta_{2}(\mathcal{H})\leq c\tau d(\mathcal{H})\hskip
28.45274pt\text{and}\hskip 28.45274pt1\leq c\tau^{2}d(\mathcal{H}).$

Then there exists a collection $\mathcal{C}\subset\mathcal{P}(V(\mathcal{H}))$
and a constant $c_{0}$ such that

  1. 1.

for every independent set $I$ there exists some $C\in\mathcal{C}$ such that
$I\subset C$,

  2. 2.

$e(\mathcal{H}[C])\leq\varepsilon e(\mathcal{H})$,

  3. 3.

$\ln|\mathcal{C}|\leq c_{0}\tau n\ln(1/\tau)$.

We will now apply this theorem to the containers obtained in Theorem 3.6
iteratively until we obtain a set of containers $\mathcal{C}_{2}$ with the
property that each container $C$ satisfies $|C|\leq(1+\gamma)\left[{{3}\atop
1}\right]_{q}$ for some $0<\gamma\leq 1$.

######  Theorem 3.9.

Let $\mathcal{H}_{q}$ be the 3-uniform hypergraph as defined before. For all
$0<\gamma\leq 1/10$ and sufficiently large $q$ we have a family $\mathcal{C}$
of subsets of $V(\mathcal{H})$ satisfying the following properties:

  * •

for every cap $I$ in $\mathrm{PG}(3,q)$, there exists some $C\in\mathcal{C}$
such that $I\subset C$,

  * •

$|C|\leq(1+\gamma)\left[{{3}\atop 1}\right]_{q}$ for all $C\in\mathcal{C}$,

  * •

$\ln|\mathcal{C}|\leq cq\ln^{2}q+c\gamma^{-1}q\ln q$ for some absolute
constant $c>0$.

###### Proof.

Let $\mathcal{C}$ be the set of containers for $\mathcal{H}_{q}$ obtained in
Theorem 3.6. Note that $\ln|\mathcal{C}|\leq c_{2}q\ln^{2}q$ and that for
every container $C\in\mathcal{C}$, $e(\mathcal{H}[C]\leq 4\left[{{3}\atop
1}\right]_{q}^{2}$, so Corollary 3.5 implies that $|C|\leq 4\left[{{3}\atop
1}\right]_{q}$.

We will apply Theorem 3.8 to any container $C\in\mathcal{C}$ for which
$e(\mathcal{H}_{q}[C])\geq\frac{(1+\gamma)^{2}\gamma}{12}\left[{{3}\atop
1}\right]_{q}^{2}$ to obtain a new set $\mathcal{C}_{2}$ of containers.
Otherwise, set $\mathcal{C}_{2}=\\{C\\}$. In the latter case, since
$\frac{(1+\gamma)^{2}\gamma}{12}\left[{{3}\atop
1}\right]_{q}^{2}<\frac{(1+\gamma)^{2}\gamma}{6}\left[{{3}\atop
1}\right]_{q}^{2}-\frac{\gamma(1+\gamma)}{3}\left[{{3}\atop 1}\right]_{q}$,
Corollary 3.5 implies that $|C|\leq(1+\gamma)\left[{{3}\atop 1}\right]_{q}$.

For any $0<\gamma<1/10$ we will apply Theorem 3.8 with
$\varepsilon=(1+\gamma)^{2}\gamma/48$. As before,
$\Delta_{2}(\mathcal{H}_{q})\leq q$ and

$d(\mathcal{H}_{q}[C])=\frac{3e(\mathcal{H}[C])}{|C|}\geq\frac{3\frac{(1+\gamma)^{2}\gamma\left[{{3}\atop
1}\right]_{q}^{2}}{12}}{4\left[{{3}\atop
1}\right]_{q}}\geq\frac{(1+\gamma)^{2}\gamma}{16}\left[{{3}\atop
1}\right]_{q}.$

Hence, it would be sufficient to choose $0<\tau\leq 1$ such that

$q\leq c\tau{\frac{(1+\gamma)^{2}\gamma}{16}}\left[{{3}\atop
1}\right]_{q}\hskip 14.22636pt\text{and}\hskip 14.22636pt1\leq
c\tau^{2}{\frac{(1+\gamma)^{2}\gamma}{16}}\left[{{3}\atop 1}\right]_{q},$

where $c=c(\varepsilon)$, with $\varepsilon=(1+\gamma)^{2}\gamma/48$, given by
Theorem 3.8. Setting $\tau=\tilde{c}(1+\gamma)^{-2}\gamma^{-1}q^{-1}$, and
using that $\gamma<1/10$, we find that both conditions are satisfied for a
sufficiently large constant $\tilde{c}$. We conclude the existence of a set of
containers $\mathcal{C}_{C}$ in $\mathcal{H}_{q}[C]$ such that
$|C_{2}|\leq(1+\gamma)^{2}\gamma\left[{{3}\atop 1}\right]_{q}$ for all
$C_{2}\in\mathcal{C}_{C}$ and $\ln|\mathcal{C}_{2}|\leq
c^{\prime}\gamma^{-1}q\ln(q)$ for some constant $c^{\prime}$, using that
$0<\gamma<1/10$.

This means that the total number of containers
$\mathcal{C}_{2}:=\bigcup_{C\in\mathcal{C}}\mathcal{C}_{C}$ satisfies

$\ln|\mathcal{C}_{2}|\leq c_{2}q\ln^{2}q+c^{\prime}\gamma^{-1}q\ln(q).$

We can replace the constants by $\max\\{c_{2},c^{\prime}\\}$ to make them
equal. We find that
$e(\mathcal{H}_{q}[C_{2}])\leq\frac{(1+\gamma)^{2}\gamma}{12}\left[{{3}\atop
1}\right]_{q}^{2}$ for all $C_{2}\in\mathcal{C}_{2}$. As before, it follows
from Theorem 3.6 that $|C_{2}|\leq(1+\gamma)\left[{{3}\atop 1}\right]_{q}$.

∎

######  Corollary 3.10.

The number of caps in $\mathrm{PG}(3,q)$ of size $m\geq cq\ln^{3}q$ for some
constant $c>0$ is at most $\binom{(1+o(1))q^{2}}{m}$ as $q\to\infty$.

###### Proof.

Putting $\gamma=(\ln q)^{-1}$, we find for sufficiently large $q$ by Theorem
3.9 a collection of containers $\mathcal{C}$ such that
$|C|\leq(1+\gamma)\left[{{3}\atop 1}\right]_{q}$ and $\ln|\mathcal{C}|\leq
c_{0}q\ln^{2}q$ for some constant $c_{0}>0$. Since every independent set in
$\mathcal{H}_{q}$, i.e. a cap in $\mathrm{PG}(3,q)$, is contained in a
container, we find that the number of caps of size $m\geq 2c_{0}q\ln^{3}q$ in
$\mathrm{PG}(3,q)$ is at most

$\displaystyle\sum_{C\in\mathcal{C}}\binom{|C|}{m}$
$\displaystyle\leq\exp({c_{0}q\ln^{2}q})\binom{(1+\gamma)\left[{{3}\atop
1}\right]_{q}}{m}$
$\displaystyle\leq\exp\left({\frac{m\gamma}{2}}\right)\binom{(1+\gamma)\left[{{3}\atop
1}\right]_{q}}{m}$
$\displaystyle\leq(1+\gamma)^{m}\binom{(1+\gamma)\left[{{3}\atop
1}\right]_{q}}{m}$ $\displaystyle\leq\binom{(1+\gamma)^{2}\left[{{3}\atop
1}\right]_{q}}{m},$

as $\gamma/2\leq\ln(1+\gamma)$ for sufficiently large $q$. Finally, put
$2c_{0}=c$ and observe that $(1+1/\ln q)\left[{{3}\atop
1}\right]_{q}=(1+o(1))q^{2}$ as $q\to\infty$. ∎

## References

  * [1] N. Alon, J. Balogh, R. Morris, and W. Samotij. Counting Sum-free sets in Abelian Groups. Israel J. Math. 199 (2014), 309–344.
  * [2] N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988), 15–19.
  * [3] N. Alon and V. Rödl. Sharp bounds for some multicolor Ramsey numbers. Combinatorica 25 (2005), 125–141.
  * [4] N. Alon and J. Spencer. The probabilistic method. Fourth edition Wiley Ser. Discrete Math. Optim. John Wiley & Sons, Inc., Hoboken, NJ, 2016. xiv+375 pp.
  * [5] J. Balogh, S. Das, M. Delcourt, H. Liu and M. Sharifzadeh. Intersecting families of discrete structures are typically trivial. J. Combin. Theory Ser. A 132 (2015), 224–245.
  * [6] J. Balogh, R. I. Garcia, L. Li and A. Z. Wagner. Intersecting families of sets are typically trivial. J. Combin. Theory Ser. B 164 (2024), 44–67.
  * [7] J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. J. Amer. Math. Soc. 28 (3) (2015), 669–709.
  * [8] J. Balogh and J. Solymosi. On the number of points in general position in the plane. Discrete Anal. 16 (2018), 20 pp.
  * [9] K. Bhowmick and Oliver Roche-Newton. Counting arcs in $\mathbb{F}_{q}^{2}$. Discrete Comput. Geom.  (2024) https://doi.org/10.1007/s00454-023-00622-w.
  * [10] A. E. Brouwer and H. Van Maldeghem. Strongly Regular Graphs. Cambridge University Press (2022). doi:10. 1017/9781009057226
  * [11] Y. Chen, X. Liu, J. Nie, J. Zeng. Random Turán and counting results for general position sets over finite fields. arXiv:2309. 07744.
  * [12] D. Conlon, W. T. Gowers. Combinatorial theorems in sparse random settings. Ann. of Math. (2) 184 (2016), 367–454.
  * [13] J. De Beule, A. Klein, and K. Metsch. Substructures of Classical Polar Spaces. In: Storme L, De Beule J, editors. Current research topics in Galois geometry. Hauppauge, NY, USA: Nova Science; 2011. p. 35–61.
  * [14] J. De Beule, S. Mattheus, and K. Metsch. An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings. J. Combin. Theory Ser. A192 (2022), Paper No. 105657, 33 pp.
  * [15] J. Eisfeld. The Eigenspaces of the Bose-Mesner-Algebras of the Association Schemes Corresponding to Projective Spaces and Polar Spaces. Designs Codes Crypt. 17 (1999), 129–150.
  * [16] P. Erdős, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320.
  * [17] W. Haemers. Interlacing eigenvalues and graphs. Linear Algebra Appl. 226/228 (1995), 593—616.
  * [18] W. Haemers. Hoffman’s ratio bound. Linear Algebra Appl. 617 (2021), 215–219.
  * [19] W. Kantor. Commutative semifields and symplectic spreads. Journal of Algebra 270 (1)(2003), 96–114.
  * [20] D. Kleitman and K. Winston. The asymptotic number of lattices. Annals of Discrete Mathematics. 6 (1980), 243–249.
  * [21] Y. Kohayakawa, S. J. Lee, V. Rodl, and W. Samotij. The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers. Random Structures Algorithms 46 (1) (2015), 1–25.
  * [22] A. Kostochka, A., D. Mubayi, and J. Verstraete. On independent sets in hypergraphs. Random Structures Algorithms 44 (2014), no. 2, 224–239.
  * [23] D. Mubayi and J. Verstraete. Coloring hypergraphs that are the union of nearly disjoint cliques. Mathematika (2023) https://doi.org/10.1112/mtk.12234.
  * [24] E. Nastase, and P. Sissokho. The maximum size of partial spreads in a finite projective space. J. Combin. Theory Ser. A 152 (2017), 353–362.
  * [25] O. Roche-Newton and A. Warren. Arcs in $\mathbb{F}_{q}^{2}$. arXiv:2003. 03656
  * [26] D. Saxton and A. Thomason. Hypergraph containers. Invent. Math. 201 (3)(2015), 925–992.
  * [27] D. Saxton and A. Thomason. Online containers for hypergraphs, with applications to linear equations. J. Combin. Theory Ser. B 121 (2016), 248–283.
  * [28] M. Schacht. Extremal results for random discrete structures. Ann. of Math. (2) 184 (2016), no. 2, 333–365.
  * [29] J. Nie and S. Spiro. Sidorenko hypergraphs and random Turán numbers. arXiv:2309. 12873.