Almost every sparse paving matroid contains $M(K_4)$ or $W^3$ as a minor

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 complete-graphic matroid M(K4).

The matroid $M(K_4)$.

The whirl W3 has six points and three dependent hyperplanes.

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$

Online talk: Yelena Yuditsky

Mon, August 10, 3pm ET (8pm BST, 7am Tue NZST)
Yelena Yuditsky, Ben-Gurion University
Typical structure of hereditary graph families
Zoom [email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]

Abstract:
A family of graphs $\cal F$ is hereditary if it is closed under isomorphism and taking induced subgraphs. For example, for a given graph $H$, a hereditary family is the family of all $H$-free graphs, that is graphs without an induced copy of $H$.

Alon, Balogh, Bollobás and Morris showed that for every hereditary family $\cal F$ there exist $\epsilon >0$ and $l\in \mathbb{N}$ such that the number of graphs in $\cal F$ on $n$ vertices is $2^{(1-1/l)n^2/2+o(n^{2-\epsilon})}$. They showed this bound by deriving various structural properties of almost all graphs in $\cal F$. We study and obtain additional structural properties of almost all graphs in some restricted hereditary families. As an application of our results, we prove the existence of an infinite family of counterexamples for the recent Reed-Scott conjecture about the structure of almost all $H$-free graphs.

This is a joint work with Segey Norin.

Online talk: Jim Geelen

Mon, August 3, 3pm ET (8pm BST, 7am Tue NZST)
Jim Geelen, University of Waterloo
Towards the excluded-minors for GF(5)-representability
Zoom [email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]

Abstract:
I will discuss a strategy towards finding the excluded-minors for GF(5)-representability of matroids. This includes some joint work with Rutger Campbell and Geoff Whittle.

Online talk: Zach Walsh

Mon, July 27, 3pm ET (8pm BST, 7am Tue NZST)
Zach Walsh, University of Waterloo
Quadratically Dense Matroids
Zoom [email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]

Abstract:
The extremal function of a class of matroids is the function whose value at an integer $n$ is the maximum number of elements of a simple matroid in the class of rank at most $n$. We present a result concerning the role of group-labeled graphs in minor-closed classes of matroids, and then use it to determine the extremal function, for all but finitely many $n$, for the class of complex-representable matroids which exclude a given rank-2 uniform matroid as a minor. This talk will focus on our original motivation, and on the connection between group-labeled graphs and representable matroids.

This is joint work with Jim Geelen and Peter Nelson.