# Minors of matroids represented by sparse random matrices over finite fields

Pu Gao
University of Waterloo
<EMAIL_ADDRESS>Research supported by NSERC RGPIN-04173-2019 Peter Nelson
University of Waterloo
<EMAIL_ADDRESS>Research supported by NSERC RGPIN-03735-2023

###### Abstract

Consider a random $n\times m$ matrix $A$ over the finite field of order $q$
where every column has precisely $k$ nonzero elements, and let $M[A]$ be the
matroid represented by $A$. In the case that q=2, Cooper, Frieze and Pegden
(RS&A 2019) proved that given a fixed binary matroid $N$, if $k\geq k_{N}$ and
$m/n\geq d_{N}$ where $k_{N}$ and $d_{N}$ are sufficiently large constants
depending on N, then a.a.s. $M[A]$ contains $N$ as a minor. We improve their
result by determining the sharp threshold (of $m/n$) for the appearance of a
fixed matroid $N$ as a minor of $M[A]$, for every $k\geq 3$, and every finite
field.

##  1 Introduction

Random graphs were first introduced by Erdős and Rényi [8, 9] in 1959, marking
them one of the most important subjects in the study of modern graph theory.
In their seminal work [9], they defined a random graph process to explore the
evolution of random graphs. The process starts with an empty graph $G_{0}$ on
$n$ vertices. At every step $1\leq m\leq\binom{n}{2}$, an edge is added to
$G_{m-1}$, which is chosen uniformly from all edges that are not present in
$G_{m-1}$. Researchers have focused on investigating the earliest occurrence
of specific structures in this random graph process $(G_{m})_{0\leq
m\leq\binom{n}{2}}$, such as trees of a certain order, cycles of particular
lengths, Hamilton cycles, connected graphs, $k$-connected subgraphs,
$k$-cores, and more. Since its introduction, this random graph process has
undergone extensive examination and has greatly influenced research over the
past half-century and continues to do so.

We may view $(G_{m})_{0\leq m\leq\binom{n}{2}}$ as a random process for
graphic matroids, where the set of the edges in $G_{m}$, and the family of
forests in $G_{m}$ is the ground set, and the family of independent sets, of
the corresponding matroid. In other words, the random graph process induces a
random matroid process $(M[I(G_{m})])_{0\leq m\leq\binom{n}{2}}$, where
$I(G_{m})$ denotes the incidence matrix of $G_{m}$, and $M[A]$ denotes the
matroid represented by matrix $A$.

The column vectors of $I(G_{m})$ are binary vectors with exactly two entries
equal to 1. A natural generalisation of the random graphic matroid process
described as above, is to allow column vectors to have support size (i.e. the
number of nonzero entries) different from two, and to permit the nonzero
entries to take value from other fields. Motivated by this, we introduce the
following more general random matroid process.

Let ${\mathbb{F}}$ be a field, ${\mathbb{F}}^{*}={\mathbb{F}}\setminus\\{0\\}$
and $k\geq 3$ be a fixed integer. The case $k=2$ corresponds to minors of
random graphs, which is already well understood; see Remarks 1 and 5 below.
Let ${\mathcal{P}}:({\mathbb{F}}^{*})^{k}\to[0,1]$ be a permutation-invariant
probability distribution over $({\mathbb{F}}^{*})^{k}$; i.e.
${\mathcal{P}}(x_{1},\ldots,x_{k})={\mathcal{P}}(x_{\pi(1)},\ldots,x_{\pi(k)})$
for any permutation $\pi$ in the symmetric group $S_{k}$. Let
${\boldsymbol{v}}\in{\mathbb{F}}^{n}$ be the random vector defined as follows.
First choose a uniformly random subset $K\subseteq[n]$ with $|K|=k$; then set
the value of $(v_{j})_{j\in K}$ by the law ${\mathcal{P}}$, whereas $v_{j}$ is
set to 0 for all $j\notin K$. Let $({\boldsymbol{v}}_{m})_{m\geq 1}$ be a
sequence of random vectors each of which is an independent copy of
${\boldsymbol{v}}$. Let $(A_{m})_{m\geq 0}$ be a sequence of random matrices
where $A_{0}$ is empty and for each $m\geq 1$,
$A_{m}=[{\boldsymbol{v}}_{1},\ldots,{\boldsymbol{v}}_{m}]$ is obtained by
including the first $m$ column vectors
${\boldsymbol{v}}_{1},\ldots,{\boldsymbol{v}}_{m}$. Thus, $A_{m}$ is a random
matrix over ${\mathbb{F}}$ where every column vector has support size equal to
$k$. We study the evolution of the matroids $(M[A_{m}])_{m\geq 0}$ represented
by the sequence of random matrices $(A_{m})_{m\geq 0}$.

A special case of this random matroid process where
${\mathbb{F}}={\mathbb{F}}_{2}$ (the binary field) has been introduced and
studied earlier by Cooper, Frieze and Pegden [7]. Note that with
${\mathbb{F}}={\mathbb{F}}_{2}$, the only possible ${\mathcal{P}}$ is
${\mathcal{P}}(1,\ldots,1)=1$. In their work, they studied the appearance of a
fixed binary matroid $N$ as a minor of $M[A_{m}]$. While the matroid growth
rate theorem by Geelen, Kung, Kabell and Whittle [10, 11] (see also Theorem 22
below) immediately implies that $N$ appears as a minor of $M[A_{m}]$ for some
$m=O(n^{2})$, Cooper, Frieze and Pegden proved that $m=O(n)$ suffices for the
appearance of an $N$-minor for this random $\mathbb{F}_{2}$-representable
matroid. More precisely, given a binary matroid $N$, there exist sufficiently
large constants $k_{N}$ and $d_{N}$ such that if $k\geq k_{N}$ and $m\geq
d_{N}n$, then asymptotically almost surely (a.a.s.) $M[A_{m}]$ contains $N$ as
a minor. As further questions, they asked “to reduce $k$, perhaps to 3, and to
get precise estimates for the number of columns needed for some fixed matroid,
the Fano plane for example.” They also asked minors of $M[A_{m}]$ over fields
other than ${\mathbb{F}}_{2}$. In this paper we answer these questions. We
characterise the phase transition for the appearance of an $N$-minor, for
every $N$ of fixed order. A very surprising discovery from our result is that
this phase transition solely depends on $k$, and to a significant extent, is
independent of the minor $N$, the field ${\mathbb{F}}$, or the distribution
${\mathcal{P}}$. Define

$\displaystyle\rho_{k,d}$ $\displaystyle=$
$\displaystyle\sup\\{x\in[0,1]:x=1-\exp(-dx^{k-1})\\}$ (1) $\displaystyle
d_{k}$ $\displaystyle=$
$\displaystyle\inf\\{d>0:\rho_{k,d}-d\rho_{k,d}^{k-1}+(1-1/k)d\rho_{k,d}^{k}<0\\}$
(2)

######  Remark 1.

For every $k\geq 3$, it can be shown that $d_{k}$ is well defined; see e.g.
the remark after [2, Theorem 1.1]. For $k=2$, it is straightforward to check
that $\rho_{2,d}=0$ for all $d<1$, $\rho_{2,d}>0$ for all $d>1$, and
$\rho_{2,d}-d\rho_{2,d}+\frac{1}{2}d\rho_{2,d}^{2}<0$ for all $d>1$, and thus
$d_{2}=1$. For readers who are familiar with random $k$-uniform hypergraphs
${\mathcal{G}}_{k}(n,m)$ with $n$ vertices and $m$ hyperedges, for $k\geq 3$,
$d_{k}$ is precisely the critical density of $km/n$ where the 2-core of
${\mathcal{G}}_{k}(n,m)$ has more hyperedges than vertices, and $d_{2}=1$ is
precisely the critical density of $2m/n$ where ${\mathcal{G}}_{2}(n,m)$ has a
giant component. It has been well understood that all graph minors of fixed
order appear simultaneously in ${\mathcal{G}}_{2}(n,m)$ when $m/kn$ exceeds
$d_{2}$; see e.g. a proof in [21, Section 4], based on an argument initially
proposed by Svante Janson.

Our first result characterises the phase transition of the appearance of
minors for $A_{m}$ over prime fields.

######  Theorem 2.

Let $k\geq 3$. Suppose that ${\mathbb{F}}={\mathbb{F}}_{p}$ where $p$ a prime
number, and let ${\mathcal{P}}$ be any permutation-invariant distribution on
$({\mathbb{F}}_{p}^{*})^{k}$. Let $N$ be a fixed simple
${\mathbb{F}}_{p}$-representable matroid. Then, for every fixed $\epsilon>0$
the following hold:

  1. (a)

If $m<(d_{k}/k-\epsilon)n$ then a.a.s. $M[A_{m}]$ does not contain $N$ as a
minor if $N$ has a circuit;

  2. (b)

If $m>(d_{k}/k+\epsilon)n$ then a.a.s. $M[A_{m}]$ contains $N$ as a minor.

######  Remark 3.

Without loss of generality we may always assume that $N$ has a circuit, as
otherwise, all elements in $N$ are independent, and consequently, a.a.s. $N$
appears as a minor of $M[A_{m}]$ precisely at the step $m=\text{rank}(N)=|N|$,
as a.a.s. ${\boldsymbol{v}}_{1},\ldots,{\boldsymbol{v}}_{h}$ are linearly
independent if $h=O(1)$.

Theorem 2 is false for non-prime finite fields. As a counterexample, consider
${\mathcal{P}}$ where ${\mathcal{P}}(1,\ldots,1)=1$ and $q=4$. Let $N$ be any
${\mathbb{F}}_{4}$-representable matroid which is not
${\mathbb{F}}_{2}$-representable. Then for every $m$, $M[A_{m}]$ is a binary
matroid, which cannot contain $N$ as a minor. Our next result confirms that
Theorem 2 is true for non-prime finite fields after imposing some weak
condition on ${\mathcal{P}}$ .

######  Theorem 4.

Let $k\geq 3$. Suppose that ${\mathbb{F}}={\mathbb{F}}_{q}$ where $q$ is a
prime power, and ${\mathcal{P}}$ is a permutation-invariant distribution on
$({\mathbb{F}}_{q}^{*})^{k}$ such that
${\mathcal{P}}(\sigma_{1},\ldots,\sigma_{k})>0$ for every
$(\sigma_{1},\ldots,\sigma_{k})\in({\mathbb{F}}_{q}^{*})^{k}$. Let $N$ be a
fixed simple ${\mathbb{F}}_{q}$-representable matroid that contains a circuit.
Then, for every fixed $\epsilon>0$ the following hold:

  1. (a)

If $m<(d_{k}/k-\epsilon)n$ then a.a.s. $M[A_{m}]$ does not contain $N$ as a
minor;

  2. (b)

If $m>(d_{k}/k+\epsilon)n$ then a.a.s. $M[A_{m}]$ contains $N$ as a minor.

######  Remark 5.

The stipulation that $k=3$ in the above results is necessary. When $k=2$, the
matroid $M[A_{m}]$ is defined to have a $\mathbb{F}_{q}$-representation in
which each column has support at most $2$; matroids with this property are
known as ${\mathbb{F}}_{q}$-frame matroids, and they form a minor-closed
class. It follows that, if $k=2$ and $N$ is _not_ an ${\mathbb{F}}_{q}$-frame
matroid, then $M[A_{m}]$ will never have an $N$-minor. Conversely, we believe
that if $k=2$ and $N$ _is_ a $\mathbb{F}_{q}$-frame matroid of corank at least
$2$, then $N$ will satisfy the conclusion of Theorem 4 for graph-theoretic
reasons similar to those outlined in Remark 1. The proof is completely
different from that of $k\geq 3$ in this paper, and is not trivial; we will
discuss that in future work.

A significant part of the proof for Theorem 4 is the same as for Theorem 2,
and indeed holds for any general field ${\mathbb{F}}$. Thus we think that
results like Theorem 4 would be true for general fields by restricting to
certain distributions ${\mathcal{P}}$. See more discussions in Remark 19
below. As a concrete example, we make the following conjecture for the minors
of $M[A_{m}]$ over ${\mathbb{Q}}$.

######  Conjecture 6.

Let $k\geq 3$. Suppose that ${\mathbb{F}}={\mathbb{Q}}$, the field of rational
numbers, and ${\mathcal{P}}(1,\ldots,1)=1$. Let $N$ be a fixed simple
${\mathbb{Q}}$-representable matroid that contains a circuit. Then $d_{k}/k$
is the threshold (of $m/n$) for the appearance of $N$ as a minor of
$M[A_{m}]$.

If we were to change $\mathbb{Q}$ to $\mathbb{R}$ everywhere, this conjecture
would fail if $N$ were not chosen to be $\mathbb{Q}$-representable, since any
$M[A_{m}]$ generated by the process would be $\mathbb{Q}$-representable, as
would all its minors. However, we believe that arbitrary minors should appear
as long as the random entries we are using allow for it. We make a stronger
conjecture to that effect.

######  Conjecture 7.

Let $k\geq 3$. Let $\mathbb{F}$ be a field, and let $\mathcal{P}$ be a
permutation-invariant probability distribution on $\mathbb{F}^{k}$. For each
$r\in\mathbb{F}$, let $\beta_{r}$ denote the probability that a vector chosen
according to $\mathcal{P}$ contains two nonzero entries whose ratio is $r$.
Let $\mathbb{F}_{0}$ be the subfield of $\mathbb{F}$ generated by the set
$G=\\{r:\beta_{r}>0\\}$. Let $N$ be a fixed simple
$\mathbb{F}_{0}$-representable matroid that contains a circuit. Then $d_{k}/k$
is the threshold for the appearance of $N$ as a minor of $M[A_{m}]$.

######  Remark 8.

  1. (a)

Note that we always have $1\in G$, so $\mathbb{F}_{0}$ contains $\mathbb{Q}$
in the characteristic-zero case and contains the prime subfield of
$\mathbb{F}$ in the positive characteristic case. Theorem 4 treats a special
case where $\mathbb{F}$ is finite, and every vector in $(\mathbb{F}^{*})^{k}$
appears with positive probability in ${\mathcal{P}}$, which gives the
hypotheses of Conjecture 7 with $G=\mathbb{F}^{*}$ and hence
$\mathbb{F}_{0}=\mathbb{F}$. So our result confirms a special case of the
above. In fact, our techniques can be extended to verify the above conjecture
for all finite $\mathbb{F}$.

  2. (b)

