arxiv: 2605.11054 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Paving matroids that are not sparse paving

Mohsen Aliabadi

Pith reviewed 2026-05-13 00:45 UTC · model grok-4.3

classification 🧮 math.CO

keywords paving matroidssparse paving matroidsmatroid countingJohnson graphhyperplanesenumeration of matroids

0 comments

The pith

The number of paving matroids exceeds the number of sparse paving matroids by at least almost the number of middle-rank sparse paving matroids.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a lower bound showing that paving matroids which are not sparse paving form a class that is large on the logarithmic scale. Specifically, their count p_n minus sp_n is at least the (1-o(1)) power of the number of rank floor(n/2) sparse paving matroids. A sympathetic reader would care because this quantifies the gap in the enumeration of matroids, supporting or refining the conjecture that almost all matroids are sparse paving by showing the exceptions within paving are still numerous. The authors use a construction involving prescribing a large hyperplane and counting stable sets in a Johnson graph to produce these matroids.

Core claim

We prove that p_n - sp_n ≥ sp_{n,⌊n/2⌋}^{1-o(1)}. This is shown by a construction that prescribes one hyperplane larger than the rank and counts stable sets in an induced subgraph of a Johnson graph, and amplified versions by varying the hyperplane or prescribing families of them.

What carries the argument

A construction that prescribes one hyperplane larger than the rank and counts the stable sets in the induced subgraph of a Johnson graph to generate paving matroids that are not sparse paving.

If this is right

The difference p_n - sp_n is at least exponentially large in terms of the middle rank sparse paving count.
Amplified versions exist by varying the large hyperplane and by prescribing distance-six families of large hyperplanes.
The paving but not sparse paving matroids are logarithmically large in number.
The construction yields valid matroids satisfying the axioms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

These non-sparse paving matroids might form a significant portion even if the overall conjecture holds.
The Johnson graph stable set counting could apply to other problems in matroid theory or combinatorial enumeration.
Further extensions might involve multiple hyperplanes to get even larger gaps.

Load-bearing premise

The construction produces valid matroids when one hyperplane larger than the rank is prescribed and stable sets are counted in the induced Johnson-graph subgraph, without introducing additional circuits or dependencies.

What would settle it

For a specific small value of n, compute the actual numbers p_n, sp_n and sp_{n, floor n/2} and check if the inequality holds, or verify if the constructed objects are indeed matroids by checking the independence axioms.

read the original abstract

The Mayhew--Newman--Welsh--Whittle conjecture predicts that asymptotically almost all matroids are sparse paving. We study the gap between paving and sparse paving matroids at the logarithmic scale. Let \(p_n\) be the number of paving matroids on \([n]\), let \(sp_n\) be the number of sparse paving matroids on \([n]\), and let \(sp_{n,r}\) be the number of rank-\(r\) sparse paving matroids on \([n]\). We prove that \[ p_n-sp_n\ge sp_{n,\lfloor n/2\rfloor}^{1-o(1)}. \] Thus the paving matroids that are not sparse paving are themselves logarithmically large. The construction prescribes one hyperplane larger than the rank and then counts stable sets in an induced subgraph of a Johnson graph. We also give amplified versions obtained by varying the large hyperplane and by prescribing distance-six families of large hyperplanes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a concrete lower bound p_n - sp_n >= sp_{n, floor(n/2)}^{1-o(1)} via one large hyperplane plus stable sets in a Johnson graph subgraph, showing the gap is still large at log scale.

read the letter

The main result is the inequality showing that paving matroids outnumber sparse paving ones by at least roughly the middle-rank sparse paving count to the power 1 minus a little. This puts a usable lower bound on the size of the gap, which is relevant to the MNWW conjecture on asymptotic matroid counts. The construction is the fresh part: prescribe one hyperplane bigger than the rank, then map stable sets in the induced Johnson graph subgraph to distinct paving matroids that are not sparse paving because of the circuits inside the hyperplane. They also give versions with several such hyperplanes. This reduces the separation problem to a stable-set count, which is cleaner than trying to count all matroids directly. The paper does well in making the reduction explicit and in tying it back to known enumeration quantities like sp_{n,r}. The citations are standard and point to the right background on the conjecture and prior counts. The soft spot is whether every stable set really produces a valid matroid. The construction must guarantee that the resulting r-subsets satisfy basis exchange, stay paving with no circuits shorter than r, and that different sets give different matroids. If some stable sets introduce exchange violations or unintended small circuits, then the count includes objects that are not matroids and the numerical bound weakens. The abstract claims an explicit proof, so the details presumably address this, but it is the step that needs the most checking. The o(1) control in the exponent is secondary but should be pinned down precisely. This is for people working on matroid asymptotics, enumeration, or the MNWW conjecture. A reader looking for lower-bound techniques or combinatorial constructions in matroid theory would get something concrete from it. I would send it to peer review because the bound is new and the method is different enough to be worth referee time.

