Binomial Random Matroids

Abstract

Let $\mathcal{B}={\mathcal{B}}_{k,n,p}$ be a random collection of $k$-subsets of $[n]$ where each possible set is present independently with probability $p$. Let ${\mathcal{E}}_{\mathcal{B}}$ be the event that $\mathcal{B}$ defines the set of bases of a matroid. We prove that If $p=1-\frac{c_n}{(k(n-k)(\genfrac{}{}{0ex}{}{n}{k}){)}^{1/2}}$ where $0\le c_n\le \infty$, then \[ \lim_{n\to\infty}\Pr[\cal E_{\cal B}\mid |\cal B|\geq2]=\begin{cases}1&c_n\to0.\\e^{-c^2/2}&c_n\to c.\\0&c_n\to \infty.\end{cases}\] In addition, we identify a condition preventing the occurence of ${\mathcal{E}}_{\mathcal{B}}$ and prove a hitting time version for the occurence of $\mathcal{B}$. We also prove that when ${\mathcal{E}}_{\mathcal{B}}$ occurs, $\mathcal{B}$ defines a sparse paving matroid w.h.p. In addition, study a greedy algorithm that produces a random matroid defined by a collection of hyperplanes. We use this to improve the estimates in \cite{HPV} on $\log m(n,k),\log p(n,k),\log s(n,k)$ where $m(n,k),p(n,k),s(n,k)$ denote the number of matroids, paving matroids, and sparse paving matroids (respectively) of rank $k$ on $[n]$. Our improvement lies in that we can deal with $k$ growing slowly with $n$ as opposed to $k=O(1)$ in \cite{HPV}. More generally, we obtain estimates for the number of matchings in nearly-regular hypergraphs with small codegree, which may be of independent interest.