Suppose $m<(d_{k}/k-\epsilon)n$. If the column vectors of $A_{m}$ are not
a.a.s. linearly independent then the subcritical case of Conjecture 7 cannot
be true. However, there is no result in the literature yet guaranteeing this
for an arbitrary field $\mathbb{F}$. The best known result regarding the rank
of $A_{m}$ is given below in Theorem 9, which does not imply linear
independence of column vectors of $A_{m}$. In the case that ${\mathbb{F}}$ is
a finite field, the linear independence of column vectors of $A_{m}$ has been
shown [2, Theorem 1.1]. If $\mathbb{F}={\mathbb{Q}}$ and ${\mathcal{P}}$ is
supported on $(1,\ldots,1)$ only, then the linear independence of column
vectors of $A_{m}$ in ${\mathbb{Q}}$ follows as a corollary of [2, Theorem
1.1], since entries in $A_{m}$ are integers and linear dependency in
${\mathbb{Q}}$ would imply the linear independence in $\mathbb{F}_{p}$ for any
prime number $p$. The same argument holds if ${\mathcal{P}}$ is supported on
$S^{k}$ for certain properly chosen subsets $S\subseteq{\mathbb{Q}}$. It would
already be very interesting to prove or refute that the column vectors of
$A_{m}$ are linearly independent for every permutation-invariant probability
distribution on ${\mathbb{Q}}^{k}$.

In addition to minors, there are several other fundamental questions that
warrant answers when considering random matroids. These include determining
the rank, the number of bases, the occurrence of circuits of specific lengths,
the connectivity, the number of submatroids isomorphic to a give matroid, and
minors of matroids with an order that is a function of the growing parameter
$n$, the automorphism group of the random matroid, etc. The rank of $M[A_{m}]$
can be deduced by examining the rank of the corresponding $A_{m}$ matrix, as
established through previous research on the rank of random sparse matrices
[6].

######  Theorem 9.

(Corollary of [6, Theorem 1.1]) For any field ${\mathbb{F}}$, integer $k\geq
1$, permutation-invariant distribution ${\mathcal{P}}$, nonnegative real $d$,
and $m\sim dn/k$,

$\lim_{n\to\infty}\frac{\text{rank}(M[A_{m}])}{n}=1-\max_{\alpha\in[0,1]}\left\\{\exp(-d\alpha^{k-1})-\frac{d}{k}(1-k\alpha^{k-1}+(k-1)\alpha^{k})\right\\}.$

With some calculations, it is easy to see that the maximisation problem on the
right hand side above is attained at $\alpha=0$ for $d<d_{k}$. That is, if
$d<d_{k}$ then a.a.s. $\text{rank}(M[A_{m}])\sim m$. As remarked above, in the
case that ${\mathbb{F}}$ is a finite field, a stronger full-column-rank result
[2, Theorem 1.1] is known if $d<d_{k}$, and this is what we use in Section 3
to prove Theorems 2(a) and 4(a).

While the other questions such as the connectivity, the circuits, etc. have
not been specifically studied for $M[A_{m}]$, they have been investigated in
other random matroid models, which we will discuss in detail in the following
subsection.

###  1.1 Other random matroid models

There are two other random matroid models that have been studied in the
literature. Mayhew, Newman, Welsh and Whittle [22] introduced the uniform
model for random matroid on $n$ elements, and they proposed various
conjectures concerning the connectivity, symmetry, minors, rank and
representability. In their work [22], they proved that the probability of a
uniformly random matroid being connected is at least 1/2. In a related study
[20], Lowrance, Oxley, Semple and Welsh proved that almost all matroids are
simple, cosimple, and 3-connected. They obtained bounds on the rank, and
estimated the number of bases, the number of circuits with given length, and
the maximum circuit size. The study of the uniform model of random matroids
eventually boils down to the enumeration of matroids on $n$ elements. Knuth
[15] established a lower bound for the number of matroids with $n$ element,
while the current best upper bound is given by Bansal, Pendavingh, and van der
Pol [3]. By counting representably matroids, Nelson [23] proved that almost
all matroids are non-representable. Pendavingh and Van der Pol [25] proved
that if a uniform random matroid $M$ has rank $r$, then almost all $r$-subsets
of $E(M)$ are beses of $M$. They derived several results on girth,
connectivity, and other related properties from this observation.

