Joint inclusion bounds for random greedy matroid bases
Loading original first page…
Abstract
Assign independent priorities from one common atomless law to the elements of a finite matroid and construct its minimum-weight basis greedily. We bound every joint inclusion probability in terms of the corresponding individual marginals, with a factorial coefficient and an explicit marginal-dependent improvement. The pair case gives a universal factor two, improving the previously stated factor eight for random minimum spanning trees. The proof first conditions on all unmarked priorities. Forcing a marked element into the basis and contracting it yields a conditional cylinder inequality; conditional Jensen and Hölder inequalities then return to the original one-element closure thresholds. Bernoulli sprinkling bounds these thresholds in convex order by a beta distribution with the same mean. We obtain a sharp moment hierarchy, characterize equality by rank-one direct summands, and derive exclusion and occupancy bounds. Finite-cylinder limits transfer the estimates to countable finitary-matroid restriction limits and to both free and wired minimal spanning forests. On transitive unimodular graphs this gives a uniform exponential bound for the wired-forest degree distribution.
Read the full paper in the original PDF.
Edition files
- Joint_inclusion_bounds_for_random_greedy_matroid_bases.pdf104.2 KiB · pdf
SHA-256
44dea1b28ca31d6c36af640fffd24717c1f167e3fdb65a01968ede1d014f8e28 - Joint_inclusion_bounds_for_random_greedy_matroid_bases_-_Publication_package.zip114.7 KiB · package
SHA-256
fa12d3a29b2dc474ad3cf6e6630d6efd5bdaf91edc501d6077cde64304d47326
Available editions
- Edition 1 · 2026-10-29 · public
Research details
- Subjects
- Mathematics · Combinatorics and Graph Theory · Probability and Statistics
- Keywords
- matroid, random greedy basis, minimum spanning forest, joint inclusion, convex order
- Manuscript date
- 2026-10-29
- Reader reuse
- none
Scope
Joint inclusion and exclusion bounds for random greedy bases under independent priorities from one common atomless law, threshold convex order and equality, occupancy estimates, and finite-cylinder returns to minimal spanning forests.
Disclosures
OpenAI ChatGPT/Codex assisted with literature discovery, mathematical exploration and proof development, manuscript drafting, verification-code development and internal critical checking. The author assumes responsibility for all content. Scott Schubr owns Luminary Oddities, which operates the Research Archive hosting this preprint. This work received no specific grant from any funding agency, commercial or not-for-profit sector.
Reproduction
The PDF contains the complete mathematical argument. The accompanying package includes editable LaTeX source, build_pdf.py, reader instructions, citation metadata and a SHA-256 member manifest.
References and related resources
- A. Gupta, Pairwise edge correlations in random minimum spanning trees: a universal bound and complete-graph negative correlation (2026). · references
- D. Mayhew, Equitable matroids (2006). · references
- J. Huh, B. Schröter and B. Wang, Correlation bounds for fields and matroids (2022). · references
- R. Lyons, Y. Peres and O. Schramm, Minimal spanning forests (2006). · references
- L. Makowiec, Fixed forests in the minimum spanning tree and cubic volume growth (2026). · references