Inclusion of Forbidden Minors in Random Representable Matroids

Abstract

In 1984, Kelly and Oxley introduced the model of a random representable matroid $M[A_n]$ corresponding to a random matrix $A_n\in {\mathbb{F}}_q^{m(n)\times n}$, whose entries are drawn independently and uniformly from ${\mathbb{F}}_q$. Whereas properties such as rank, connectivity, and circuit size have been well-studied, forbidden minors have not yet been analyzed. Here, we investigate the asymptotic probability as $n\to \infty$ that a fixed ${\mathbb{F}}_q$-representable matroid $M$ is a minor of $M[A_n]$. (We always assume $m(n)\ge \text{rank}(M)$ for all sufficiently large $n$, otherwise $M$ can never be a minor of the corresponding $M[A_n]$.) When $M$ is free, we show that $M$ is asymptotically almost surely (a.a.s.) a minor of $M[A_n]$. When $M$ is not free, we show a phase transition: $M$ is a.a.s. a minor if $n-m(n)\to \infty$, but is a.a.s. not if $m(n)-n\to \infty$. In the more general settings of $m\le n$ and $m>n$, we give lower and upper bounds, respectively, on both the asymptotic and non-asymptotic probability that $M$ is a minor of $M[A_n]$. The tools we develop to analyze matroid operations and minors of random matroids may be of independent interest. Our results directly imply that $M[A_n]$ is a.a.s. not contained in any proper, minor-closed class $\mathcal{M}$ of ${\mathbb{F}}_q$-representable matroids, provided: (i) $n-m(n)\to \infty$, and (ii) $m(n)$ is at least the minimum rank of any ${\mathbb{F}}_q$-representable forbidden minor of $\mathcal{M}$, for all sufficiently large $n$. As an application, this shows that graphic matroids are a vanishing subset of linear matroids, in a sense made precise in the paper. Our results provide an approach for applying the rich theory around matroid minors to the less-studied field of random matroids.

to appear in Discrete Mathematics