On the other hand, Kelly and Oxley [12, 13] introduced the concept of random
representable matroid over finite fields and specifically the model
${\text{P}G}(n-1,q,p)$. In this model, each vector in the projective space
${\text{P}G}(n-1,q)$ is independently included into the ground set of the
random matroid with a probability $p$, analogous to the binomial random graph
model ${\mathcal{G}}(n,p)$. They focused their studies on various aspects of
these random matroids, including the rank of the largest projective geometry
occurring as a submatroid, as well as other submatroids and independent sets.
Subsequent work by Kordecki [16, 17], Kordecki and Łuczak [18, 19] delved into
further exploration of the connectivity, circuits and small submatroids. In
[14] Kelly and Oxley introduced a slightly different model $M[U_{n,m}]$, where
$U_{n,m}$ is a uniformly random $n\times m$ matrix over ${\mathbb{F}}_{q}$.
This model is asymptotically equivalent to ${\text{P}G}(n-1,q,p)$ unless $m$
is close to $q^{n}$ (or equivalently when $p$ is close to 1 in
${\text{P}G}(n-1,q,p)$. In this slightly different model, Kelly and Oxley
studied the rank, connectivity and circuit sizes of $M[U_{n,m}]$. More
recently, Altschuler and Yang [1] determined the threshold for the appearance
of fixed minors in $M[U_{n,m}]$.

##  2 Preliminaries

We refer the readers to Oxley [24] for basic definitions of matroids. In
particular, if $M=(E,{\mathcal{I}})$ is a matroid and $X\subseteq E$, then the
contraction and deletion of $X$ in $M$ are defined respectively by
$M\\!\setminus\\!X=(E-X,\\{I\in{\mathcal{I}}:I\cap X=\varnothing\\})$ and

$\displaystyle M/X$ $\displaystyle=(E-X,{\mathcal{I}}^{*}),\quad\mbox{where}$
$\displaystyle{\mathcal{I}}^{*}$ $\displaystyle=\\{I\in{\mathcal{I}}:I\cap
X=\varnothing,I\cup J\in{\mathcal{I}}\ \mbox{for some maximal independent
subset $J$ of $X$}\\}.$

The independent sets of $M/X$ turn out not to depend on the choice of $J$. A
_submatroid_ of $M$ (also called a “restriction”) is any matroid of the form
$M\\!\setminus\\!X$, and a _minor_ of $M$ is a matroid of the form
$M/X\\!\setminus\\!Y$. Contraction and deletion commute in the sense that
$M/X_{1}\\!\setminus\\!Y_{1}/X_{1}\\!\setminus\\!Y_{2}=M/(X_{1}\cup
X_{2})\\!\setminus\\!(Y_{1}\cup Y_{2})$, and so any sequence of deletions and
contractions gives a minor.

Let ${\mathbb{F}}$ be a field. A matroid $M=(E,{\mathcal{I}})$ is
_${\mathbb{F}}$ -representable_ if there is a matrix $A=[a_{p}]_{p\in E}$ over
${\mathbb{F}}$ whose columns are indexed by elements in $M$ such that
$S\subseteq E$ is in ${\mathcal{I}}$ if and only if $\\{a_{p}:p\in S\\}$ are
linearly independent. We call such a matrix $A$ an _$\mathbb{F}$
-representation_ of $M$. A matroid $M$ is called _simple_ if for every
$p_{1},p_{2}\in E$, $\\{p_{1},p_{2}\\}\in{\mathcal{I}}$. In other words, if
$A=[a_{p}]_{p\in E}$ is an $\mathbb{F}$-representation of a simple matroid $M$
over ${\mathbb{F}}$, then the columns of $A$ are nonzero and pairwise non-
parallel.

Given a matrix $A$ over ${\mathbb{F}}$, let $M[A]$ denote the matroid
represented by $A$. We say two matrices $A$ and $B$ are row equivalent,
denoted by $A\sim B$, if $B$ is obtained from $A$ by performing a sequence of
elementary row operations. Note that an elementary row operation does not
change column dependencies, and thus $M[A]=M[B]$ if $A\sim B$.

We wish to consider deletions and contractions of representable matroids.
Given a matrix $A$ over ${\mathbb{F}}$ with column set $E$ and a subset
$X\subseteq E$, let $A_{X}$ denote the submatrix of $A$ consisting of the
columns in $X$, and let $A_{\setminus X}=A_{E-X}$. Let $A_{/X}$ be any matrix
obtained by first finding $B\sim A$ such that

$B_{X}=\left[\begin{array}[]{cc}I_{a\times a}&*\\\
0&0\end{array}\right],\quad\text{ where $a=\text{rank}(A_{X})$}$

and then deleting from $B$ the $a$ rows where the identity matrix $I_{a\times
a}$ lies, together with all the columns in $X$. The following standard result
shows that these matrices gives representations of deletions and contractions
of $M$.

######  Proposition 10.

If $A$ is a matrix over $\mathbb{F}$ with column set $E$, and $X\subseteq E$,
then $M[A]\\!\setminus\\!X=M[A_{\setminus X}]$, and $M[A]/X=M[A_{/X}]$,
regardless of the choice of $A_{/X}$.

Let $q$ be a prime power and let ${\mathbb{F}}_{q}$ denote the finite field of
order $q$. A special class of representable matroids is the projective
geometry ${\text{P}G}(t-1,q)$, which is the matroid represented by the matrix
$A$ whose column vectors correspond to the set of 1-dimensional subspaces of
${\mathbb{F}}_{q}^{t}$ (i.e. $A$ contains exactly one nonzero vector in each
1-dimensional subspace). The concept of ${\text{P}G}(t-1,q)$ bears a
resemblance to the notion of a simple complete graph, and as a result, they
play a central role in the examination of submatroids and minors of matroids,
in contrast to the study of subgraphs and minors of graphs. By the following
simple observation, in order to find any specific
${\mathbb{F}}_{q}$-representable rank-$t$ matroid as a minor, it suffices to
find ${\text{P}G}(t-1,q)$ as a minor.

######  Observation 11.

Let $q$ be a prime power. Then, ${\text{P}G}(t-1,q)$ contains every simple
rank-t ${\mathbb{F}}_{q}$-representable matroid as a submatroid.

In this paper, all asymptotics refer to $n\to\infty$. For two sequences of
real numbers $(a_{n})$ and $(b_{n})$, we write $a_{n}=O(b_{n})$ if there is
$C>0$ such that $|a_{n}|<C|b_{n}|$ for every $n$. We say $a_{n}=\Omega(b_{n})$
if $a_{n}>0$ and $b_{n}=O(a_{n})$. We say $b_{n}=o(a_{n})$ if $a_{n}>0$ and
$lim_{n\to\infty}b_{n}/a_{n}=0$. We say $b_{n}=\omega(a_{n})$ if $b_{n}>0$ and
$a_{n}=o(b_{n})$. We say a sequence of events $A_{n}$ holds a.a.s. if
${\mathbb{P}}(A_{n})=1-o(1)$.

##  3 Proof of Theorem 2(a) and Theorem 4(a)

By [2, Theorem 1.1] (note that our matrix $A$ in this paper corresponds to the
transpose of the matrix in [2] ), a.a.s. all columns of $A$ are linearly
independent under the hypotheses of Theorem 2(a) or Theorem 4(a). Thus $M[A]$
is a free matroid, which cannot contain a minor that has a circuit.

##  4 Proof of Theorem 2(b) and Theorem 4(b)

Most proofs in this section are independent of ${\mathbb{F}}$ and
${\mathcal{P}}$. Without specification, ${\mathbb{F}}$ is an arbitrary field,
and ${\mathcal{P}}$ is an arbitrary permutation-invariant distribution on
$(\mathbb{F}^{*})^{k}$. Let $t$ be a fixed integer and let $N$ be a simple
${\mathbb{F}}$-representable rank-$t$ matrix. We aim to find $N$ as a minor of
$M[A_{m}]$ where $m=(d_{k}/k+\epsilon)n$ for some $\epsilon=o(1)$. Recall that
${\boldsymbol{v}}\in{\mathbb{F}}^{n}$ is defined as a random vector by first
choosing a uniformly random subset $K\subseteq[n]$ with $|K|=k$ and then
setting the value of $(v_{j})_{j\in K}$ by the law ${\mathcal{P}}$, whereas
$v_{j}$ is set to 0 for all $j\notin K$.

In this section, we use the notation $A^{1},A^{2},\ldots$ to represent
matrices indexed by superscripts. It is important to note that the proofs in
this paper do not involve powers of any matrix. This clarification is provided
to ensure that readers do not confuse the notation with matrix powers.

We construct $A_{m}$ by starting with $A^{1}\sim A_{m_{1}}$ where $m_{1}$ is
slightly smaller than $d_{k}n$. Then, we carry out multiple rounds of
sprinkling random vectors to build the matrix $A_{m}$. Throughout the process
we leverage the existing structures present in $A^{1}$ as well as those
emerging from the successive rounds of sprinkled vectors. These structures aid
us in identifying the columns of $A_{m}$ to be contracted, and ultimately
enable us to find the desired minor.

Step 1 (Start with a subcritical matrix): Let $A^{1}\sim A_{m_{1}}$ where
$m_{1}=(d_{k}/k-\epsilon_{1})n$ where $\epsilon_{1}>0$ and
$\epsilon_{1}=o(1)$. The following lemma follows by [2, Theorem 1.1].

######  Lemma 12.

Let $\mathbb{F}$ be a finite field. Then, a.a.s. all columns of $A_{1}$ are
linearly independent, provided that $\epsilon_{1}$ approaches to 0
sufficiently slowly.

######  Definition 13.

Given a matrix $A$, the 2-core of $A$, denoted by ${A_{\text{2-core}}}$, is
defined by the matrix obtained by repeatedly deleting the all-zero rows, and
deleting the rows that contain exactly one nonzero entry, as well as the
column where that nonzero entry lies in.

Let ${(A^{1})_{\text{2-core}}}$ be the 2-core of $A^{1}$ and let $n_{1}$
denote the number of columns in ${(A^{1})_{\text{2-core}}}$. By definition,
every column of ${(A^{1})_{\text{2-core}}}$ has exactly $k$ nonzero entries,
and every row of ${(A^{1})_{\text{2-core}}}$ has at least two nonzero entries.
Next, we prove that ${(A^{1})_{\text{2-core}}}$ is close to a square matrix.

######  Lemma 14.

A.a.s. $n_{1}=\Theta(n)$ and the number of rows in ${(A^{1})_{\text{2-core}}}$
is $(1+\Theta(\epsilon_{1}))n_{1}$.

By possibly rearranging the columns and rows of $A^{1}$, we may write

$A^{1}=\left[\begin{array}[]{cc}{(A^{1})_{\text{2-core}}}&*\\\
0&*\end{array}\right],$

where $*$ denote entries in $A$ belonging to columns and rows that do not
belong to ${(A^{1})_{\text{2-core}}}$. Let
${\texttt{Row}}({(A^{1})_{\text{2-core}}})$ denote the set of rows in
${(A^{1})_{\text{2-core}}}$, which is the set of rows of $A^{1}$ that are
contained in ${(A^{1})_{\text{2-core}}}$.

Step 2 (First round of sprinkling random vectors): By Lemma 14 we may assume
that all columns of ${(A^{1})_{\text{2-core}}}$ are linearly independent. Let
$\eta=o(1)$ be chosen so that $\eta=o(\epsilon_{1})$. Let $A^{2}$ be the
matrix obtained by adding $\eta n$ independent random column vectors to
$A^{1}$, each distributed as ${\boldsymbol{v}}$. Given a subset $X$ of columns
of a matrix $A$, let $\langle A_{X}\rangle$ and $\langle A\rangle$ denote the
subspaces spanned by the column vectors in $A_{X}$ and in $A$ respectively.
Let $U$ be a subset of columns of $A^{2}$ constructed as follows. Given a
vector $u\in{\mathbb{F}}^{n}$, let ${\text{supp}\left(u\right)}$ denote the
set of entries of $u$ whose value is nonzero.

  1. (a)

Let $U_{0}$ be the set of columns in ${(A^{1})_{\text{2-core}}}$; denote these
column vectors by $v_{1},\ldots,v_{n_{1}}$.

  2. (b)

Let $u_{1},\ldots,u_{\eta n}$ be the $\eta n$ column vectors in
$A^{2}\setminus A^{1}$ whose columns are indexed by $p_{1},\ldots,p_{\eta n}$.
For $i=1,\ldots,\eta n$, if
${\text{supp}\left(u_{i}\right)}\subseteq{\texttt{Row}}({(A^{1})_{\text{2-core}}})$
and $u_{i}\notin\langle(A^{2})_{U_{i-1}}\rangle$, then
$U_{i}=U_{i-1}\cup\\{p_{i}\\}$; otherwise $U_{i}=U_{i-1}$.

  3. (c)

Let $U=U_{\eta n}$.

Let $A^{3}$ be the submatrix of $A^{2}$ obtained by deleting all columns that
are not in $U$, i.e. $A^{3}=(A^{2})_{U}$. Note that by the construction of
$U$, $A^{3}$ contains all column vectors in ${(A^{1})_{\text{2-core}}}$.

######  Lemma 15.

Let $v\sim{\boldsymbol{v}}$ be independent of $A^{3}$. Then,

${\mathbb{P}}(v\in\langle A^{3}\rangle\mid
v\in{\texttt{Row}}({(A^{1})_{\text{2-core}}}))=1-O(\epsilon_{1}/\eta).$

By the construction of $U$, the columns of $A^{3}$ are all linearly
independent, and they contain $U_{0}$, the set of all columns of
${(A^{1})_{\text{2-core}}}$. We may, by permuting the rows of $A^{3}$ if
necessary, write

$A^{3}=\left[\begin{array}[]{c}A^{\prime\prime}\\\ \end{array}\right]$

where $A^{\prime\prime}$ is an invertible $|U|\times|U|$ matrix. By Lemma 14
we may assume that

$A^{\prime\prime}$ contains all but at most $O(\epsilon_{1})n$ rows of
${\texttt{Row}}({(A^{1})_{\text{2-core}}})$.

Step 3 (The linear operator turning $A^{\prime\prime}$ to $I$): Let
$B=(A^{\prime\prime})^{-1}$. Let $b_{1},\ldots,b_{n^{\prime}}$ be the rows of
$B$ where $n^{\prime}=|U|$. Given $J\subseteq U$, let $B^{J}$ denote the
matrix consisting of rows $b_{j}$, $j\in J$. We prove the following key lemma
about $B$.

######  Lemma 16.

Let $r>0$ be a fixed positive integer. There exists a fixed $\delta>0$ such
that a.a.s. for every $J\subseteq[r]$ and for every nonzero
$\alpha\in{\mathbb{F}}^{J}$, $\sum_{j\in J}\alpha_{j}b_{j}$ has at least
$\delta n^{\prime}$ nonzero elements.

Step 4 (The second round of sprinkling random vectors): Let $A^{4}$ be the
matrix obtained by adding $\epsilon_{1}n$ random column vectors
$v_{1},\ldots,v_{\epsilon_{1}n}$ to $A^{2}$, each as an independent copy of
${\boldsymbol{v}}$. Let $(A^{\prime})^{4}$ be the corresponding matrix by
adding $v_{1},\ldots,v_{\epsilon_{1}n}$ to $A^{3}$ instead. Thus
$(A^{\prime})^{4}$ is a submatrix of $A^{4}$.

By Lemma 14,
${\mathbb{P}}({\text{supp}\left(v_{i}\right)}\subseteq{\texttt{Row}}({(A^{1})_{\text{2-core}}}))=\Theta(1)$
for every $1\leq i\leq\epsilon_{1}n$. By Lemma 15,
${\mathbb{P}}(v_{i}\in\langle(A^{5})_{U}\rangle\mid{\text{supp}\left(v_{i}\right)}\subseteq{\texttt{Row}}({(A^{1})_{\text{2-core}}}))=1-O(\epsilon_{1}/\eta)=1-o(1)$
for every $1\leq i\leq\epsilon_{1}n$. It follows by the standard Chernoff
bound that a.a.s. $|V|=\Theta(\epsilon_{1}n)$, where

$V=\\{v\in\\{v_{1},\ldots,v_{\epsilon_{1}n}\\}:{\text{supp}\left(v\right)}\subseteq{\texttt{Row}}({(A^{1})_{\text{2-core}}}),v\in\langle(A^{5})_{U}\rangle\\}.$

Let $v^{\prime}_{1},\ldots,v^{\prime}_{\epsilon_{2}n}$ be the vectors in $V$.
To match the dimension, write
$v^{\prime}_{i}=\left[\begin{subarray}{c}x^{\prime}_{i}\\\
y^{\prime}_{i}\end{subarray}\right]$. Let $A^{5}$ be the submatrix of
$(A^{\prime})^{4}$ such that

$A^{5}=\left[\begin{array}[]{ccc}A^{\prime\prime}&|&x^{\prime}_{1},\ldots,x^{\prime}_{\epsilon_{2}n}\\\
A^{*}&|&y^{\prime}_{1},\ldots,y^{\prime}_{\epsilon_{2}n}\end{array}\right].$

That is, $A^{5}$ is obtained from $(A^{\prime})^{4}$ by deleting all vectors
in $\\{v_{1},\ldots,v_{\epsilon_{1}n}\\}\setminus V$. Thus, with appropriate
row operations, i.e. multiplying $A^{5}$ by

$\left[\begin{array}[]{cc}B&0\\\ -A^{*}B&I\end{array}\right]$

to the left, $A^{5}$ is row equivalent to

$\left[\begin{array}[]{ccccc}I&|&Bx^{\prime}_{1}&\ldots&Bx^{\prime}_{\epsilon_{2}n}\\\
0&|&y^{\prime}_{1}-A^{*}Bx^{\prime}_{1}&\ldots&y^{\prime}_{\epsilon_{2}n}-A^{*}Bx^{\prime}_{\epsilon_{2}n}\end{array}\right].$

Note that for each $1\leq i\leq\epsilon_{2}n$,
$v^{\prime}_{i}\in\langle(A^{5})_{U}\rangle$ if and only if
$y^{\prime}_{i}-A^{*}Bx^{\prime}_{i}=0$. Thus we immediately have the
following observation.

######  Observation 17.

For every $1\leq j\leq\epsilon_{2}n$, $y_{j}^{\prime}-A^{*}Bx^{\prime}_{j}=0$.

Step 5 (Contraction): Recall that $U$ is the set of columns of $A^{3}$, i.e.
the set of columns in the submatrix
$\left[\begin{subarray}{c}A^{\prime\prime}\\\ A^{*}\end{subarray}\right]$ of
$A^{5}$. Let $r=r(t)$ be a sufficiently large constant that depends only on
$t$, the rank of $N$, and let $[r]$ denote the first $r$ columns of $U$. Let
$A^{6}$ be the matrix obtained from $A^{5}$ by contracting all columns in
$U\setminus[r]$. By Observation 17,

$\text{rank}(A^{6})=r.$ (3)

Without loss of generality, we may keep only the first $r$ rows of $A^{6}$ as
the remaining rows are all-zero rows by Observation 17, and deleting these
rows does not change the matroid the matrix represents. The final step is to
find the desired minor in $M^{\prime}=M[A^{6}]$.

######  Lemma 18.

Let $\mathbb{F}$ be a finite field. Then, a.a.s. $M^{\prime}$ contains any
fixed simple ${\mathbb{F}}$-representable matroid $N$ as a minor.

###  4.1 Completing the proofs of Theorems 2(b) and 4(b)

First of all, notice that $A^{4}\sim A_{m}$, where $m=m_{1}+\eta
n+\epsilon_{1}n=(d_{k}/k+\eta)n$ where $\eta=o(1)$. As $(A^{\prime})^{4}$ is a
submatrix of $A^{4}$ and $M^{\prime}$ is a minor $(A^{\prime})^{4}$, which
contains $N$ as a minor by Lemma 18, Theorems 2(b) and 4(b) follow.

######  Remark 19.

Step 1 holds for $\mathbb{F}={\mathbb{Q}}$ with appropriate setting of
${\mathcal{P}}$ such as in Conjecture 6. See Remark 8(b) for more discussions.
The subsequent steps and Lemmas 14, 15, 16 and Observation 17 hold for any
arbitrary field. The only part of the proof that specifically requires
$\mathbb{F}$ to be a finite field is for Lemma 18.

We complete this section by proving Lemmas 14 and 15. We prove Lemma 18
assuming Lemma 16 in Section 5, where two distinct cases are discussed
separately, depending on whether ${\mathbb{F}}$ is a prime field, or a field
of order that is a prime power. Finally, Lemma 16 is proved in Section 6.

###  4.2 Proof of Lemmas 14 and 15

Proof of Lemma 14.  Recall $\rho_{k,d}$ and $d_{k}$ from (1) and (2). Let
$d_{k}^{*}=\inf\\{d>0:\rho_{k,d}>0\\}$. By [2, Theorem 1.6], by letting
$d=km/n$, the number of rows and columns in ${A_{\text{2-core}}}$ is a.a.s.
asymptotic to $(\rho_{k,d}-d\rho_{k,d}^{k-1}+d\rho_{k,d}^{k})n$ and
$(d\rho_{k,d}^{k}/k)n$ respectively. Moreover, the function

$\pi_{k}:d\to\frac{d}{k}\rho_{k,d}^{k}\left(\rho_{k,d}-d\rho_{k,d}^{k-1}+d\rho_{k,d}^{k}\right)^{-1}$

is strictly increasing on $[d_{k}^{*},\infty)$. By the definition of $d_{k}$,
the monotonicity of $\pi_{k}$, and the assumption that
$m=(d_{k}/k-\epsilon_{1})n$, the assertion in the lemma follows immediately.

Proof of Lemma 15.  Let $I={\texttt{Row}}({(A^{1})_{\text{2-core}}})$. Since
${\text{supp}\left(v\right)}$ is uniform over $\binom{[n]}{k}$, it follows
that ${\text{supp}\left(v\right)}$ is uniform over $\binom{I}{k}$ conditional
on ${\text{supp}\left(v\right)}\subseteq I$. Let $K>0$ be a sufficiently large
constant. Suppose on the contrary that

${\mathbb{P}}(v\notin\langle(A^{2})_{U}\rangle\mid
v\in{\text{supp}\left({(A^{1})_{\text{2-core}}}\right)})>K\epsilon_{1}/\eta.$

Note that ${\mathbb{P}}(u_{i}\notin\langle(A^{2})_{U_{i-1}}\rangle\mid
u_{i}\in{\text{supp}\left({(A^{1})_{\text{2-core}}}\right)})$ is non-
increasing for $i$. It follows immediately that

${\mathbb{P}}(u_{i}\notin\langle(A^{2})_{U_{i-1}}\rangle\mid
u_{i}\in{\text{supp}\left({(A^{1})_{\text{2-core}}}\right)})>K\epsilon_{1}/\eta,\quad\mbox{for
every $1\leq i\leq\eta n$.}$

Let $X_{i}=1_{\\{U_{i}=U_{i-1}\cup\\{p_{i}\\}\\}}$. Then, $\sum_{i=1}^{\eta
n}X_{i}$ stochastically dominates ${\bf Bin}(\eta n,K\epsilon_{1}/\eta)$. By
the Chernoff bound,

${\mathbb{P}}\left(\sum_{i=1}^{\eta
n}X_{i}<(K/2)\epsilon_{1}n\right)\leq{\mathbb{P}}\Big{(}{\bf Bin}(\eta
n,K\epsilon_{1}/\eta)<(K/2)\epsilon_{1}n\Big{)}=\exp(-\Omega(\epsilon_{1}n)).$

Thus, a.a.s. $\sum_{i=1}^{\eta n}X_{i}\geq(K/2)\epsilon_{1}n$. It follows then
that a.a.s. $|U|-|U_{0}|\geq(K/2)\epsilon_{1}n$. But then the submatrix of
$(A^{2})_{U}$ restricted to the rows in
${\texttt{Row}}({(A^{1})_{\text{2-core}}})$ contains more columns than rows by
Lemma 14, contradicting with the fact that all column vectors in $U$ are
linearly independent.

##  5 Proof of Lemma 18

######  Definition 20.

For an $r\times n^{\prime}$ matrix $C$, we say that $C$ contains
$\\{u_{1},\ldots,u_{r}\\}$ as a $\delta$-dense basis for
${\mathbb{F}}_{q}^{r}$, if $\langle
u_{1},\ldots,u_{r}\rangle={\mathbb{F}}_{q}^{r}$, and for each $1\leq i\leq r$,
there are at least $\delta n^{\prime}$ column vectors in $C$ equal to $u_{i}$.

Recall that $B^{[r]}$ is the matrix obtained by taking the first $r$ rows of
$B$; thus $B^{[r]}$ is an $r\times n^{\prime}$ matrix. By Lemma 14,
$n^{\prime}\geq n_{1}=\Theta(n)$. We prove that a.a.s. $B^{[r]}$ has a
$\delta$-dense basis, for some constant $\delta>0$, if ${\mathbb{F}}$ is a
finite field.

######  Lemma 21.

Let $q$ be a prime power and let $r>0$ be a fixed positive integer. Then there
exists a constant $\delta>0$ such that a.a.s. $B^{[r]}$ contains a
$\delta$-dense basis for ${\mathbb{F}}_{q}^{r}$.

Proof.  We prove this lemma assuming Lemma 16. Let $\delta>0$ be the constant
whose existence is guaranteed by Lemma 16. We prove that $B^{[r]}$ contains a
$\delta/q^{r}$-dense basis for $\mathbb{F}_{q}^{r}$. We say $u$ is a
$(\delta/q^{r})$-dense column vector of $B^{[r]}$ if there are at least
$(\delta/q^{r})n^{\prime}$ column vectors of $B^{[r]}$ equal to $u$. We prove
that if $u_{1},u_{2},\ldots,u_{h}$ are linearly independent
$(\delta/q^{r})$-dense column vectors of $B^{[r]}$ and $h<r$, then there
exists a $(\delta/q^{r})$-dense column vector $u_{h+1}$ of $B^{[r]}$ such that
$u_{1},u_{2},\ldots,u_{h+1}$ are linearly independent. Note that this
immediately implies the assertion of the lemma.

Let $C$ be the set of column vectors of $B^{[r]}$ that are in $\langle
u_{1},\ldots,u_{h}\rangle$. We prove that

$|C|\leq(1-\delta)n^{\prime}.$ (4)

Since $u_{1},\ldots,u_{h}$ are linearly independent,
$\text{rank}(B^{[r]}_{C})=h<r$. Hence there exists a nonzero
$\alpha\in\mathbb{F}_{q}^{r}$ such that $\alpha^{T}C=0$. In other words,
$\alpha^{T}B_{[r]}$ contains at most $n^{\prime}-|C|$ nonzero elements. By
Lemma 16, $n^{\prime}-|C|\geq\delta n^{\prime}$, confirming (4). Since
$|\mathbb{F}_{q}^{r}|=q^{r}$, there exists a column vector $u$ such that
$u\notin C$ and $u$ appears at least $(\delta/q^{r})n^{\prime}$ times in
$B^{[r]}$. Then, $u$ is $(\delta/q^{r})$-dense, and $u_{1},\ldots,u_{h},u$ are
linearly independent. Thus we may choose $u_{h+1}=u$.

###  5.1 Proof of Lemma 18 when ${\mathbb{F}}={\mathbb{F}}_{p}$ where $p$ is
prime

We use the following growth rate theorem by Geelen, Kabell, Kung and Whittle
[11, Corollary 1.5] to find $N$ as a minor of $M^{\prime}$.

######  Theorem 22.

Let $p$ be a prime. For every integer $t\geq 2$ there exists $C_{t}>0$ such
that for all positive integer $r$, if $M$ is an
${\mathbb{F}}_{p}$-representable rank-$r$ matroid with at least $C_{t}r^{2}$
elements then $M$ contains ${\text{P}G}(t-1,p)$ as a minor.

Proof of Lemma 18 (when ${\mathbb{F}}={\mathbb{F}}_{p}$).  Let $C_{t}$ be the
constant in Theorem 22. We prove that a.a.s. $M^{\prime}$ has rank $r$ and at
least $\binom{r}{k}$ elements. Since $k\geq 3$, this implies that $M^{\prime}$
contains at least $C_{t}r^{2}$ elements by choosing sufficiently large $r$ and
consequently, $M^{\prime}$ contains ${\text{P}G}(t-1,p)$ as a minor by Theorem
22.

Recall that $M^{\prime}=M[A^{6}]$. By (3), $\text{rank}(M^{\prime})=r$. By
Lemma 21, let $u_{1},\ldots,u_{r}$ be column vectors of $B^{[r]}$ that form a
$\delta$-dense basis for $\mathbb{F}_{p}^{r}$. Let
$\alpha=(\alpha_{1},\ldots,\alpha_{k})$ be such that
${\mathcal{P}}(\alpha_{1},\ldots,\alpha_{k})>0$. Let $u_{J}=[u_{j}]_{j\in J}$
be the matrix obtained by including all column vectors in $\\{u_{j}:\ j\in
J\\}$. Define

$S=\\{u_{J}\alpha^{T}:\ J\subseteq[r],|J|=k.\\}$

Then $|S|=\binom{r}{k}$. It suffices to prove that $A^{6}$ contains all
vectors in $S$.

Fix $v\in S$, For $1\leq j\leq\epsilon_{2}n$, let $X^{v}_{j}$ be the indicator
variable that

$B^{[r]}v^{\prime}_{j}=v,\quad\mbox{and}\
v^{\prime}_{j}\in\langle(A_{5})_{U}\rangle.$

Thus, $v$ is a column vector of $A^{6}$ if $\sum_{1\leq
j\leq\epsilon_{2}n}X^{v}_{j}\geq 1$. Suppose
$v=\sum_{j=1}^{k}\alpha_{j}u_{i_{j}}$ for some
$\\{u_{i_{1}},\ldots,u_{i_{k}}\\}\subseteq\\{u_{1},\ldots,u_{r}\\}$. Since
$u_{1},\ldots,u_{r}$ are all $\delta$-dense, and
${\mathcal{P}}(\alpha_{1},\ldots,\alpha_{k})>0$,
${\mathbb{P}}(B^{[r]}v^{\prime}_{j}=v)=\Omega(\delta)$, since
${\text{supp}\left(v_{j}^{\prime}\right)}$ is uniform in
$\binom{{\mathcal{I}}}{k}$, where
${\mathcal{I}}={\texttt{Row}}({(A^{1})_{\text{2-core}}})$. Thus,

${\mathbb{P}}(X^{v}_{j}=1)=\Omega(\delta)-{\mathbb{P}}(v^{\prime}_{j}\notin\langle(A_{5})_{U}\rangle)=\Omega(\delta),$

as ${\mathbb{P}}(v^{\prime}_{j}\notin\langle(A_{5})_{U}\rangle)=o(1)$ by Lemma
15 and the choice that $\epsilon_{1}=o(\eta)$. By the Chernoff bound,

${\mathbb{P}}\left(\sum_{1\leq
j\leq\epsilon_{2}n}X^{v}_{j}=0\right)=\exp(-\Omega(\epsilon_{2}n)),$

and thus by the union bound, a.a.s. $\sum_{1\leq
j\leq\epsilon_{2}n}X^{v}_{j}\geq 1$ for every $v\in S$. Hence, a.a.s. $A^{6}$,
the matrix representing $M^{\prime}$, contains all $\binom{r}{k}$ vectors in
$S$.

###  5.2 Proof of Lemma 18 when ${\mathbb{F}}={\mathbb{F}}_{q}$ where $q$ is a
prime power

In this section, let $\mathbb{F}=\mathbb{F}_{q}$ where $q$ is a prime power.
Consequently, we assume that ${\mathcal{P}}$ is a permutation-invariant
distribution on $({\mathbb{F}}_{q}^{*})^{k}$ such that
${\mathcal{P}}(\sigma_{1},\ldots,\sigma_{k})>0$ for every
$(\sigma_{1},\ldots,\sigma_{k})\in({\mathbb{F}}_{q}^{*})^{k}$, as required in
the hypotheses of Theorem 4.

Given integer $\ell\geq 1$, a matrix $A\in\mathbb{F}^{R\times E}$ is said
_$\ell$ -complete_ if $|R|\geq\ell$ and, for every nonzero vector
$v\in\mathbb{F}^{R}$ with support size at most $\ell$, there is a nonzero
column of $A$ that is parallel to $v$. (So an $\mathbb{F}_{q}$-complete matrix
has at least $\frac{1}{q-1}\sum_{i=1}^{\ell}\binom{|R|}{i})$ columns.) We say
a matroid $M$ is _$\ell$ -complete_ if it is represented by an $\ell$-complete
matrix $A$. Since such an $A$ has (a multiple of) each standard basis vector
as a column, the rank of such an $M$ is equal to the number of rows of $A$.