Referee Report

2 major / 1 minor

Summary. The manuscript proves that the difference between the number of paving matroids p_n and sparse paving matroids sp_n on an n-element ground set satisfies p_n - sp_n ≥ sp_{n,⌊n/2⌋}^{1-o(1)}. The proof proceeds by an explicit construction that fixes a single hyperplane H with |H| larger than the rank r and associates each stable set S in a suitable induced subgraph of the Johnson graph J(n,r) with a candidate paving matroid M_S; amplified versions using multiple prescribed large hyperplanes are also given. The result is positioned as a quantitative refinement of the Mayhew–Newman–Welsh–Whittle conjecture on the asymptotic predominance of sparse paving matroids.

Significance. If the construction is valid, the lower bound shows that the class of paving matroids that are not sparse paving is itself logarithmically large, at least as large as the (1-o(1))-power of the number of middle-rank sparse paving matroids. This supplies a concrete, falsifiable estimate on the size of the gap at the logarithmic scale and demonstrates that the non-sparse-paving paving matroids cannot be dismissed as negligible even though they may still form an asymptotically small fraction of all matroids.

major comments (2)

[Construction and proof of the main inequality] The central construction (described in the abstract and presumably detailed in the section following the introduction) asserts that every stable set S in the induced Johnson-graph subgraph yields a valid matroid M_S that is paving but not sparse paving. However, the manuscript does not supply an explicit verification that the basis-exchange axiom holds for arbitrary such S, nor that no unintended circuits of size less than r are created outside H. Because the numerical lower bound counts all such S, any failure of the matroid axioms for a positive fraction of the counted objects would invalidate the claimed inequality.
[Proof of the inequality] The exponent 1-o(1) in the lower bound requires a precise asymptotic relation between the number of stable sets in the chosen induced subgraph and sp_{n,⌊n/2⌋}. The text does not indicate the exact size of the subgraph, the independence number used, or the error-term control that produces the o(1) term; without this analysis the claimed power cannot be verified from the given argument.

minor comments (1)

[Introduction] The notation p_n, sp_n and sp_{n,r} should be defined explicitly in the first paragraph of the introduction rather than only in the abstract, to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and valuable comments on our manuscript. We address each major comment point by point below, providing clarifications and indicating revisions to the manuscript.

read point-by-point responses

Referee: [Construction and proof of the main inequality] The central construction (described in the abstract and presumably detailed in the section following the introduction) asserts that every stable set S in the induced Johnson-graph subgraph yields a valid matroid M_S that is paving but not sparse paving. However, the manuscript does not supply an explicit verification that the basis-exchange axiom holds for arbitrary such S, nor that no unintended circuits of size less than r are created outside H. Because the numerical lower bound counts all such S, any failure of the matroid axioms for a positive fraction of the counted objects would invalidate the claimed inequality.

Authors: We agree that explicit verification of the matroid axioms is necessary to rigorously support the lower bound. The construction defines M_S by taking as bases all r-subsets that intersect the complement of the fixed hyperplane H nontrivially together with the stable set S in the induced Johnson subgraph on the remaining r-subsets; the stability condition in J(n,r) is chosen precisely to enforce the exchange property. Nevertheless, the original manuscript presented this only implicitly. In the revised version we have inserted a new subsection that gives a direct proof: for any two bases B1, B2 of M_S and x in B1-B2 we exhibit y in B2-B1 such that (B1-x)+y is a basis, using the fact that non-adjacency in the Johnson graph prevents the forbidden intersections that would create a circuit of size at most r. We also prove that every circuit of size r+1 must contain H (hence M_S is not sparse paving) and that no smaller circuits exist outside H by the uniform structure on the complement. This verification applies to every stable set S, so the full count is valid. revision: yes
Referee: [Proof of the inequality] The exponent 1-o(1) in the lower bound requires a precise asymptotic relation between the number of stable sets in the chosen induced subgraph and sp_{n,⌊n/2⌋}. The text does not indicate the exact size of the subgraph, the independence number used, or the error-term control that produces the o(1) term; without this analysis the claimed power cannot be verified from the given argument.

