Two conjectures and a theorem

One conjecture that I quite like is the following, due to Mayhew, Newman, Welsh, and Whittle.

Conjecture 1. Let $N$ be a sparse paving matroid. Almost every matroid has an $N$-minor.

We say that almost every matroid has an $N$-minor when the fraction of matroids on ground set $\{1,2,\ldots,n\}$ that does not have an $N$-minor tends to 0 as $n$ tends to infinity. A sparse paving matroid is a matroid in which every dependent hyperplane is a circuit; equivalently, every $r(M)$-set is either a basis or a circuit-hyperplane. Such matroids are combinatorially more benign than general matroids, although it has been conjectured that almost every matroid is sparse paving.

The conjecture is known to hold in only a few special cases: when $N$ is a uniform matroid and when $N$ is a matroid of rank 3 on 6 elements with at most two dependent hyperplanes. The two smallest cases that remain open are $N=M(K_4)$ and $N=W^3$.

The matroid $M(K_4)$.

The matroid $W^3$.

The conjecture remains hard even when we restrict our attention to sparse paving matroids.

Conjecture 2. Let $N$ be a sparse paving matroid. Almost every sparse paving matroid has an $N$-minor.

Conjecture 2 holds for all the cases for which we know that Conjecture 1 holds. A few additional cases, including $N = W^3$, are proved by Critchlow in his PhD thesis. Here, I want to give a quick proof that almost every sparse paving matroid contains an $M(K_4)$- or $W^3$-minor.

Theorem. Almost every sparse paving matroid has an $M(K_4)$- or $W^3$-minor.

It may be much harder to prove the corresponding claim for general matroids.

Reduction to rank 3

A few years ago, Rudi Pendavingh and I wrote about using entropy to bound the number of matroids in minor-closed classes. The main technical result in that post is the following, which allows one to translate a bound on the number of matroids of rank $s$ to a bound on the number of matroids of rank $r$.

Matroid Entropy Lemma. If $\mathcal{M}$ is a class of matroid that is closed under isomorphism and contraction, then for all $s \le r$ $$\log\left(m_{\mathcal{M}}(n,r)+1\right)/\binom{n}{r} \le \log\left(m_{\mathcal{M}}(n-r+s,s) + 1\right)/\binom{n-r+s}{s}.$$

Here we write $m_{\mathcal{M}}(n,r)$ for the number of matroids in $\mathcal{M}$ on ground set $\{1,2,\ldots,n\}$ that have rank $r$.

The Matroid Entropy Lemma (used with $s=2$) is sufficiently strong to prove a near-optimal upper bound on the number of matroids. Moreover, when the lemma is used with $s=3$, it can be used that almost every matroid contains a $U_{2,k}$- or $U_{3,6}$-minor.

As Rudi and I described in our blog post, the Matroid Entropy Lemma is useful for problems of enumeration, since it reduces general counting problems to counting problems in fixed rank. In particular, when we use $s=3$, counting problems reduce to counting problems involving points and lines. Specialising the lemma to the case of excluding rank-3 sparse paving matroids, we obtain the following general result.

Lemma 1. Let $\mathcal{X}$ be a set of sparse paving matroids of rank 3, and let $s_{\mathcal{X}}(n)$ be the number of sparse paving matroids of rank 3 on ground set $\{1,2,…,n\}$ that do not have any minor contained in $\mathcal{X}$. If there exists a constant $c < 1/2$ such that $\log s_{\mathcal{X}}(n) \le \frac{c}{n}\binom{n}{3}$ for all sufficiently large $n$, then almost every sparse paving matroid has an element of $\mathcal{X}$ as a minor.

Sparse paving matroids of rank 3 are extremely friendly objects. Their dependent hyperplanes (or long lines) form the edges of linear 3-uniform hypergraph, or equivalently the blocks of a partial Steiner triple system.

Unfortunately, when $\mathcal{X} = \{M(K_4)\}$, Lemma 1 is of no use to us.

In design theory literature, $M(K_4)$ is known as the Pasch configuration or quadrilateral, and it is well known that there exist “anti-Pasch” or “quadrilateral-free” Steiner triple systems whenever $n = 1,3 \mod 6$ and $n \ge 15$. As a full Steiner triple system contains $n(n-1)/6$ blocks, the Lemma does not apply.

When $\mathcal{X} = \{W^3\}$, Lemma 1 requires us to bound the number of 3-uniform linear hypergraphs without $W^3$ as an induced subgraph, which may be an interesting class to study.

The Ruzsa–Szemerédi problem

Something interesting happens when $\mathcal{X} = \{W^3, M(K_4)\}$. Lemma 1 now requires us to bound the number of 3-uniform linear hypergraphs that do not contain $W^3$ are a subgraph. Equivalently, the union of any three edges of such a hypergraph contains at least seven vertices. Let us call such a hypergraph a Ruzsa–Szemerédi hypergraph.

The Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in such a hypergraph. Let us write $\text{rs}(n)$ for this number; Rusza and Szemerédi showed that $\text{rs}(n) = o(n^2)$ using the Szemerédi Regularity Lemma.

We now show that this implies that we can use Lemma 1 to prove the Theorem.

Lemma 2. Let $\mathcal{X} = \{W^3, M(K_4)\}$. Then $s_{\mathcal{X}}(n) = 2^{o(n^2)}$.

Proof. Let $H$ be a Ruzsa–Szemerédi hypergraph on $n$ vertices. Let $G(H)$ be the graph on the same vertex set, whose edges correspond to pairs of elements that are contained in an edge of $H$. Such a graph has the property that every edge is in a unique triangle, which means that $H$ can be reconstructed from $G(H)$. As $G(H)$ has at most $3\text{rs}(n)$ edges, it follows that the number of Ruzsa–Szemerédi hypergraphs on $n$ vertices is at most $\binom{\binom{n}{2}}{\le 3\text{rs}(n)}$. A standard bound on binomial coefficients tells us that this is at most $2^{h\left(\text{rs}(n)/\binom{n}{2}\right)\binom{n}{2}}$, where $h$ is the binary entropy function. The lemma now follows from the fact that $\text{rs}(n) = o(n^2)$ and $h(\varepsilon)\downarrow 0$ as $\varepsilon \downarrow 0$. $\Box$