######  Lemma 23.

Let $s\geq\ell\geq 3$. If $M$ is an $\ell$-complete
$\mathbb{F}_{q}$-representable matroid of rank at least $s+q^{2}\binom{s}{2}$,
then $M$ has an $(\ell+1)$-complete minor of rank $s$.

Proof.  Let $A$ be a $k$-complete matrix representing $M$. By possibly
removing some rows and their corresponding support-one columns of $A$ to
obtain a minor of $M$, we may assume that $A$ has precisely
$s+q^{2}\binom{s}{2}$ rows. Identify the rows of $A$ with the set $R_{1}\cup
R_{2}$, where $R_{1}=[s]$ and $R_{2}=\mathbb{F}^{2}\times\binom{[s]}{2}$. Let
$\\{x_{i}:i\in[s]\\}\cup\\{y_{\alpha,\beta,I}:\alpha,\beta\in\mathbb{F},I\in\binom{[s]}{2}\\}$
be the corresponding collection of standard basis vectors of $\mathbb{F}^{R}$,
where $R=R_{1}\cup R_{2}$. The columns of $A$ corresponding to these vectors
$\\{x_{i}\\}$ and $\\{y_{\alpha,\beta,I}\\}$ are indexed by elements in $R$.

For each $\alpha\in\mathbb{F}$ and $I=\\{i_{1},i_{2}\\}\in\binom{[s]}{2}$ with
$i_{1}<i_{2}$, let $v_{\alpha,\beta,I}=y_{\alpha,\beta,I}-\alpha
x_{i_{1}}-\beta x_{i_{2}}$. Since $k\geq 3$ and this vector has support $3$,
the matrix $A$ has a nonzero column parallel to $v_{\alpha,\beta,I}$; let
$e_{\alpha,\beta,I}$ be the corresponding element of $M$; thus,
$e_{\alpha,\beta,I}=\mu v_{\alpha,\beta,I}$ for some $\mu\in\mathbb{F}^{*}$.
We will contract the set
$C=\\{e_{\alpha,\beta,I}:\alpha,\beta\in\mathbb{F},I\in\binom{[s]}{2}\\}$ to
obtain the desired $(k+1)$-complete minor.

Let $A^{\prime}$ be the matrix obtained from $A$ by the following sequence of
operations. For each $\alpha,\beta\in\mathbb{F}$ and
$I=\\{i,j\\}\in\binom{[s]}{2}$ with $i<j$, adding $\alpha$ times the
$({\alpha,\beta,I})$-row of $A$ to the $i$-row and $\beta$ times the
$({\alpha,\beta,I})$-row to the $j$-row. Now, for each $I$, the $I$-column of
$A^{\prime}$ is a multiple of the standard basis vector $y_{I}$. Therefore
$M/C=M[B]$, where $B$ is obtained from $A^{\prime}$ by removing all the rows
indexed by $I$, and removing all columns indexed by $C$.

We need to show that for each $u\in\mathbb{F}^{s}\setminus\\{0\\}$ of support
at most $k+1$, there is a nonzero column of $B$ parallel to $u$. That is, for
each such $u$, there are distinct $\ell_{1},\dotsc,\ell_{k+1}\in[s]$ and some
$(\lambda_{1},\dotsc,\lambda_{k+1})\in\mathbb{F}^{k+1}\setminus\\{0\\}$ such
that $u$ is nonzero outside the rows in $\\{\ell_{1},\dotsc,\ell_{k+1}\\}$,
and has entry $\lambda_{i}$ in row $\ell_{i}$. Consider the following vector
in $\mathbb{F}^{R}$:

$v=y_{\lambda_{1},\lambda_{2},\\{\ell_{1},\ell_{2}\\}}+\sum_{i=3}^{k+1}\lambda_{i}x_{\ell_{i}}.$

It is clear that $v$ is nonzero and has support at most $k$, and so $\mu v$ is
a column of $A$ for some $\mu\in\mathbb{F}^{*}$. Since the only nonzero entry
of $v$ indexed by $R_{2}$ is the $y_{\ell_{1},\ell_{2}}$ entry, it is routine
to verify that the corresponding column of $A^{\prime}$ is obtained from $v$
by adding $\lambda_{1}$ to the $\ell_{1}$-entry, and $\lambda_{2}$ to the
$\ell_{2}$-entry, which gives the vector
$v^{\prime}=\mu(y_{\lambda_{1},\lambda_{2},\\{\ell_{1},\ell_{2}\\}}+\sum_{i=1}^{k+1}\lambda_{i}x_{\ell_{i}})$.
Since $(\lambda_{1},\dotsc,\lambda_{k+1})\neq 0$, and all columns in $C$ are
zero on the $R_{1}$-indexed entries, it follows that $v^{\prime}$ is not
parallel to any column in $C$. Removing the $R_{2}$ indexed entries from
$v^{\prime}$ gives (a multiple of) the desired vector $u$ as a column of $B$.

######  Lemma 24.

Let $t\geq 3$, and $q$ be a prime power. If $A$ is a matrix over
$\mathbb{F}_{q}$ with at least $(qt)^{2^{t}}$ rows, and every standard basis
vector and every support-three vector is a column of $A$, then $M(A)$ has a
${\text{P}G}(t-1,q)$-minor.

Proof.  For each $k\in\\{3,\dotsc,t\\}$, let $n_{k}=(q^{2}t)^{2^{t-k}}/q^{2}$.
By the hypothesis, the matrix $A$ has more than $n_{3}$ rows; let $A^{\prime}$
be obtained from $A$ by removing $\text{rank}(A)-n_{3}$ rows and the
corresponding standard basis vector column. Now $M(A^{\prime})$ is a minor of
$M(A)$, and all support-three vectors are columns of $A^{\prime}$, so
$M(A^{\prime})$ is $3$-complete with rank equal $n_{3}$. Let
$k\in\\{3,\dotsc,t\\}$ be the maximum integer so that $M$ has a $k$-complete
minor $M_{k}$ of rank at least $n_{k}$.