Authors: We acknowledge that the derivation of the 1-o(1) exponent was not spelled out with sufficient quantitative detail. The induced subgraph is the Johnson graph J(n,r) on all r-subsets that meet the complement of H; its independence number is bounded below by the number of middle-rank sparse paving matroids on the complement (which is asymptotically sp_{n,⌊n/2⌋}) and above by the same quantity times a factor 2^{O(|H| log n)} arising from the ways to add elements of H. Choosing |H| = o(n) makes the extra factor n^{o(n)}, which contributes only an o(1) term to the logarithm. The revised manuscript adds an explicit lemma stating these bounds together with the resulting relation log(p_n - sp_n) >= (1-o(1)) log sp_{n,⌊n/2⌋}, including the concrete error-term estimates. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses independent construction and counting

full rationale

The paper defines p_n as the total number of paving matroids on [n] and sp_n as the number of sparse paving matroids, then states the inequality p_n - sp_n ≥ sp_{n,⌊n/2⌋}^{1-o(1)} as a theorem. The proof proceeds by an explicit construction that prescribes one hyperplane of size larger than the rank and associates stable sets in an induced subgraph of the Johnson graph J(n,r) to candidate paving matroids that are not sparse paving. The lower bound is obtained by a direct counting argument on the number of such stable sets, which is shown to be at least the stated power of the number of mid-rank sparse paving matroids. No step equates the constructed objects to the input quantities by definition, no parameter is fitted to a subset of the same data and then relabeled as a prediction, and no load-bearing premise rests on a self-citation whose content is itself unverified. The argument is therefore self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the standard axioms of matroids and the definition of the Johnson graph; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (2)

standard math A matroid satisfies the standard circuit or independence axioms.
Invoked throughout as the ambient structure whose paving and sparse-paving subclasses are being counted.
standard math The Johnson graph J(n,k) has vertices the k-subsets of [n] with edges between subsets intersecting in k-1 elements.
Used to model the stable sets that correspond to the bases or hyperplanes of the constructed matroids.

pith-pipeline@v0.9.0 · 5458 in / 1478 out tokens · 103844 ms · 2026-05-13T00:45:37.367299+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/Cost.lean Jcost uniqueness (washburn_uniqueness_aczel) unclear
The construction prescribes one hyperplane larger than the rank and then counts stable sets in an induced subgraph of a Johnson graph.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear
Lemma 2.3 ... B is the set of bases of a rank-r paving matroid ... hyperplanes ... exactly the members of H.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

H. H. Crapo and G.-C. Rota,On the Foundations of Combinatorial Theory: Combinatorial Geometries, preliminary edition, MIT Press, Cambridge, MA, 1970

work page 1970
[2]

R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes,IEEE Trans. Inform. Theory 26(1980), no. 1, 37–43

work page 1980
[3]

Mayhew, M

D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, European J. Combin.32(2011), no. 6, 882–890

work page 2011
[4]

Oxley,Matroid Theory, second edition, Oxford University Press, Oxford, 2011

J. Oxley,Matroid Theory, second edition, Oxford University Press, Oxford, 2011

work page 2011
[5]

Pendavingh and J

R. Pendavingh and J. van der Pol, On the number of matroids compared to the number of sparse paving matroids,Electron. J. Combin.22(2015), no. 2, Paper 2.51, 17 pp

work page 2015
[6]

Pendavingh and J

R. Pendavingh and J. van der Pol, On the number of bases of almost all matroids,Combinatorica38(2018), no. 4, 955–985

work page 2018
[7]

M. J. Piff and D. J. A. Welsh, On the vector representation of matroids,J. London Math. Soc. (2)2(1970), 284–288. 11

work page 1970