Binomial Random Matroids
Pith reviewed 2026-05-15 14:08 UTC · model grok-4.3
The pith
A binomial random collection of k-subsets forms the bases of a matroid with limiting probability 1, e^{-c^2/2} or 0 as c_n tends to 0, a constant or infinity.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Let B be the random collection of k-subsets of [n] in which each k-set appears independently with probability p. Let E_B be the event that B is exactly the collection of bases of a matroid on [n]. If p = 1 - c_n / sqrt(k(n-k) binom(n,k)) with 0 <= c_n <= infinity, then the limit of Pr[E_B | |B| >= 2] equals 1 when c_n -> 0, equals e^{-c^2/2} when c_n -> c, and equals 0 when c_n -> infinity. Whenever E_B occurs, the resulting matroid is sparse paving with high probability.
What carries the argument
The binomial random collection B_{k,n,p} together with the event E_B that it satisfies the matroid basis axioms, whose probability is controlled by bounding the occurrence of forbidden configurations inside the stated scaling window.
If this is right
- When c_n tends to zero, almost every collection with at least two sets is the base set of a matroid.
- Any matroid produced in the window is sparse paving with high probability.
- A greedy hyperplane algorithm yields improved logarithmic asymptotics for the number of matroids, paving matroids and sparse paving matroids when k grows slowly with n.
- The same estimates apply to the number of matchings in nearly-regular hypergraphs of small codegree.
- There exists an explicit hitting time at which the random collection first becomes the base set of a matroid.
Where Pith is reading between the lines
- Most matroids that arise in this binomial model are sparse paving, so the typical random matroid has a comparatively simple circuit structure.
- The same threshold analysis may extend to other axiom systems defined by local forbidden configurations in set systems.
- The hypergraph matching estimates could be used to count other classes of combinatorial objects whose defining properties reduce to small-codegree matchings.
Load-bearing premise
Different k-subsets are included independently so that the probability of any forbidden configuration can be estimated directly from the given scaling of p.
What would settle it
For fixed k and large n, generate many independent samples at the critical value of p and measure whether the empirical fraction of collections that form matroids lies within sampling error of the predicted value e^{-c^2/2}.
read the original 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 $\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/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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies binomial random collections of k-subsets of an n-set, where each k-subset is included independently with probability p. It establishes a threshold phenomenon for the event that such a collection forms the bases of a matroid: when p = 1 - c_n / sqrt(k(n-k) binom(n,k)) with c_n tending to a constant c, the probability that the collection is the bases of a matroid, conditioned on having at least two bases, tends to e^{-c^2/2}. It further shows that the resulting matroid is sparse-paving with high probability, provides a hitting-time version, and uses a greedy algorithm on hyperplanes to obtain improved logarithmic estimates for the number of matroids, paving matroids, and sparse-paving matroids on n elements of rank k, for k growing slowly with n. The approach also yields estimates for the number of matchings in nearly regular hypergraphs with small codegrees.
Significance. If correct, the threshold result is a notable contribution to the study of random matroids, providing a precise limiting probability rather than just existence of a threshold. The extension of counting results to growing k improves upon previous work restricted to fixed k, and the hypergraph matching estimates may find independent use in combinatorial enumeration. The identification of sparse-paving as the typical outcome adds structural insight.
major comments (1)
- [Theorem 1.1 and §3] The proof of the limiting distribution (Theorem 1.1 and the argument in §3): the claim that Pr[E_B | |B|≥2] converges to e^{-c^2/2} for bounded c relies on the number of basis-exchange violations behaving as a Poisson random variable with mean c^2/2. The second-moment calculation must explicitly show that covariances between indicators of pairs of potential violations (which share 1 or 2 elements) contribute o(1) to the variance uniformly for c_n = O(1); without a separate estimate of these joint probabilities (beyond marginals), the Stein-Chen or second-moment method does not yet establish the limit.
minor comments (2)
- [Abstract] Abstract: 'occurence' is misspelled and should read 'occurrence'.
- [Introduction] The statement of the main threshold result should explicitly recall the definition of the event E_B immediately before the displayed limit, to avoid any ambiguity in the conditioning.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We address the single major comment below and will revise the paper accordingly to strengthen the proof.
read point-by-point responses
-
Referee: [Theorem 1.1 and §3] The proof of the limiting distribution (Theorem 1.1 and the argument in §3): the claim that Pr[E_B | |B|≥2] converges to e^{-c^2/2} for bounded c relies on the number of basis-exchange violations behaving as a Poisson random variable with mean c^2/2. The second-moment calculation must explicitly show that covariances between indicators of pairs of potential violations (which share 1 or 2 elements) contribute o(1) to the variance uniformly for c_n = O(1); without a separate estimate of these joint probabilities (beyond marginals), the Stein-Chen or second-moment method does not yet establish the limit.
Authors: We agree that the second-moment argument requires an explicit uniform bound on the covariances to rigorously establish the Poisson limit. In the revised version we will insert a new lemma (placed in §3 immediately before the application of the second-moment method) that computes the joint probability for any two distinct potential basis-exchange violations. The lemma will show that when the two violations share one or two ground-set elements the covariance is at most O(1/(k(n-k) binom(n,k))) uniformly for c_n = O(1); the total contribution of all such pairs to the variance is therefore o(1). With this estimate the second-moment method yields Var(X) = E[X] + o(1) where X counts the violations, which together with the already-established first-moment calculation implies convergence in distribution to Poisson(c^2/2) and hence the claimed limit e^{-c^2/2}. We thank the referee for highlighting this gap in the exposition. revision: yes
Circularity Check
No circularity: independent probabilistic derivation of threshold limit from binomial model
full rationale
The central result parameterizes p directly via c_n and derives the limiting conditional probability of E_B from the independent-inclusion model using standard probabilistic tools (second-moment or Stein-Chen methods on forbidden configurations). No parameter is fitted to the target distribution and then relabeled as a prediction. The citation to HPV appears only in the secondary counting application and is not invoked to justify the main limit theorem or to forbid alternative models. The derivation therefore remains self-contained against the stated random-matroid axioms and does not reduce to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The k-subsets are included independently with probability p.
- standard math A collection of k-subsets forms the bases of a matroid precisely when it satisfies the matroid basis axioms.
Reference graph
Works this paper leans on
-
[1]
P. Bennett and T. Bohman. A natural barrier in random greedy hypergraph matching.Combin. Probab. Comput., 28(6):816–825, 2019
work page 2019
-
[2]
P. Bennett and A. Dudek. A gentle introduction to the differential equation method and dynamic concentration.Discrete Math., 345(12):Paper No. 113071, 17, 2022
work page 2022
-
[3]
S. Chakravarty and N. Spanier. The linearq-hypergraph process.Electron. J. Combin., 32(1):Paper No. 1.17, 18, 2025
work page 2025
-
[4]
T. M. Cover and J. A. Thomas.Elements of information theory. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, second edition, 2006
work page 2006
-
[5]
J. Cutler and A. J. Radcliffe. An entropy proof of the Kahn-Lov´ asz theorem.Electron. J. Combin., 18(1):Paper 10, 9, 2011
work page 2011
-
[6]
M. Kwan, A. Sah, and M. Sawhney. Enumerating matroids and linear spaces.C. R. Math. Acad. Sci. Paris, 361:565–575, 2023. 14
work page 2023
-
[7]
N. Linial and Z. Luria. An upper bound on the number of Steiner triple systems.Random Structures Algorithms, 43(4):399–406, 2013
work page 2013
- [8]
-
[9]
Oxley.Matroid theory, volume 21 ofOxford Graduate Texts in Mathematics
J. Oxley.Matroid theory, volume 21 ofOxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011
work page 2011
-
[10]
R. Pendavingh and J. van der Pol. Enumerating matroids of fixed rank.Electron. J. Combin., 24(1):Paper No. 1.8, 28, 2017
work page 2017
-
[11]
J. Radhakrishnan. An entropy proof of Bregman’s theorem.J. Combin. Theory Ser. A, 77(1):161–164, 1997
work page 1997
-
[12]
R. van der Hofstad, R. Pendavingh, and J. van der Pol. The number of partial Steiner systems and d-partitions.Adv. Comb., pages Paper No. 2, 23, 2022
work page 2022
-
[13]
D. J. A. Welsh. Combinatorial problems in matroid theory. InCombinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pages 291–306. Academic Press, London-New York, 1971. 15
work page 1969
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.