Binomial Random Matroids
This provides theoretical insights into random matroid structures and improves combinatorial bounds, with incremental advances in handling non-constant ranks.
The paper tackles the problem of determining when a random collection of k-subsets forms a matroid, proving a threshold probability result and showing it typically yields sparse paving matroids, and improves estimates on the number of matroids, paving matroids, and sparse paving matroids for ranks growing slowly with n.
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 $\cal 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)\binom nk)^{1/2}}$ where $0\leq c_n\leq \infty$, then \[ \lim_{n\to\infty}\Pr[\cal E_{\cal B}\mid |\cal B|\geq2]=\begin{cases}1&c_n\to0.\\e^{-c^2}&c_n\to c.\\0&c_n\to \infty.\end{cases}\] In addition, we identify a condition preventing the occurence of $\cal E_{\cal B}$ and prove a hitting time version for the occurence of $\cal B$. We also prove that when $\cal 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.