If $k<t$, then $M_{k}$ is $k$-complete with rank $n_{k}$. Now

$n_{k}=(q^{2}t)^{2^{t-k}}/q^{2}=((q^{2}t)^{2^{t-(k+1)}})^{2}/q^{2}=(q^{2}n_{k+1})^{2}/q^{2}\geq
n_{k+1}+q^{2}\tbinom{n_{k+1}}{2}$

so by Lemma 23, the matroid $M_{k}$ has a $(k+1)$-complete minor of rank
$n_{k+1}$, which contradicts the maximality of $k$.

If $k=t$, then $M$ has a $t$-complete minor $M_{t}$ of rank $n_{t}=t$, with a
$t$-complete representation $A_{t}$. Since every nonzero vector in
$\mathbb{F}_{q}^{t}$ is parallel to a column of $A_{t}$, we have
$M_{t}=M(A_{t})\cong{\text{P}G}(t-1,q)$, so $M$ has the required minor.

Proof of Lemma 18 (when $\mathbb{F}=\mathbb{F}_{q}$). Let $r=(qt)^{2^{t}}$.
Recall that $M^{\prime}=M[A^{6}]$. By Lemma 24, it suffices to prove that
a.a.s. $A^{6}$ is row equivalent to a matrix $C$ such that the column vectors
in $C$ contain every standard basis vector, and every support-three vector in
$\mathbb{F}_{q}^{r}$. By Lemma 21, let $u_{1},\ldots,u_{r}$ be a
$\delta$-dense basis of $B_{[r]}$ for $\mathbb{F}_{q}^{r}$. Let

$S=\\{[u_{1},\ldots,u_{r}]\alpha:\alpha\in\mathbb{F}_{q}^{r},1\leq|{\text{supp}\left(\alpha\right)}|\leq
k\\}.$

Again by the standard Chernoff bound and an analogous argument as in the proof
of this lemma for the prime field case, it is easy to see that a.a.s. $A^{6}$
contains every vector in $S$. In particular, $A^{6}$ contains all vectors
$u_{1},\ldots,u_{r}$. Applying row operations to reduce $[u_{1},\ldots,u_{r}]$
to the identity matrix, these row operations reduce $A^{6}$ to a matrix $C$
which contains all vectors in

$S^{\prime}=\\{\alpha\in\mathbb{F}_{q}^{r}:1\leq|{\text{supp}\left(\alpha\right)}|\leq
k\\}.$

Since $k\geq 3$, $C$ contains every standard basis vector, and every support-
three vector in $\mathbb{F}_{q}^{r}$, as desired.

##  6 Proof of the key lemma: Lemma 16

Recall that $B=(A^{\prime\prime})^{-1}$. As before, let $U$ denote the set of
columns in $A^{\prime\prime}$ and let $U_{0}\subseteq U$ denote the set of
columns in ${(A^{1})_{\text{2-core}}}$. Let $b_{1},\ldots,b_{n^{\prime}}$ be
the row vectors of $B$, where $n^{\prime}=|U|$. Recall also that
$n_{1}=|U_{0}|$ which is the number of columns in ${(A^{1})_{\text{2-core}}}$,
and that $n^{\prime}=(1+O(\epsilon_{1}))n_{1}=\Theta(n)$.

For each $1\leq i\leq n^{\prime}$, let $b_{i}=(b_{ij})_{1\leq j\leq
n^{\prime}}$ denote the $i$-th row vector. Let $a_{1},\ldots,a_{n^{\prime}}$
denote the rows of $A^{\prime\prime}$. Since $BA^{\prime\prime}=I$, we know
that $b_{i}A^{\prime\prime}=e_{i}$, where $e_{i}$ is the $i$-th standard basis
row vector. In other words,

$\sum_{j=1}^{n^{\prime}}b_{ij}a_{j}=e_{i},\quad\mbox{for every $1\leq i\leq
n^{\prime}$}.$

It is more convenient to index the right hand side above by the columns of
$A^{\prime\prime}$, and index entries of $B$ by rows and columns of
$A^{\prime\prime}$ accordingly. That is, we may equivalently write

$\sum_{j\in{\texttt{Row}}(A^{\prime\prime})}b_{ij}a_{j}=e_{i},\quad\mbox{for
every $i\in U$}.$ (5)

It is helpful to recall that $A^{\prime\prime}$ contains all but
$O(\epsilon_{1}n)$ rows of ${\texttt{Row}}({(A^{1})_{\text{2-core}}})$ by
Lemma 14.

For each row vector $a_{i}$, the components of $a_{i}$ are indexed by columns
in $U$. As $U_{0}\subseteq U$, let $\bar{a}_{i}$ be the row vector obtained
from $a_{i}$ by dropping the components that are not in $U_{0}$, for every
$i\in{\texttt{Row}}({(A^{1})_{\text{2-core}}})\supseteq{\texttt{Row}}(A^{\prime\prime})$.
It is much easier to analyse row vectors $\bar{a}_{i}$ than $a_{i}$ since we
know little about the distribution of the column vectors in $U\setminus
U_{0}$. In particular, they are not independent copies of ${\boldsymbol{v}}$.
By considering $b_{i}\left[\begin{subarray}{c}\vdots\\\ \bar{a}_{j}\\\
\vdots\end{subarray}\right]$ for $i\in U_{0}$, it follows now that

$\sum_{j\in{\texttt{Row}}(A^{\prime\prime})}b_{ij}\bar{a}_{j}=e_{i},\quad\mbox{for
every $i\in U_{0}$}.$

Let $J\subseteq[r]$ and $\alpha\in\mathbb{F}^{J}$. It follows then that

$\sum_{j\in{\texttt{Row}}(A^{\prime\prime})}\Big{(}\sum_{i\in
J}\alpha_{i}b_{i}\Big{)}_{j}\bar{a}_{j}=\sum_{i\in J}\alpha_{i}e_{i}.$

The right hand side above is a row vector that is everywhere zero except for
entries in $J$. That is,

$\sum_{j\in{\texttt{Row}}(A^{\prime\prime})}\Big{(}\sum_{i\in
J}\alpha_{i}b_{i}\Big{)}_{j}\bar{a}_{jh}=0,\quad\mbox{for all $h\in
U_{0}\setminus J$}.$ (6)

Let $U_{0}=\\{v_{1},\ldots,v_{n_{1}}\\}$ denote the set of columns in $U_{0}$.
Let ${\text{supp}\left(v_{h}\right)}|_{A^{\prime\prime}}$ be the set of
nonzero entries in column $v_{h}$ of $A^{\prime\prime}$ (i.e. the set of
$j\in{\texttt{Row}}(A^{\prime\prime})$ such that $\bar{a}_{jh}\neq 0$). Then,
to satisfy (6), it is necessary that for every $h\in U_{0}\setminus J$, the
set

${\mathcal{Z}}^{\alpha,J}_{h}:=\left\\{j\in{\text{supp}\left(v_{h}\right)}|_{A^{\prime\prime}},\Big{(}\sum_{i\in
J}\alpha_{i}b_{i}\Big{)}_{j}\neq 0\right\\}$ (7)

is either empty or has cardinality at least two.

######  Definition 25.

Let $H=H[{(A^{1})_{\text{2-core}}}]$ be the hypergraph where
$V(H)=\\{v_{1},\ldots,v_{n_{1}}\\}$ is the set of columns of
${(A^{1})_{\text{2-core}}}$, and $E(H)$ is the set of subsets $\\{j\in
V(H):\bar{a}_{ij}\neq 0\\}$, for each
$i\in{\texttt{Row}}({(A^{1})_{\text{2-core}}})$. The size of the edge
$\\{j:\bar{a}_{ij}\neq 0\\}$ is the cardinality of this set. An edge is called
a $j$-edge if its size is $j$.

Recall from (5) that the rows of $B$ are indexed by columns in $U\supseteq
U_{0}$. Given any $i\in U_{0}$, let $H^{\alpha}_{i}$ denote the subgraph of
$H$ obtained by including edges

$\\{\bar{a}_{j}:\ \alpha_{i}b_{ij}\neq 0\\},$

and then deleting all the isolated vertices. Analogously, given a subset
$J\subseteq U_{0}$, let $H^{\alpha}_{J}$ be the subgraph obtained by including
all edges $\bar{a}_{j}$ where $\sum_{i\in J}\alpha_{i}b_{ij}\neq 0$, and then
deleting all the isolated vertices. Obviously if
${\mathcal{Z}}^{\alpha,J}_{h}$ has cardinality zero or at least two for every
$h\in U_{0}\setminus J$ then all vertices in $V(H^{\alpha}_{J})\setminus J$
must be incident to at least two edges in $H^{\alpha}_{J}$ (as there are no
isolated vertices in $H^{\alpha}_{J}$).

Consequently, to confirm Lemma 16, it is then sufficient to prove that a.a.s.

$\mbox{for all nonzero $\alpha\in\mathbb{F}^{r}$:}\ H^{\alpha}_{J}\ \mbox{has
at least $\delta n$ edges for every $J\subseteq[r]$}$ (8)

We prove (8) by studying subgraphs of $H$ where all but at most $|J|\leq r$
vertices have degree at least two.

Given a positive integer $h$, let ${\mathscr{Y}}^{\delta n}_{h}$ denote the
set of subgraphs $S$ of $H$ such that

  * •

$|E(S)|\leq\delta n$; and

  * •

exactly $h$ vertices of $S$ have degree one; and

  * •

all the other vertices in $S$ have degree at least two.

We can confirm (8) if $\cup_{h=1}^{r}{\mathscr{Y}}^{\delta n}_{h}$ is a.a.s.
empty. However, this is far from being true. Indeed, for every fixed $h\geq 2$
we have $|{\mathscr{Y}}^{\delta n}_{h}|=\Omega(n)$. To see this, consider
$h=2$. Clearly, any subgraph $S$ composed of a single 2-edge is a member of
${\mathscr{Y}}^{\delta n}_{2}$ and it is easy to prove that a.a.s. there are
$\Omega(n)$ $2$-edges in $H$. Analogously, for any $h\geq 3$, we immediately
find that $|{\mathscr{Y}}^{\delta n}_{h}|=\Omega(n^{\left\lfloor
h/2\right\rfloor})$ by only considering members of ${\mathscr{Y}}^{\delta
n}_{h}$ that are some sort of pseudo-forest (see Definition 30). However,
since randomly permuting vertices in $H$ does not change its distribution, we
may regard $[r]$ as a random subset of $r$ vertices of $H$. Provided that

$|{\mathscr{Y}}^{\delta n}_{h}|=o(n^{h}),\quad\mbox{for all $1\leq h\leq r$,}$
(9)

the probability that the set of leaf-vertices (vertices with degree one) in
any member of ${\mathscr{Y}}^{\delta n}_{h}$ is a subset of $[r]$ is $o(1)$.
Thus it suffices to confirm (9), as (8) follows by taking union bound over
$1\leq h\leq r$.

It is sometimes convenient to represent $H$ by a bipartite graph that is
called the Tanner graph of $H$, defined below.

######  Definition 26.

Given a hypergraph $G$, the Tanner graph of $G$, denoted by
${\mathcal{T}}_{G}$, is the bipartite graph on $V(G)\cup E(G)$, where $ux\in
V(G)\times E(G)$ is an edge in ${\mathcal{T}}_{G}$ if $u\in x$ in $G$. We call
elements in $V(G)$ the vertex-nodes of ${\mathcal{T}}_{G}$, and elements in
$E(G)$ the edge-nodes of ${\mathcal{T}}_{G}$.

We start from the distribution of $H$ and the size of the edges in $H$. We
first define a few parameters and a technical lemma. Let

$f(x)=\frac{x(e^{x}-1)}{e^{x}-1-x}.$

######  Lemma 27.

$f(x)$ is an increasing function on $x>0$, and $\lim_{x\to 0+}f(x)=2$.

Proof.  By considering $f^{\prime}(x)$, it is sufficient to prove that
$e^{2x}-(2+x^{2})e^{x}+1>0$ for every $x>0$, which follows by

$\displaystyle e^{2x}-(2+x^{2})e^{x}+1$
$\displaystyle=(e^{x}-1-x-x^{2}/2)^{2}+1+2xe^{x}-(1+x+x^{2}/2)^{2}$
$\displaystyle>(e^{x}-1-x-x^{2}/2)^{2}+1+2x(1+x+x^{2}/2+x^{3}/6)-(1+x+x^{2}/2)^{2}$
$\displaystyle=(e^{x}-1-x-x^{2}/2)^{2}+x^{4}/12>0.$

The assertion that $\lim_{x\to 0+}f(x)=2$ follows by taking the Tayler
expansion of $e^{x}=1+x+x^{2}/2+O(x^{3})$.

Given $c>2$, let $\mu(c)$ be the unique positive root of

$\frac{\sum_{j\geq 2}je^{-\mu}\mu^{j}/j!}{\sum_{j\geq
2}e^{-\mu}\mu^{j}/j!}=f(\mu)=c.$

Note that the existence and uniqueness of $\mu(c)$ is guaranteed by Lemma 27.
Further, define $\beta=\beta_{k}$ where

$\beta_{k}=\dfrac{e^{-\mu}\mu^{2}/2}{\sum_{j\geq
2}e^{-\mu}\mu^{j}/j!},\quad\mbox{where $\mu=\mu(k)$.}$

Recall that $n_{1}=|V(H)|=\Theta(n)$.

######  Lemma 28.

  1. (a)

The number of 2-edges in $H$ is a.a.s. $(\beta_{k}+O(\epsilon_{1}))n_{1}$
where $\beta_{k}<0.45$ for every $k\geq 3$.

  2. (b)

Conditional on the number of edge-nodes in ${\mathcal{T}}_{H}$, and the
degrees of all nodes in ${\mathcal{T}}_{H}$, ${\mathcal{T}}_{H}$ is uniformly
distributed over all bipartite graphs with the given number of nodes and
degrees of the nodes.

  3. (c)

The maximum degree of ${\mathcal{T}}_{H}$ is $O(\log n)$.

