REVIEW 4 minor 6 references
The smallest matroids with no large independent flat
T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For a simple rank-$r$ matroid with no $(t+1)$-element independent flat, the minimum number of elements is exactly the size of $M_{r,t}$, the direct sum of $t$ balanced binary projective geometries, and this minimizer is unique when $r \ge…
desk verdict Solid extremal matroid paper: the lower bound is clean, the equality characterization is intricate but checks out, and the graph analogue is a nice bonus. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing objects are claws and the matroid $M_{r,t}$. A claw is a set that is simultaneously a flat and independent; forbidding a $(t+1)$-claw is a matroid analogue of forbidding an induced forest. $M_{r,t}$ is the direct sum of $t$ binary projective geometries, meaning the point sets of finite projective spaces over $\mathbb{F}_2$, with ranks as balanced as possible. The proof of the lower bound is driven by the recurrence $f(r,t)=2f(r-t,t)+t$: contract a $t$-claw $S$, note that every parallel class of $M/S$ has size at least two, and apply induction. The equality proof is carried by Lemma 3.2, which forces a loopless matroid with no $(t+1)$-claw and exactly $2r-t$ elements to be a direct sum of $r-t$ circuits and coloops; applied to $3t$-element closures of the form $\operatorname{cl}_M(S\cup U)$, this lemma forces each such closure to split into $t$ triangles, and a bijection $\psi$ from the contracted elements to $S$ then reassembles the whole matroid as a balanced direct sum of projective geometries.
What would settle it
Find a simple rank-$r$ matroid with no $(t+1)$-claw and fewer than $|M_{r,t}|$ elements, or, for $r\ge 2t$, an equality example not isomorphic to $M_{r,t}$; a finite exhaustive search over simple matroids on a small ground set, for instance rank $6$ with $t=2$ searching for a $13$-element counterexample, would settle the first case. Alternatively, construct a loopless rank-$r$ matroid with no $(t+1)$-claw, exactly $2r-t$ elements, whose simplification contains a rank-$3$ flat that is not a circuit; this would disprove Lemma 3.2 and break the equality proof.
Extended reading notes
Core claim
The central discovery is a sharp extremal theorem. For integers $r,t \ge 1$, write $f(r,t)=|M_{r,t}|$, where $M_{r,t}$ is a direct sum of $t$ binary projective geometries of ranks $\lfloor r/t\rfloor$ or $\lceil r/t\rceil$; equivalently $f(r,t)=(t-a)2^{\lfloor r/t\rfloor}+a2^{\lceil r/t\rceil}-t$ with $a \equiv r \pmod t$. Theorem 1.1 asserts that every simple rank-$r$ matroid with no $(t+1)$-claw has at least $f(r,t)$ elements, and that equality with $r\ge 2t$ forces $M\cong M_{r,t}$. When $t<r<2t$, equality also allows direct sums of coloops together with $r-t$ circuits that are not all triangles. Along the way the paper proves a loopless analogue: a loopless rank-$r$ matroid with no $(t+1)$-claw has at least $2r-t$ elements, with equality exactly for a direct sum of $r-t$ circuits and coloops. It also states a graph version in which every $n$-vertex graph with no induced forest on $2t+1$ vertices has at least $|E(G_{n,t})|$ edges, with tight examples classified by Theorem 4.1.
Load-bearing premise
The uniqueness proof depends on the strict inequality $|X|<2r(M^*)$ in Lemma 3.2, which forces a minimal loopless example to decompose as a direct sum of circuits and coloops; if that inequality could be an equality, the step that splits closures into triangles would fail and the equality characterization would not follow.
Editorial extensions
If this is right
- The exact extremal number for simple rank-$r$ matroids with no $(t+1)$-claw is $f(r,t)$, so the minimum size grows roughly like $t\,2^{r/t}$.
- For $r\ge 2t$, $M_{r,t}$ is the unique minimizer, so any other simple rank-$r$ matroid with no $(t+1)$-claw has strictly more elements.
- The loopless version has the much smaller bound $2r-t$, and equality forces a direct sum of $r-t$ circuits and coloops; this shows the simplicity condition in the main theorem is essential.
- The graph analogue is an extremal statement for graphs: every $n$-vertex graph with no induced forest on $2t+1$ vertices has at least $|E(G_{n,t})|$ edges, with tight examples classified for all $n$.
- The paper proves the $t=1$ case of Conjecture 1.3: a simple rank-$r$ triangle-free matroid with no $3$-claw has at least $2^{r-1}$ elements, with equality exactly for the binary affine geometry $\operatorname{AG}(r-1,2)$.
Reading between the lines
- The paper does not fully classify the circuits appearing in the $t<r<2t$ equality cases; enumerating them would complete the portrait of tight examples.
- One could adapt the contraction argument to forbid claws of a different size $k$, obtaining a family of recursively defined extremal functions, of which the paper's recurrence is the first member.
- If Conjecture 1.3 is true, binary affine geometries are the triangle-free analogues of the projective geometries here; testing $t=2$ by computer search would give evidence before a general proof is attempted.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper determines the minimum number of elements in a simple rank-r matroid with no (t+1)-claw, where a claw is an independent flat. The extremal matroid is shown to be the direct sum of t binary projective geometries with ranks differing by at most 1, and for r ≥ 2t this is the unique extremal matroid. The proof combines a contraction-based induction for the lower bound with a detailed equality analysis built around Lemma 3.2, a structural result for loopless matroids. The paper also proves a graph-theoretic analogue (Theorem 1.2) concerning induced forests, and proves the t=1 case of a conjecture about triangle-free matroids.
Significance. If correct, Theorem 1.1 is a clean and striking result: the extremal matroid for the binary case remains extremal in the class of all matroids. The lower-bound proof is elegant, and the equality characterization is strong and nontrivial. Lemma 3.2's dual-counting argument is subtle but sound. The graph-theoretic theorem is a nice Turán-type result for induced forests, and Conjecture 1.3 provides a clear direction for future work. The paper addresses a natural extremal question and gives a complete answer, with credit due for the careful induction and the explicit equality analysis.
minor comments (4)
- [Section 1] The sentence claiming that 'the direct sum of r−t parallel pairs and t coloops has 2r−t elements and is the unique smallest loopless rank-r matroid with no (t+1)-claw' is not correct as a uniqueness statement. Lemma 3.2 permits equality for any direct sum of r−t circuits and some number of coloops; for example, when r=3 and t=1, the direct sum of a 3-circuit and a 2-circuit also has 5 elements and no 2-claw, and it is not isomorphic to the stated matroid. Please rephrase this to indicate that the stated matroid is one extremal example, while Lemma 3.2 gives the full equality structure.
- [Lemma 3.1] The inference 'since r ≥ 3 this gives that M has no U_{2,4}-minor so is binary' is terse. The general principle 'all single-element contractions are binary implies binary' is false (U_{2,4} is a counterexample). The proof actually relies on the earlier-established fact that every line has size exactly 3, so no U_{2,4}-restriction can occur. A short clarification would prevent confusion.
- [Theorem 3.3, step 3.3.4] The conclusion 'and therefore that is precisely the direct sum of t triangles' would benefit from an explicit justification: since M' is a restriction of a simple matroid, each circuit in the decomposition has size at least 3, and the equality of sizes forces each to be a triangle and rules out the presence of coloops.
- [Section 1] There is a typo in the introduction: 'ex cluding' should be 'excluding'.
Circularity Check
No circularity: the extremal bound and uniqueness theorem are proved from external benchmarks and internal lemmas, with the self-citation [3] used only as motivation.
full rationale
The paper's central claim, Theorem 1.1, is not an input in disguise. The lower bound in Theorem 2.2 is derived from Lemma 2.1 and the recursive definition of f(r,t), which is computed from the explicit construction M_{r,t}; no parameter is fitted to the data being predicted. The equality characterization is built on Lemma 3.1 (using Tutte's external characterization of binary matroids) and Lemma 3.2, whose dual-counting proof establishes the strict inequality |X| < 2r(M*) independently and then upgrades the loopless bound to the direct-sum structure at equality. Steps 3.3.1-3.3.7 apply these lemmas to force the triangle decomposition and the projective-geometry components; the final rank-balancing argument is an internal exchange computation. The cited prior work [3] supplies only the t=2 binary conjecture and motivation, not a premise: the proof never invokes [3] as justification for a step. External benchmarks (Tutte's characterization, the Bose-Burton affine-geometry uniqueness result, and Turan's theorem for the graph analogue) are used as genuine independent support. Thus no circularity or fitted-input-as-prediction pattern is present.
Assumptions & free parameters
assumptions (4)
- standard math Tutte's characterization: a matroid is binary if and only if it has no U_{2,4}-minor.
- standard math Bose-Burton characterization: a simple rank-r binary matroid with 2^(r-1) elements and no triangles is isomorphic to AG(r-1,2).
- standard math Turan's theorem: a graph on n vertices with no stable set of size t+1 has at least |E(G_{n,t})| edges.
- standard math Standard matroid theory: definition of flats, claws, contractions, simplifications, direct sums, projective and affine geometries, and the fact that a rank-n projective geometry has 2^n - 1 elements.
Cite this review
Pith. "Pith review of The smallest matroids with no large independent flat." pith.science (2026). https://pith.science/paper/K4YNMLDM
@misc{pith2026190902045,
author = {Pith},
title = {Pith review of: The smallest matroids with no large independent flat},
year = {2026},
howpublished = {\url{https://pith.science/paper/K4YNMLDM}},
note = {Machine review of arXiv:1909.02045}
}
abstract
We show that a simple rank-$r$ matroid with no $(t+1)$-element independent flat has at least as many elements as the matroid $M_{r,t}$ defined as the direct sum of $t$ binary projective geometries whose ranks pairwise differ by at most $1$. We also show for $r \ge 2t$ that $M_{r,t}$ is the unique example for which equality holds.
Reference graph
Works this paper leans on
-
[3]
The structure of claw-free binary matroids
P. Nelson, K. Nomoto, The structure of claw-free binary matro ids. arXiv:1807.11543
-
[1]
R. C. Bose, R. C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and the MacDonald codes, J. Combin. Theory 1 (1966), 96–104
work page 1966
-
[2]
The structure of binary matroids with no induced claw or Fano plane restriction
M. Bonamy, F. Kardoˇ s, T. Kelly, P. Nelson, L. Postle, The struc - ture of binary matroids with no induced claw or Fano plane re- striction. arXiv:1806.04188
-
[4]
J. G. Oxley, Matroid Theory, Oxford University Press, New York (2011)
work page 2011
-
[5]
P. Tur´ an, On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok(1941) (in Hungarian), 436—452
work page 1941
-
[6]
Tutte, Lectures on matroids, Journal of Research of the National Bureau of Standards (1965), 1—47
W.T. Tutte, Lectures on matroids, Journal of Research of the National Bureau of Standards (1965), 1—47
work page 1965
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.