Proof.  By reversing the vertices and edges in $H$, the 2-edges in $H$
correspond to the vertices of degree two in the 2-core of a random $k$-uniform
hypergraph where the ratio of number of vertices and the number of $k$-edges
in the 2-core is $1+O(\epsilon_{1})$. The 2-core of such a random hypergraph
is well studied, and it is known that the distribution of the proportion of
vertices with degree two is asymptotically truncated Poisson with parameter
$\mu=(1+O(\epsilon_{1}))\mu(k)$ where $\mu(k)$ is the root of $f(\mu)=k$. We
refer the reader to [5, Theorem 3.3] for a proof of this assertion. Since
$\mu_{3}\approx 2.1491258$. It follows from Lemma 27 that $\mu_{k}>2$ for
every $k\geq 3$. The derivative of $x^{2}/2(e^{x}-1-x)$ is negative for all
$x>2$. Hence, $\beta_{k}\leq\beta_{3}\approx.4254370997$. This confirms part
(a). Part (b) is obvious: consider any two bipartite graphs $G_{1}$ and
$G_{2}$ in the support of the probability space in part (b). Suppose $A$ is a
matrix in the support of the probability space of $A^{1}$ such that the Tanner
graph of $H[{A_{\text{2-core}}}]$ is $G_{1}$, then replacing $G_{1}$ by
$G_{2}$ yields another matrix $B$ such that the Tanner graph of
$H[{B_{\text{2-core}}}]$ is $G_{2}$. Since $A$ and $B$ appear with equal
probability as being $A^{1}$, $G_{1}$ and $G_{2}$ must appear with equal
probability. Part (c) follows from well known results in the literature on the
degrees of vertices of a random $k$-uniform hypergraph, and we skip its proof.

We use the configuration model, introduced by Bollobás [4], to analyse $H$
conditioning the set of vertex-nodes, the edge-nodes, and the degree sequence.
Represent each node $u$ by a bin containing $d_{u}$ points where $d_{u}$ is
the degree of $u$. Uniformly at random match points in the bins representing
edge-nodes to points in the bins representing vertex-nodes. By contracting
each bin to a node, and each matched pair of points as an edge, the matching
yields a bipartite multigraph with the given degree sequence. Conditional on
the resulting bipartite graph being simple, the configuration model generates
a bipartite graph with the same distribution as $H$. A simple counting
argument as in [4] shows that the probability that the configuration model
generates a simple bipartite graph in our setting is $\Omega(1)$. Thus, any
property that is a.a.s. true in the configuration model is a.a.s. true for
$H$. For simplicity, when we use the configuration model, we still call bins
the vertex-nodes and edge-nodes.

We pay particular attention to the 2-edges in $H$. For convenience, colour all
2-edges of $H$ red and let ${H_{\text{red}}}$ denote the subgraph of $H$
induced by the red edges. Note that (9) cannot be true if ${H_{\text{red}}}$
has a linear component with $o(n)$ diameter. Suppose it does. Then the largest
component of ${H_{\text{red}}}$ has a spanning tree $T$ consisting of
$\Omega(n)$ vertices. For every $u,v$ in $T$, the $(u,v)$-path in $T$ is a
subgraph of $H$, which is also a member of ${\mathscr{Y}}^{\delta n}_{2}$. It
would immediately imply that $|{\mathscr{Y}}^{\delta n}_{2}|=\Omega(n^{2})$,
contradicting (9). Our next target is to prove that ${H_{\text{red}}}$ does
not contain any large component.

######  Lemma 29.

A.a.s every component of ${\mathcal{T}}_{{H_{\text{red}}}}$ has order $O(\log
n)$.

Proof.  ${\mathcal{T}}_{{H_{\text{red}}}}$ has $n_{1}$ vertex-nodes and
$(\beta_{k}+O(\epsilon_{1}))n_{1}$ edge-nodes by Lemma 28. Consider the
configuration model: every point in the set of degree-two edge-nodes are
uniformly matched to one of the $kn_{1}$ points in the vertex-nodes. Colour
the points that are contained in degree-two edge-nodes red. Starting from any
red point $p$, let $v$ be the vertex that contains the point that $p$ is
matched to. For each of the remaining $k-1$ points $p^{\prime}$ in $v$ (other
than the one matched to $p$), the probability that it is matched to a red
point is

$\rho\sim\frac{2\beta_{k}}{k}+O(\epsilon_{1}).$

Hence, the expected number of red points by this 1-step branching process
starting from $p$ is $(k-1)\rho<2\beta_{k}<1$ by Lemma 28(a). By a standard
coupling argument comparing with a full branching process whose expected
number of children in each step is less than one, the claim of the lemma
follows immediately. We leave the details of the proof as a simple exercise.

######  Definition 30.

A hypergraph $G$ is called a pseudo-forest if all vertices have degree at
least one, and ${\mathcal{T}}_{G}$ is a forest (i.e. ${\mathcal{T}}_{G}$ is
acyclic). A vertex in a pseudo-forest is called a leaf if its degree is equal
to one.

We are ready to count ${\mathscr{Y}}^{\delta n}_{h}$. It is easy to bound the
number of members in ${\mathscr{Y}}^{\delta n}_{h}$ that are pseudo-forests.
Note that every pseudo-forest must have at least two leaves.

######  Lemma 31.

Let $h\geq 2$. A.a.s. the number of subgraphs of $H$ that are pseudo-forests
with at most $h$ leaves is $O((n\log^{2h}n)^{h/2})$.

Proof.  Let $F$ be a subgraph of $H$ which is a pseudo-forest. Then every
component of $F$ must have at least two leaves. Thus, $F$ has at most $h/2$
components. We call a pseudo-forest a pseudo-tree if its tanner graph is
connected. It is thus sufficient to prove that there are a.a.s.
$O(n\log^{2h}n)$ pseudo-trees in $H$ with at most $h$ leaves.

Suppose $T$ is a pseudo-tree, we obtain $P(T)$ by contracting every 2-edges in
$T$; we call $P(T)$ the profile of $T$. See Figure 1 below for an
illustration. The round nodes are vertex-nodes and the square nodes are edge-
nodes. Edge-nodes with degree two are coloured red. After contracting all the
2-edges, i.e. contracting all red edge-nodes in the Tanner graph, vertices
$v_{1}$, $v_{2}$ and $v_{3}$ are merged to a single vertex, labelled as
$v_{1}$ in the figure on the right hand side. After contraction, all red
square nodes disappear. Notice that $P(T)$ has the same number of leaves as
$T$. Suppose that $T$ is a pseudo-tree with $h$ leaves. It is easy to see that
$P(T)$ has at most $h$ edges, since every edge in $P(T)$ has size at least
three, and $P(T)$ has $h$ leaves. It follows now that for a fixed $h$, there
are at most $O(1)$ possible profiles (i.e. pseudo-trees where every edge has
size at least three) with $h$ leaves. Fix a profile $P$, we prove that the
number of pseudo-trees $T$ in $H$ such that $P(T)=P$ is $O(n\log^{2h}n)$. Then
summing over all $O(1)$ possible $P$ gives our desired bound on the number of
pseudo-trees in $H$.

Figure 1: The figure on the left is the Tanner graph of a pseudo-tree $T$; the
figure on the right is the Tanner graph of $P(T)$.

Pick an arbitrary vertex $u$ in $P$. Obviously there are at most $n_{1}\leq n$
ways to choose $u$ in $H$. Enumerate all edges $e_{1},\ldots,e_{\ell}$,
($\ell\leq h$) in $P$ by a BFS-tree starting from $u$. We embed these edges or
their counterparts in $H$ (corresponding to certain paths in
${\mathcal{T}}_{H}$ defined below) one at a time, and count the number of
choices for $e_{i}$, given the embedding of $e_{1},\ldots,e_{i-1}$. Suppose
the parent of the edge-node $e_{i}$ in ${\mathcal{T}}_{P}$ is vertex-node $v$,
and suppose that $e_{1},\ldots,e_{i-1}$ has already been embedded into $H$.
That means, $v$ is already embedded into $H$. To embed $e_{i}$ into $H$, we
need to find an edge $e$ in $H$ whose size is equal to $e_{i}$, and a
$(v,e)$-path in ${\mathcal{T}}_{H}$ such that all the internal edge-nodes are
red. For example, take $P$ whose Tanner graph ${\mathcal{T}}_{P}$ is given by
the right hand side of Figure 1. Given $v_{1}$ embedded into $H$ already, in
order to embed the edge $a$, we need to find a $(v_{1},a)$-path in
${\mathcal{T}}_{H}$ as shown on the left hand side of Figure 1. We prove that
for each $i$, there are $O(\log^{2}n)$ ways to embed $e_{i}$.

######  Claim 32.

There are $O(\log^{2}n)$ choices for $(e,P)$ in $H$, such that $e$ has the
same size as $e_{i}$, and $P$ is a $(v,e)$-path in ${\mathcal{T}}_{H}$ such
that all the internal edge-nodes are red.

Since there are $h$ edges in $P(T)$, the lemma follows immediately. It remains
to prove the claim.

Proof of Claim 32.  By Lemma 29, there are $O(\log n)$ choices for a
$(v,u)$-path in ${\mathcal{T}}_{H}$ such that $u$ is a vertex node, and all
the internal edge-nodes are red. Then, by Lemma 28(c), given $u$, there are
$O(\log n)$ choices for an edge $e$ incident to $u$ such that the size of $e$
is equal to the size of $e_{i}$. Combining them together yields the claim.

Next we treat members of ${\mathscr{Y}}^{\delta n}_{h}$ that are not pseudo-
forests. Suppose $S\in{\mathscr{Y}}^{\delta n}_{h}$ and ${\mathcal{T}}_{S}$
contains a cycle. Then, we can repeatedly remove leaves from
${\mathcal{T}}_{S}$ until we obtain a subgraph of ${\mathcal{T}}_{S}$ whose
minimum degree is at least two. This subgraph is known as the 2-core of
${\mathcal{T}}_{S}$, denoted by ${({\mathcal{T}}_{S})_{\text{2-core}}}$. The
notation of the 2-core of a graph and hypergraph is analogous to Definition 13
by treating $A$ as the transpose of a weighted incidence matrix of a
hypergraph. Since ${\mathcal{T}}_{S}$ contains a cycle,
${({\mathcal{T}}_{S})_{\text{2-core}}}$ is nonempty. However, the hypergraph
with Tanner graph ${({\mathcal{T}}_{S})_{\text{2-core}}}$ is not necessarily a
subgraph of $H$, and in particular, ${({\mathcal{T}}_{S})_{\text{2-core}}}$ is
not necessarily ${\mathcal{T}}_{{H_{\text{2-core}}}}$. This is because that it
is possible that there is some edge-node $x$ in
${({\mathcal{T}}_{S})_{\text{2-core}}}$ with smaller degree than its degree in
${\mathcal{T}}_{H}$, and thus the edge corresponding to $x$ in the hypergraph
corresponding to the Tanner graph ${({\mathcal{T}}_{S})_{\text{2-core}}}$ is
not an edge in $H$. Look at the example in Figure 2. The bipartite graph
${\mathcal{T}}_{G}$ in the middle is the Tanner graph of the hypergraph $G$ on
the left, and the bipartite graph on the right is
${({\mathcal{T}}_{G})_{\text{2-core}}}$, the 2-core of ${\mathcal{T}}_{G}$.
The edge-node $a$ in ${\mathcal{T}}_{G}$ has degree 3, whereas it has degree 2
in ${({\mathcal{T}}_{G})_{\text{2-core}}}$ after the removal of $u$, and thus
the edge-node $a$ in ${({\mathcal{T}}_{G})_{\text{2-core}}}$ does not
correspond to an edge of $G$ any more. Indeed, the 2-core of $G$ is empty,
whereas ${({\mathcal{T}}_{G})_{\text{2-core}}}$ is nonempty. Obviously, to
relate ${({\mathcal{T}}_{S})_{\text{2-core}}}$ to the “correct subgraph” of
$S$ (which is not ${\mathcal{T}}_{{S_{\text{2-core}}}}$ as illustrated by the
above example), we need to treat edge-nodes in
${({\mathcal{T}}_{S})_{\text{2-core}}}$ whose degrees are smaller than their
degrees in $S$.

Figure 2: An example of a hypergraph, its Tanner graph, and the 2-core of its
Tanner graph

######  Definition 33.

Given a subgraph $S^{\prime}$ of a Tanner graph $S$, we say an edge-node $x$
in $S^{\prime}$ has excess $t$, if $\deg_{S}(x)=\deg_{S^{\prime}}(x)+t$. The
excess of $S^{\prime}$ is defined by the total excess of all edge-nodes in
$S^{\prime}$. The closure of $S^{\prime}$, denoted by
${\text{c}l}(S^{\prime})$, is the minimum Tanner graph such that
$S^{\prime}\subseteq{\text{c}l}(S^{\prime})\subseteq S$, $S^{\prime}$ and
${\text{c}l}(S)$ have the same set of edge-nodes, and
$\deg_{S}(x)=\deg_{{\text{c}l}(S^{\prime})}(x)$ for every edge-node $x$ of
${\text{c}l}(S^{\prime})$.

For example, let $S$ be the Tanner graph in the middle of Figure 2, and let
$S^{\prime}$ be the graph on the right hand side of Figure 2. Then, edge-node
$a^{\prime}$ in $S^{\prime}$ has excess 1, and all the other edge-nodes in
$S^{\prime}$ has excess 0. In this example, ${\text{c}l}(S^{\prime})=S$.

We will count non-pseudo-forest members of ${\mathscr{Y}}^{\delta n}_{h}$ in
an inside-out manner. First we bound the number of subgraphs $S^{\prime}$ of
${\mathcal{T}}_{H}$ that can potentially be
${({\mathcal{T}}_{S})_{\text{2-core}}}$ for some $S\in{\mathscr{Y}}^{\delta
n}_{h}$. Then, we start from such an $S^{\prime}$, and find all possible
subgraphs $G$ of $H$ such that $G\in{\mathscr{Y}}^{\delta n}_{h}$ and
${({\mathcal{T}}_{G})_{\text{2-core}}}=S^{\prime}$. Recall the procedure of
obtaining the 2-core of a Tanner graph by repeatedly removing leaves.
Recovering $G$ from ${({\mathcal{T}}_{G})_{\text{2-core}}}=S^{\prime}$ can be
done by first finding ${\text{c}l}(S^{\prime})$ and then apply a reverse
procedure, which repeatedly extends ${\text{c}l}(S^{\prime})$ by attaching
some tree-structures. We formally define the procedure below.

Given a subgraph $S$ of a hypergraph $H$, we say that we attach a leaf-edge
$x$ to $S$, if we obtain a subgraph $S\subseteq S^{\prime}\subseteq H$ by
adding into $S$ a set of vertices $v_{1},\ldots,v_{t}\notin V(S)$ and an edge
$x\in E(H)$, where $x=\\{v_{0},v_{1},\ldots,v_{t}\\}$ for some $v_{0}\in
V(S)$. A subgraph $S^{\prime}$ of $H$ is called a tree-extension of $S$, if
$S^{\prime}$ is obtained from $S$ by repeatedly attaching leaf-edges. Part (a)
of the following observation is obvious by the leaf-removal process to obtain
the 2-core of ${\mathcal{T}}_{G}$ for a hypergraph $G$. Part (b) follows by
the fact that the number of leaves does not decrease in the process of tree-
extensions.

######  Observation 34.

Let $h\geq 1$ be fixed.

  1. (a)

Suppose $S\in{\mathscr{Y}}^{\delta n}_{h}$ and $\mathcal{T}_{S}$ contains a
cycle. Then $S$ is a tree-extension of $S^{\prime}$, where $S^{\prime}$ is the
hypergraph corresponding to
${\text{c}l}({(\mathcal{T}_{S})_{\text{2-core}}})$.

  2. (b)

Suppose $S\in{\mathscr{Y}}^{\delta n}_{h}$ and $\mathcal{T}_{S}$ contains a
cycle, then ${({\mathcal{T}_{S}})_{\text{2-core}}}$ has excess at most $h$.

If $S\in{\mathscr{Y}}^{\delta n}_{h}$ then
${({\mathcal{T}}_{S})_{\text{2-core}}}$ is a subgraph of ${\mathcal{T}}_{H}$
in which every node (i.e. every vertex-node and every edge-node) has degree at
least two. This motivates the consideration of the following set of subgraphs
of ${\mathcal{T}}_{H}$. Let $h\geq 0$ be fixed. Let
${\mathcal{A}}^{h}(x,y_{2},y_{\geq 3},t)$ denote the set of subgraphs $S$ of
${\mathcal{T}}_{H}$ such that

  * •

$S$ has exactly $x$ vertex-nodes , each of which has degree at least two in
$S$;

  * •

$S$ has exactly $y_{2}$ edge-nodes whose degree in $\mathcal{T}_{H}$ is 2, and
$y_{\geq 3}$ edge-nodes whose degree in $\mathcal{T}_{H}$ is at least three;

  * •

$S$ has total excess $h$;

  * •

$S$ has exactly $t$ edges.

We bound the number of non-pseudo-forest members of ${\mathscr{Y}}^{\delta
n}_{h}$ by bounding the cardinality of ${\mathcal{A}}^{h}(x,y_{2},y_{\geq
3},t)$ and the number of tree-extensions of any member of
${\mathcal{A}}^{h}(x,y_{2},y_{\geq 3},t)$.

######  Lemma 35.

Let $h\geq 0$ be fixed and $\delta>0$ be a sufficiently small real number.

  1. (a)

$\sum_{t\leq\delta n_{1}}\sum_{x,y_{2},y_{\geq
3}}{\mathbb{E}}|{\mathcal{A}}^{h}(x,y_{2},y_{\geq
3},t)|=O((\log^{2h+7}n)n^{h/2}).$

  2. (b)

There exists a sufficiently large constant $K>0$ such that
$\sum{\mathbb{E}}|{\mathcal{A}}^{h}(x,y_{2},y_{\geq 3},t)|=o(1)$, where the
summation is over all $(x,y_{2},y_{\geq 3},t)$ such that $t\leq\delta n_{1}$
and $\max\\{y_{2},y_{\geq 3}\\}\geq K\log^{2}n$.

  3. (c)

For every fixed $K>0$, a.a.s. for every

$S\in\cup_{j=0}^{h}\cup_{\begin{subarray}{c}(x,y_{2},y_{\geq 3},t)\\\ t\leq
K\log^{3}n\end{subarray}}\mathcal{A}^{j}(x,y_{2},y_{\geq 3},t),$

the subgraph of $H$ with Tanner graph ${\text{c}l}(S)$ has $O(\log^{2h+3}n)$
tree extensions, each of which has $h$ vertices with degree one.

Using Lemma 35 we confirm (9) in the following lemma.

######  Lemma 36.

For all sufficiently small $\delta>0$ and every fixed integer $h\geq 1$,
a.a.s. $|{\mathscr{Y}}^{\delta n}_{h}|=O(n^{h/2+o(1)})$.

Proof.  Let $K>0$ be the constant that makes the assertion in Lemma 35(b)
holds. Then, the probability of having $S\in{\mathscr{Y}}^{\delta n}_{h}$ such
that ${({\mathcal{T}}_{S})_{\text{2-core}}}$ has more than $K\log^{2}n$ edge-
nodes of degree two, or more than $K\log^{2}n$ edge-nodes of degree at least
three, is $o(1)$ by Markov’s inequality. Now consider
$S\in{\mathscr{Y}}^{\delta n}_{h}$ such that
${({\mathcal{T}}_{S})_{\text{2-core}}}$ is nonempty and has at most
$2K\log^{2}n$ edge-nodes. By Lemma 28(c), we may assume that
${({\mathcal{T}}_{S})_{\text{2-core}}}$ has $O(K\log^{3}n)=O(\log^{3}n)$
edges. By Lemma 35(a,c), the expected number of such
$S\in{\mathscr{Y}}^{\delta n}_{h}$ is bounded by
$O((\log^{4h+10}n)n^{h/2})=O(n^{h/2+o(1)})$. The assertion now follows by
combining the above two cases and Lemma 31.

###  6.1 Proof of Lemma 16

By Lemma 36 and the argument above (9), a.a.s. there exists constant
$\delta>0$ such that ${\mathcal{E}}$ holds, where ${\mathcal{E}}$ denotes the
event that there is no subgraph $S$ of $H$ such that $S$ has less than $\delta
n$ edges and has exactly at most $r$ vertices of degree equal to 1, all of
which are contained in $[r]$. Suppose event ${\mathcal{E}}$ holds for $H$.
Suppose on the contrary to (8) that there exists nonzero
$\alpha\in\mathbb{F}^{r}$ such that $H_{J}^{\alpha}$ has less than $\delta n$
edges. But $H_{J}^{\alpha}$ must be a subgraph of $H$ such that all vertices
in $V(H_{J}^{\alpha})\setminus J$ have degree at least two, as shown above
(8). In other words, $H_{J}^{\alpha}$ is a subgraph of $H$ with less than
$\delta n$ edges, and all vertices with degree equal to 1 is contained in
$[r]$. This contradicts with the event ${\mathcal{E}}$.

###  6.2 Proof of Lemma 35.

We first prove part (c). Given any

$S\in\cup_{j=0}^{h}\cup_{\begin{subarray}{c}(x,y_{2},y_{\geq 3},t)\\\ t\leq
K\log^{3}n\end{subarray}}\mathcal{A}^{j}(x,y_{2},y_{\geq 3},t),$

there are $O(\log^{3}n)$ edges in $S$, and thus $O(\log^{3}n)$ total vertex-
nodes and edge-nodes in $S$ and ${\text{c}l}(S)$. Immediately, the subgraph
$G$ of $H$ such that ${\mathcal{T}}_{G}={\text{c}l}(S)$ has $O(\log^{3}n)$
vertices. Following the same proof as in Lemma 31, there are $O(\log^{2h}n)$
tree extensions starting from any given vertex in $G$. Thus, the total number
of tree extensions is $O(\log^{2h+3}n)$.

Next, we prove parts (a) and (b). We use the configuration model for the
analysis. Given any $S\in{\mathcal{A}}^{h}(x,y_{2},y_{\geq 3})$, let $y_{j}$
denote the number of edge-nodes in $S$ whose degree in ${\mathcal{T}}_{H}$ is
$j$, for $j\geq 3$. Then immediately $t=\sum_{j\geq 2}jy_{j}-h$. Moreover,
every vertex-nodes in $S$ has degree at least two, and at most $k$. Thus,
necessarily, $2x\leq t\leq kx$. We choose vertex-nodes and edge-nodes for
$S\in{\mathcal{A}}^{h}(x,y_{2},y_{\geq 3},t)$. Let $\beta=\beta_{k}$. By Lemma
28(a), there are at most $(\beta+O(\epsilon_{1}))n_{1}$ edge-nodes in
${\mathcal{T}}_{H}$ with degree two. Thus, there are at most
$\binom{(1+O(\epsilon_{1}))n_{1}}{x}$ ways to choose the vertex-nodes, at most
$\binom{(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}$ ways to choose edge-nodes that
have degree two in ${\mathcal{T}}_{H}$, and at most
$\binom{(1+O(\epsilon_{1}))n_{1}}{y_{\geq 3}}$ ways to choose the edge-nodes
whose degree in ${\mathcal{T}}_{H}$ is at least three. Given the choices of
all vertex-nodes and edge-nodes, there are at most $(\sum_{j\geq
2}jy_{j})^{h}=(t+h)^{h}=O(t^{h})$ ways to choose the $h$ points in the edge-
nodes of $S$ that are not matched to any points in the vertex-nodes of $S$.
Then, there are at most $\binom{k}{2}^{x}\binom{kx-2x}{t-2x}$ ways to choose
$t$ points from the vertex-nodes of $S$ so that every vertex-nodes contain at
least two of the $t$ chosen points. Finally, there are $t!$ ways to match the
$t$ points in the vertex-nodes of $S$ to the $t$ points in the edge-nodes. The
probability of the appearance of every such $t$ pairs of points is

$\prod_{i=0}^{t-1}\dfrac{1}{(kn_{1}-2i-1)}\leq(kn_{1}-2t)^{-t}.$

Hence,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|\leq$
$\displaystyle\binom{(1+O(\epsilon_{1}))n_{1}}{x}\binom{(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\binom{(1+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}O(t^{h})\binom{k}{2}^{x}\binom{kx-2x}{t-2x}$ $\displaystyle\times
t!(kn_{1}-2t)^{-t}.$

Let $M=(1+O(\epsilon_{1}))n_{1}$ and define

$g(x)=\binom{(1+O(\epsilon_{1}))n_{1}}{x}\binom{k}{2}^{x}\binom{kx-2x}{t-2x}.$

Then, for any $1\leq x\leq t/2-1$ where $t\leq\delta n_{1}$,

$\frac{g(x+1)}{g(x)}=\frac{M-x}{x+1}\binom{k}{2}(t-2x)_{2}\frac{((k-2)(x+1))_{t-2x-2}}{((k-2)x)_{t-2x}}\geq\frac{1}{\delta}\left(\frac{t-2x-1}{kx-t+2}\right)^{2}.$

The above ratio is at least one if $t-2x\geq 2k\sqrt{\delta}x$. On the other
hand, $x\leq t/2$ is necessary for ${\mathcal{A}}(x,y_{2},y_{\geq 3},t)$ to be
nonempty. Consequently, $g(x)$ is maximised at some

$x^{*}=(1/2+O(\delta^{1/2}))t,\quad\text{and}\ x^{*}\leq t/2.$

Thus, by choosing sufficiently small $\delta$,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|=$
$\displaystyle
O(t^{h})\binom{(1+O(\epsilon_{1}))n_{1}}{t/2}\binom{(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\binom{(1+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\binom{k}{2}^{t/2}\binom{kx-2x^{*}}{t-2x^{*}}$ $\displaystyle\times
t!(kn_{1}-2t)^{-t}$ $\displaystyle=$ $\displaystyle
O(t^{h})\binom{(1+O(\epsilon_{1}))n_{1}}{t/2}\binom{(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\binom{(1+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\left(\dfrac{k^{2}}{2}\right)^{t/2}$
$\displaystyle\times\binom{kt/2}{O(\delta^{1/2}t)}t!(kn_{1}(1+O(\delta)))^{-t}.$

Using Stirling’s formula, the inequality $\binom{y}{z}\leq(ey/z)^{z}$ and by
setting $(y/0)^{0}=1$ for any real $y$, we obtain

$\displaystyle\binom{(1+O(\epsilon_{1}))n_{1}}{t/2}\leq$
$\displaystyle\left(\dfrac{(2+O(\epsilon_{1}))en_{1}}{t}\right)^{t/2}$
$\displaystyle\binom{(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\leq$
$\displaystyle\left(\dfrac{e(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\right)^{y_{2}}$
$\displaystyle\binom{(1+O(\epsilon_{1}))n_{1}}{y_{\geq 3}}\leq$
$\displaystyle\left(\dfrac{(e+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\right)^{y_{\geq 3}}$ $\displaystyle\binom{kt/2}{O(\delta^{1/2}t)}\leq$
$\displaystyle\exp(O(\delta^{1/2}\log\delta^{-1/2})t)$ $\displaystyle t!=$
$\displaystyle O(t^{1/2})\left(t/e\right)^{t}.$

Hence,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|\leq$
$\displaystyle
O(t^{h+1/2})\left(\exp(O(\delta^{1/2}\log\delta^{-1/2}+\epsilon_{1}))\left(\frac{t}{en_{1}}\right)^{1/2}\right)^{t}\left(\dfrac{e(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\right)^{y_{2}}$
$\displaystyle\times\left(\dfrac{(e+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\right)^{y_{\geq 3}}.$

Therefore, there exists
$K=\exp(O(\delta^{1/2}\log\delta^{-1/2}+\epsilon_{1}))$ such that

${\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|\leq
O(t^{h+1/2})\left(K\left(\frac{t}{en_{1}}\right)^{1/2}\right)^{t}\left(\dfrac{e(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\right)^{y_{2}}\left(\dfrac{(e+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\right)^{y_{\geq 3}}.$ (10)

The derivative of
$\log\left(t^{h+1/2}\left(K\left(\frac{t}{en_{1}}\right)^{1/2}\right)^{t}\right)$
is

$\frac{h+1/2}{t}+\log K+\frac{1}{2}\log(t/en_{1})+\frac{1}{2}<0,$

as $t<\delta n_{1}$ where $\delta$ is sufficiently small. So the right hand
side of (10) is a decreasing function of $t$. Since

$t=\sum_{j\geq 2}jy_{j}-h\geq 2y_{2}+3y_{\geq 3}-h,$

the right hand side of (10) is maximised at $t=2y_{2}+3y_{\geq 3}-h$. Hence,
using $\epsilon_{1}=o(\delta)$ and thus $K=1+O(\delta^{1/4})$,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|=$
$\displaystyle O((y_{2}+y_{\geq
3})^{h+1/2}n_{1}^{h/2})\left(K^{2}\cdot\dfrac{2y_{2}+3y_{\geq
3}}{en_{1}}\cdot\frac{e(\beta+O(\epsilon_{1}))n_{1}}{y_{2}}\right)^{y_{2}}$
$\displaystyle\times\left(K^{3}\left(\dfrac{2y_{2}+3y_{\geq
3}}{en_{1}}\right)^{3/2}\cdot\frac{(e+O(\epsilon_{1}))n_{1}}{y_{\geq
3}}\right)^{y_{\geq 3}}$ $\displaystyle=$ $\displaystyle O((y_{2}+y_{\geq
3})^{h+1/2}n_{1}^{h/2})\left(\dfrac{\beta(2y_{2}+3y_{\geq
3})}{y_{2}(1+O(\delta^{1/4}))}\right)^{y_{2}}\left(\dfrac{(2y_{2}+3y_{\geq
3})^{3/2}}{y_{\geq 3}\sqrt{en_{1}}(1+O(\delta^{1/4}))}\right)^{y_{\geq 3}}.$

Let $0<c<1$ be a constant such that $\beta(2+3c)<0.95$. We consider two cases.

Case 1: $y_{\geq 3}\leq cy_{2}$. By choosing sufficiently small $\delta>0$,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|=O(y_{2}^{h+1/2}n_{1}^{h/2})\cdot
0.96^{y_{2}}\left(\dfrac{C_{1}y_{2}^{3/2}}{y_{\geq
3}\sqrt{n_{1}}}\right)^{y_{\geq 3}}\quad\mbox{for some constant $C_{1}>0$.}$
(11)

Notice that

$\displaystyle\sum_{y_{2}\leq\delta n_{1}}\sum_{y_{\geq
3}<cy_{2}}\sum_{t\leq\delta n_{1}}\sum_{t/k\leq x\leq
t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|={\sum}_{1}+{\sum}_{2},$

where

$\displaystyle{\sum}_{1}$ $\displaystyle=\sum_{0\leq
y_{2}<\log^{2}n_{1}}\sum_{y_{\geq 3}<cy_{2}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|$ $\displaystyle{\sum}_{2}$ $\displaystyle=\sum_{\log^{2}n_{1}\leq
y_{2}\leq\delta n_{1}}\sum_{y_{\geq 3}<cy_{2}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|$

For the first sum above, both $y_{2}$ and $y_{\geq 3}$ are $O(\log^{2}n)$. By
Lemma 28(c), we may assume that $t=O(\log^{3}n)$ as otherwise
${\mathcal{A}}(x,y_{2},y_{\geq 3},t)$ is a.a.s. empty. By (11),

$\displaystyle{\sum}_{1}$ $\displaystyle=O(\log^{6}n_{1})\sum_{0\leq
y_{2}<\log^{2}n_{1}}\sum_{y_{\geq
3}<cy_{2}}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|$
$\displaystyle=O(\log^{2h+7}n_{1})n_{1}^{h/2}\sum_{0\leq
y_{2}<\log^{2}n_{1}}0.96^{y_{2}}\sum_{0\leq y_{\geq
3}<cy_{2}}\left(\dfrac{C_{1}\log^{3}n_{1}}{y_{\geq
3}\sqrt{n_{1}}}\right)^{y_{\geq 3}}$
$\displaystyle=O(\log^{2h+7}n_{1})n_{1}^{h/2}.$

For $\sum_{2}$, note that $t=O(y_{2}\log n_{1})$ and thus $x=O(y_{2}\log
n_{1})$. Thus,

$\displaystyle{\sum}_{2}=$ $\displaystyle
O(n_{1}^{h/2})\sum_{\log^{2}n_{1}\leq y_{2}\leq\delta n_{1}}\sum_{y_{\geq
3}<cy_{2}}y_{2}^{2}\log^{2}n_{1}\cdot y_{2}^{h+1/2}\cdot
0.96^{y_{2}}\left(\dfrac{C_{1}y_{2}^{3/2}}{y_{\geq
3}\sqrt{n_{1}}}\right)^{y_{\geq 3}}.$

The above function is maximised at $y_{\geq
3}=C_{1}y_{2}^{3/2}/e\sqrt{n_{1}}$. So

$\displaystyle{\sum}_{2}=$ $\displaystyle
O(n_{1}^{h/2})n_{1}\cdot\log^{2}n_{1}\sum_{\log^{2}n_{1}\leq y_{2}\leq\delta
n_{1}}y_{2}^{h+5/2}\cdot
0.96^{y_{2}}\exp\left(C_{1}y_{2}^{3/2}/e\sqrt{n_{1}}\right)$ $\displaystyle=$
$\displaystyle O(n_{1}^{h/2})n_{1}\cdot\log^{2}n_{1}\sum_{\log^{2}n_{1}\leq
y_{2}\leq\delta
n_{1}}y_{2}^{h+5/2}\exp\left(y_{2}(\ln(0.96)+(C_{1}/e)\sqrt{y_{2}/n_{1}})\right).$

Since $y_{2}\leq\delta n_{1}$ and by choosing sufficiently small $\delta$,

$\displaystyle{\sum}_{2}=$ $\displaystyle
O(n_{1}^{h/2})n_{1}\cdot\log^{2}n_{1}\sum_{\log^{2}n_{1}\leq y_{2}\leq\delta
n_{1}}y_{2}^{h+5/2}\exp\left(-\Theta(y_{2})\right)=o(1).$ (12)

It follows now that

$\displaystyle\sum_{y_{2}\leq\delta n_{1}}\sum_{y_{\geq
3}<cy_{2}}\sum_{t\leq\delta n_{1}}\sum_{t/k\leq x\leq
t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|=O(\log^{2h+7}n_{1})n_{1}^{h/2}.$ (13)

Case 2: $y_{\geq 3}>cy_{2}$. Note that this immediately implies that $y_{\geq
3}\geq 1$. In this case, for some constants $C_{2},C_{3}>0$,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|$
$\displaystyle=O(y_{\geq 3}^{h+1/2}n_{1}^{h/2})\left(\dfrac{C_{2}y_{\geq
3}}{y_{2}}\right)^{y_{2}}\left(\dfrac{C_{3}y_{\geq
3}^{1/2}}{\sqrt{n_{1}}}\right)^{y_{\geq 3}}.$

Similarly as before, $\left(\dfrac{C_{2}y_{\geq 3}}{y_{2}}\right)^{y_{2}}$ is
maximised at $y_{2}=C_{2}y_{\geq 3}/e$. Thus,

$\displaystyle{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|$
$\displaystyle=O(y_{\geq 3}^{h+1/2}n_{1}^{h/2})\exp\left(\dfrac{C_{2}y_{\geq
3}}{e}\right)\left(\dfrac{C_{3}y_{\geq 3}^{1/2}}{\sqrt{n_{1}}}\right)^{y_{\geq
3}}$ $\displaystyle=O(y_{\geq 3}^{h+1/2}n_{1}^{h/2})\exp\left(y_{\geq
3}\left(\dfrac{C_{2}}{e}+\frac{1}{2}\log(y_{\geq 3}/n_{1})+\log
C_{3}\right)\right).$

Hence, $\sum_{y_{\geq 3}\geq 1}\sum_{y_{2}\leq c^{-1}y_{\geq
3}}\sum_{t\leq\delta n_{1}}\sum_{t/k\leq x\leq
t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq 3},t)|=\Sigma_{3}+\Sigma_{4}$
where

$\displaystyle{\sum}_{3}$ $\displaystyle=$ $\displaystyle\sum_{1\leq y_{\geq
3}\leq\log^{2}n_{1}}\sum_{y_{2}\leq c^{-1}y_{\geq 3}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|$ (14) $\displaystyle=$ $\displaystyle O(n_{1}^{h/2})\sum_{1\leq y_{\geq
3}\leq\log^{2}n_{1}}\sum_{y_{2}\leq c^{-1}y_{\geq 3}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}y_{\geq 3}^{h+1/2}\exp\left(\dfrac{C_{2}y_{\geq
3}}{e}\right)\left(\dfrac{C_{3}y_{\geq 3}^{1/2}}{\sqrt{n_{1}}}\right)^{y_{\geq
3}}$ $\displaystyle=$ $\displaystyle O(n_{1}^{h/2})\log^{8}n_{1}\sum_{1\leq
y_{\geq 3}\leq\log^{2}n_{1}}y_{\geq 3}^{h+1/2}\exp\left(\dfrac{C_{2}y_{\geq
3}}{e}\right)\left(\dfrac{C_{3}y_{\geq 3}^{1/2}}{\sqrt{n_{1}}}\right)^{y_{\geq
3}}$ $\displaystyle=$ $\displaystyle
O(n_{1}^{(h-1)/2}\log^{8}n_{1})=O(n_{1}^{(h-1)/2}\log^{8}n_{1}),$

and

$\displaystyle{\sum}_{4}$ $\displaystyle=$ $\displaystyle\sum_{y_{\geq
3}\geq\log^{2}n_{1}}\sum_{y_{2}\leq c^{-1}y_{\geq 3}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}{\mathbb{E}}|{\mathcal{A}}(x,y_{2},y_{\geq
3},t)|$ (15) $\displaystyle=$ $\displaystyle O(n_{1}^{h/2})\sum_{y_{\geq
3}>\log^{2}n_{1}}\sum_{y_{2}\leq c^{-1}y_{\geq 3}}\sum_{t\leq\delta
n_{1}}\sum_{t/k\leq x\leq t/2}O(y_{\geq 3}^{h+1/2})\exp\left(y_{\geq
3}\left(\dfrac{C_{2}}{e}+\frac{1}{2}\log(y_{\geq 3}/n_{1})+\log
C_{3}\right)\right)$ $\displaystyle=$ $\displaystyle
O(n_{1}^{h/2})n_{1}^{3}\sum_{y_{\geq 3}>\log^{2}n_{1}}O(y_{\geq
3}^{h+1/2})\exp\left(-\Omega(y_{\geq 3})\right)=o(1).$

Now part (a) of the lemma follows by (13) and (14), and part (b) of the lemma
follows by (12) and (15) and by choosing $K=1/c$.

## References

  * [1] Jason Altschuler and Elizabeth Yang.  Inclusion of forbidden minors in random representable matroids.  Discrete Mathematics, 340(7):1553–1563, 2017.
  * [2] Peter Ayre, Amin Coja-Oghlan, Pu Gao, and Noëla Müller.  The satisfiability threshold for random linear equations.  Combinatorica, 40(2):179–235, 2020.
  * [3] Nikhil Bansal, Rudi A Pendavingh, and Jorn G van der Pol.  On the number of matroids.  Combinatorica, 35:253–277, 2015.
  * [4] Béla Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  European Journal of Combinatorics, 1(4):311–316, 1980.
  * [5] Julie Cain and Nicholas Wormald.  Encores on cores.  the electronic journal of combinatorics, pages R81–R81, 2006.
  * [6] Amin Coja-Oghlan, Alperen A Ergür, Pu Gao, Samuel Hetterich, and Maurice Rolvien.  The rank of sparse random matrices.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 579–591. SIAM, 2020.
  * [7] Colin Cooper, Alan Frieze, and Wesley Pegden.  Minors of a random binary matroid.  Random Structures & Algorithms, 55(4):865–880, 2019.
  * [8] Paul Erdős and Rényi.  On random graphs i.  Publ. math. debrecen, 6(290-297):18, 1959.
  * [9] Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. math. inst. hung. acad. sci, 5(1):17–60, 1960.
  * [10] Jim Geelen and Kasper Kabell.  Projective geometries in dense matroids.  Journal of Combinatorial Theory, Series B, 99(1):1–8, 2009.
  * [11] Jim Geelen, Joseph PS Kung, and Geoff Whittle.  Growth rates of minor-closed classes of matroids.  Journal of Combinatorial Theory, Series B, 99(2):420–427, 2009\.
  * [12] Douglas G Kelly and James G Oxley.  Asymptotic properties of random subsets of projective spaces.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 91, pages 119–130. Cambridge University Press, 1982.
  * [13] Douglas G Kelly and James G Oxley.  Threshold functions for some properties of random subsets of projective spaces.  The Quarterly Journal of Mathematics, 33(4):463–469, 1982.
  * [14] Douglas G Kelly and JG Oxley.  On random representable matroids.  Studies in Applied Mathematics, 71(3):181–205, 1984.
  * [15] Donald E Knuth.  The asymptotic number of geometries.  Journal of Combinatorial Theory, Series A, 16(3):398–400, 1974\.
  * [16] Wojciech Kordecki.  Strictly balanced submatroids in random subsets of projective geometries.  In Colloquium Mathematicum, volume 2, pages 371–375, 1988.
  * [17] Wojciech Kordecki.  Small submatroids in random matroids.  Combinatorics, Probability and Computing, 5(3):257–266, 1996.
  * [18] Wojciech Kordecki and Tomasz Łuczak.  On random subsets of projective spaces.  In Colloquium Mathematicae, volume 62, pages 353–356, 1991.
  * [19] Wojciech Kordecki and Tomasz Łuczak.  On the connectivity of random subsets of projective spaces.  Discrete mathematics, 196(1-3):207–217, 1999.
  * [20] Lisa Lowrance, James Oxley, Charles Semple, and Dominic Welsh.  On properties of almost all matroids.  Advances in Applied Mathematics, 50(1):115–124, 2013.
  * [21] Tomasz Łuczak, Boris Pittel, and John C Wierman.  The structure of a random graph at the point of the phase transition.  Transactions of the American Mathematical Society, 341(2):721–748, 1994.
  * [22] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle.  On the asymptotic proportion of connected matroids.  European Journal of Combinatorics, 32(6):882–890, 2011.
  * [23] Peter Nelson.  Almost all matroids are non-representable.  arXiv preprint arXiv:1605.04288, 2016.
  * [24] James G Oxley.  Matroid theory, volume 3.  Oxford University Press, USA, 2006.
  * [25] Rudi Pendavingh and Jorn Van Der Pol.  On the number of bases of almost all matroids.  Combinatorica, 38:955–985, 2018.