Girth conditions and Rota's basis conjecture

Benjamin Friedman; Sean McGuinness

REVIEW 3 major objections 5 minor 15 references

Girth conditions and Rota's basis conjecture

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read High-girth, low-overlap matroids admit n-o(n) disjoint rainbow bases, bringing Rota's basis conjecture within o(n) of full strength.

desk verdict The disjoint case is a solid extension of Geelen–Humphries, but the overlapping case as written does not go through: Lemma 4.2 is omitted, (A) misapplies Lemma 4.3, and reference [14] likely supersedes the main asymptotic claim. read the letter →

arxiv 1908.01216 v2 pith:KFCLJGKW submitted 2019-08-03 math.CO

Benjamin Friedman , Sean McGuinness This is my paper · ORCID

classification math.CO MSC 05B3505D99

keywords Rota'sbasisconjecturematroidrainbowbasesgirthoverlappingbasesequencesrootcascadesdisjointindependentsetsasymptoticdecomposition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Rota's basis conjecture says that n given bases of a rank-n matroid can be repacked into n disjoint rainbow bases. This paper proves the conjecture in an asymptotic sense under two quantitative hypotheses: the matroid has girth at least n-o(√n), meaning every circuit is almost as large as the rank, and the n given bases are κ-overlapping with κ=o(√n), meaning no element of the ground set occurs in more than o(√n) bases. Under these hypotheses, at least n-o(n) disjoint rainbow bases exist. The value is that the obstruction to the full conjecture, whatever it is, becomes a vanishing fraction of the rank in this high-girth, low-overlap regime.

What carries the argument

The load-bearing objects are roots and cascades. A root is (S,S,b), where S is a collection of disjoint rainbow independent sets, S is one member, and b is a colour absent from S; elements of S are swappable if they can be exchanged for an unused element of colour b, and addable if they can enter S with at most such an exchange. A root cascade is a chain of roots in which a cascadable element from the next set triggers a swap and shifts the missing colour along the chain; Observation 2.3 says that in a maximal collection every intermediate set in the cascade must be a rainbow base. The signature τ(S)=(τ_1,...,τ_n) counting sets by size, ordered lexicographically from largest downward, is the maximality device that makes the contradiction: an improvement in signature is impossible, so a shortage of rainbow bases must instead produce many cascadable elements concentrated in one set. For overlapping bases, the new operation transforms a bad root into a good root through a graph whose vertices are coloured elements and whose levels grow by a factor α/κ; a good root is one with an unused colour-b element outside the ground set of S, which restores the lower bound on swappable elements. Lemma 4.2, stated without proof, is the assertion that this good-root cascade finds k cascadable elements under the same parameter conditions as the disjoint lemma.

What would settle it

Exhibit a matroid of rank n with girth at least n-o(√n) and a κ-overlapping base sequence, κ=o(√n), for which the maximum number of disjoint rainbow bases is strictly below n-(2κ(n)+2β(n)+1)^2-β(n)-2; equivalently, give a concrete instance where the conclusion of Lemma 4.2 fails while its hypotheses hold, since Theorem 1.3 is derived from that lemma.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.3: for a rank-n matroid M with girth g ≥ n-β(n)+1 and a κ-overlapping base sequence B, provided n > 2((2κ(n)+2β(n)+1)^2+β(n)), the largest set of disjoint rainbow bases satisfies t(B) ≥ n - (2κ(n)+2β(n)+1)^2 - β(n) - 2. When both β(n) and κ(n) are o(√n), this is t(B) ≥ n - o(n). The proof works at the level of collections of disjoint rainbow independent sets ordered by their signature, counting how many sets of each size they contain. Any collection that is maximal in this order cannot be improved, so the assumption that rainbow bases are missing forces a root cascade containing many cascadable elements; girth then supplies enough swappable elements to contradict maximality. In the overlapping case the paper inserts a repair step, the good root, which uses a colour-exchange graph to find an unused element outside the ground set of the chosen set, restoring the girth-based count.

Load-bearing premise

In the overlapping case, everything depends on Lemma 4.2, which asserts that when a κ-overlapping sequence has fewer rainbow bases than the target, some maximal or submaximal collection contains a good-root cascade with at least k cascadable elements; the paper states that its proof is the same as the disjoint Lemma 2.6 and omits it, so the step from disjoint to overlapping is not independently verified.

Editorial extensions

If this is right

If Theorem 1.3 is correct, Rota's basis conjecture holds asymptotically for every rank-n matroid with girth n-o(√n) and overlap o(√n): the number of disjoint rainbow bases is n-o(n).
The error term is explicit: t(B) ≥ n - (2κ(n)+2β(n)+1)^2 - β(n) - 2, so any improvement in the overlap or girth slack shrinks the missing bases quadratically.
The good-root repair step means that even when some bases overlap heavily, a bad root can be replaced by a good one as long as the overlap κ is below the slack α, so the obstruction to improving a collection is confined to sets whose elements are reused many times.
In the disjoint case, Theorem 1.2 gives the concrete bound t(B) ≥ n - 4β(n)^2 - 7β(n) - 4 whenever n ≥ 4β^2+7β+5, showing the same method works without the overlap repair.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next question, suggested by the quadratic dependence on (2κ+2β+1)^2, is whether the o(n) loss can be upgraded to O(√n) or removed entirely; the current theorem likely reflects the method's cost rather than a true obstruction.
The good-root level-expansion argument appears transferable to other rainbow decomposition problems in which each ground-set element is assigned to a bounded number of colour classes, since the only matroid input used is that recolouring preserves independence.
A testable small case is rank n=5 or 6 with β and κ chosen near the boundary of the theorem: exhaustive computation of t(B) would show whether the constant (2κ+2β+1)^2 is tight or merely an artifact of the proof.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is that the disjoint case (Theorem 1.2) is a solid extension of Geelen–Humphries, and the good-root cascade idea is a real attempt to get n-o(n) for overlapping bases. The overlapping case as written, however, does not go through: the proof of (A) misapplies Lemma 4.3, and Lemma 4.2 is asserted without proof. On top of that, [14] likely supersedes the main asymptotic claim.

What the paper does well: the cascade framework from Bucić et al. is adapted carefully to the girth setting. Theorem 1.2's proof is coherent: Lemma 2.6 supplies a large cascadable set in the disjoint case, and the counting in Section 3 is plausible. The explicit bounds are nice, and the paper is honest enough to cite [14] in the introduction, even if it does not fully discuss the overlap.

The soft spots are real. Lemma 4.2 is the only bridge between the disjoint and overlapping cases; the text says the proof is 'essentially the same' and omits it. But the good-root operation changes colour data, and the disjointness of B is used in the averaging argument of Lemma 2.6. That is a nontrivial adaptation. Then in the proof of (A), Lemma 4.3 gives a lower bound on |S∩S'| in terms of the number of good-cascadable elements in S, but the proof feeds in q_S=|R∩S|, the number of addable elements from the R_i. Those are not the same set, and the lemma's hypothesis is not satisfied. The summation also quietly drops |R∩S'| before using the lower bound on |R|. These are not cosmetic; the displayed inequality q(n−β−q²) < κn+2β(n−α) does not follow.

The novelty overlap is worth flagging too. If [14] indeed proves n-o(n) disjoint rainbow bases unconditionally, then Theorem 1.3 is a corollary. The paper's description of [14] as giving large rainbow independent sets looks like an understatement. Even if the technique is independent, the main theorem loses its news value.

Who is this for? Specialists in matroid theory and the RBC literature. The disjoint case is worth reading; the overlapping case is not established by the text. I would send it to a serious referee because the topic is important and the gap in (A) is identifiable and potentially fixable—but I would not cite it in its current form.

Referee Report

3 major / 5 minor

Summary. The paper studies lower bounds on the number t(B) of disjoint rainbow bases in a rank-n matroid, under the assumptions of large girth and bounded overlap of the base sequence. Theorem 1.2 gives t(B) ≥ n - 4β(n)^2 - 7β(n) - 4 for disjoint base sequences when the girth is at least n - β(n) + 1. Theorem 1.3 claims the asymptotically optimal t(B) ≥ n - (2κ+2β+1)^2 - β - 2 = n - o(n) when the girth is n - β(n) + 1 with β,κ = o(√n) and the base sequence is κ-overlapping. The proof adapts the cascade machinery of Bucić et al., introducing 'good roots' and 'good root cascades' to handle overlapping bases. Section 2 develops root cascades and proves a concentration lemma (Lemma 2.6) in the disjoint case. Section 3 proves Theorem 1.2. Section 4 introduces the good-root transformation and states Lemma 4.2, whose proof is omitted, and then proves Theorem 1.3 via a contradiction argument (parts (A), (B), (C)).

Significance. If the results were correct, Theorem 1.3 would be a substantial advance for Rota's basis conjecture, showing that a near-complete set of disjoint rainbow bases exists for matroids of near-maximal girth and sublinear overlap, and would significantly extend the Geelen--Humphries paving-matroid result. The cascade idea is well chosen, and the disjoint-case proof (Section 3) is a coherent, quantitative improvement in its own right. The paper is carefully structured and makes falsifiable, explicit bounds. However, the central overlapping-case result rests on two substantial unproven or misapplied steps, so the main advertised theorem is not established as written.

major comments (3)

[Section 4.2, Lemma 4.2] Lemma 4.2 is the only bridge from the disjoint case to the κ-overlapping case, yet its proof is omitted with the remark that it is 'essentially the same' as Lemma 2.6. This is not a routine adaptation. The good-root transformation of Section 4.1 changes the colour data of the collection (while preserving ground sets), so the collection S in Lemma 4.2 is not necessarily the same kind of collection as in Lemma 2.6, and the disjointness of B is used in the proof of Lemma 2.6 in the averaging step and in the invocation of Lemma 2.4, whose proof is also left to the reader. Since part (B) of the proof of Theorem 1.3 relies on Lemma 4.2 to produce the collection with q good-cascadable elements, Theorem 1.3 is not established without a full proof of this lemma.
[Section 4.3, part (A)] The proof of part (A) misapplies Lemma 4.3. Lemma 4.3 states that if |CASCgood(S0,...,Sk−1) ∩ S| = q for a single set S that is the terminal set of a cascade, then for every other set S′ one has |S ∩ S′| ≥ q − 2β. In part (A), however, the proof feeds in q_S = |R ∩ S|, where R is the union of addable elements from q different good-root cascades (one for each (x_i,c_i)). The hypotheses of Lemma 4.3 are not satisfied for this q_S, so the inequality |S ∩ S′| ≥ q_S − 2β does not follow. The subsequent chain leading to q(n − β − q^2) < κn + 2β(n − α) is therefore unsupported.
[Section 4.3, part (A), display near (A)] Even if Lemma 4.3 were applicable, the displayed chain contains an additional unjustified step: the passage from the lower bound on ∑ |R ∩ S′| over S′ in S − {S0,...,Sk} to the lower bound on ∑ q_S after removing one additional set S′ drops the term |R ∩ S′| without accounting for it in the inequality. The displayed inequality '≥ q(n − β − q^2) − 2β(n − α − q)' is obtained as if the removed set contributed nothing, and the paper does not explain why the removed set has empty intersection with R or why its contribution can be ignored. Together with the misapplication of Lemma 4.3, this makes part (A) invalid as written.

minor comments (5)

[Section 1, definition of κ-overlapping] The phrase 'κκκ-overlapping' appears in the introduction in a way that suggests a typographical artifact; it should read 'κ-overlapping'.
[Section 2.2, Lemma 2.2] Lemma 2.2 is stated without proof or reference. If it is a standard matroid exchange lemma, a proof or citation would help the reader; if it is new, it needs a proof.
[Section 2.3, proof of Observation 2.3] The proof of Observation 2.3 writes expressions like τn(S_i) where S_i is a set, but the signature τ is defined for collections. The intended meaning is presumably the signature of the collection obtained by a replacement operation; please clarify.
[Section 4.1, Lemma 4.1] The proof of Lemma 4.1 would be clearer if it explicitly separated the count of coloured elements in the union ∪UN_c(S) from the count of distinct ground elements, which is where the κ-overlapping condition is used.
[Section 4.3, proof of Lemma 4.3] In the proof of Lemma 4.3, the notation S' is used both for a set in the collection and for a modified collection; this makes the construction of T hard to follow. Please disambiguate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the proof is self-contained, with unproved lemmas and proof gaps but no reduction of conclusions to inputs.

full rationale

I found no circularity in the claimed derivation. Theorems 1.2 and 1.3 are matroid-theoretic arguments built from the stated girth hypothesis, the kappa-overlap condition, and cascade lemmas adapted from the external work of Bucic, Kwan, Pokrovskiy, and Sudakov. No parameter is fitted to the target quantity, and the lower bound on t(B) is not inserted as an input. The principal concern in the paper is Lemma 4.2, whose proof is omitted with the statement that it is essentially the same as Lemma 2.6, together with Lemma 2.4 whose proof is also left to the reader. These are missing proofs or verification gaps, not circular reductions: an unproved lemma is an assumption in the argument, but it is not a case of defining or fitting X in terms of Y. Similarly, the apparent mismatch in part (A), where Lemma 4.3 is applied to quantities q_S = |R intersect S| that are not shown to be CASCgood counts, is a potential correctness gap rather than circularity. The only self-citation in the paper, reference [7], is a contextual survey of Alon-Tarsi results and is not load-bearing for the main theorem. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof relies on standard matroid exchange and on the cascade framework of [2]. No numerical parameters are fitted to data, and no new mathematical entities are postulated. The main unproven load-bearing steps are the omitted proofs of Lemma 2.4 and Lemma 4.2, plus the misapplication of Lemma 4.3 discussed in red flags.

assumptions (3)

standard math Strong basis exchange: for any two bases S and B_c, there exists an injection φ_c: S → B_c such that S - x + φ_c(x) is a base for each x ∈ S.
Invoked in Lemma 2.2 and throughout Sections 3 and 4; standard result in matroid theory.
domain assumption g(M) ≥ n - β(n) + 1.
Explicit hypothesis of Theorems 1.2 and 1.3.
domain assumption No ground element belongs to more than κ(n) bases of B.
Explicit hypothesis of Theorem 1.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Girth conditions and Rota's basis conjecture." pith.science (2026). https://pith.science/paper/KFCLJGKW

@misc{pith2026190801216,
  author       = {Pith},
  title        = {Pith review of: Girth conditions and Rota's basis conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KFCLJGKW}},
  note         = {Machine review of arXiv:1908.01216}
}

abstract

Rota's basis conjecture (RBC) states that given a collection $\mathcal{B}$ of $n$ bases in a matroid $M$ of rank $n$, one can always find $n$ disjoint rainbow bases with respect to $\mathcal{B}$. In this paper, we show that if $M$ has girth at least $n-o(\sqrt{n})$, and no element of $M$ belongs to more than $o(\sqrt{n})$ bases in $\mathcal{B}$, then one can find at least $n - o(n)$ disjoint rainbow bases with respect to $\mathcal{B}$. This result can be seen as an extension of the work of Geelen and Humphries, who proved RBC in the case where $M$ is paving, and $\mathcal{B}$ is a pairwise disjoint collection. We make extensive use of the cascade idea introduced by Buci\'c et al.

Figures

Figures reproduced from arXiv: 1908.01216 by the authors.

**Figure 2.** This sequence of operations, known as a good root casca [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[14]

Pokrovskiy

A. Pokrovskiy. Rota’s basis conjecture holds asymptotically. arXiv:2008.06045v1, 2020

arXiv 2008
[1]

Alon and M

N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125–134, 1992

work page 1992
[2]

Buci´ c, M

M. Buci´ c, M. Kwan, A. Pokrovskiy, and B. Sudakov. Halfway to Rota’s Basis Conjecture. International Mathematics Research Notices , 02 2020. rnaa004

work page 2020
[3]

W. Chan. An exchange property of matroid. Discrete Math., 146(1-3):299–302, 1995

work page 1995
[4]

M. Cheung. Computational proof of Rota’s basis conjecture fo r matroids of rank 4. educ.jmu.edu/~duceyje/undergrad/2012/mike.pdf, 2012. unpublished

work page 2012
[5]

Dong and J

S. Dong and J. Geelen. Improved Bounds for Rota’s Basis Conjec ture. Combinatorica, 39(2):265–272, 2019

work page 2019
[6]

A. A. Drisko. On the number of even and odd Latin squares of ord er p + 1. Adv. Math., 128(1):20–35, 1997

work page 1997
[7]

Friedman and S

B. Friedman and S. McGuinness. The Alon-Tarsi conjecture: a p erspective on the main results. Discrete Math., 342(8):2234–2253, 2019

work page 2019

Show all 15 references

[8]

Geelen and P

J. Geelen and P. J. Humphries. Rota’s basis conjecture for pavin g matroids. SIAM J. Discrete Math. , 20(4):1042–1045, 2006

2006
[9]

Geelen and K

J. Geelen and K. Webb. On Rota’s basis conjecture. SIAM J. Discrete Math. , 21(3):802–804, 2007

2007
[10]

D. G. Glynn. The conjectures of Alon-Tarsi and Rota in dimensio n prime minus one. SIAM J. Discrete Math., 24(2):394–399, 2010

2010
[11]

Huang and G.-C

R. Huang and G.-C. Rota. On the relations of various conjectur es on Latin squares and straightening coeﬃcients. Discrete Math., 128(1-3):225–236, 1994

1994
[12]

S. Onn. A colorful determinantal identity, a conjecture of Ro ta, and Latin squares. Amer. Math. Monthly, 104(2):156–159, 1997

1997
[13]

J. Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics . Oxford University Press, Oxford, second edition, 2011. 13

2011
[15]

M. Wild. On Rota’s problem about n bases in a rank n matroid. Adv. Math. , 108(2):336–345, 1994. 14

1994

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [14]

Pokrovskiy

A. Pokrovskiy. Rota’s basis conjecture holds asymptotically. arXiv:2008.06045v1, 2020

arXiv 2008

[2] [1]

Alon and M

N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125–134, 1992

work page 1992

[3] [2]

Buci´ c, M

M. Buci´ c, M. Kwan, A. Pokrovskiy, and B. Sudakov. Halfway to Rota’s Basis Conjecture. International Mathematics Research Notices , 02 2020. rnaa004

work page 2020

[4] [3]

W. Chan. An exchange property of matroid. Discrete Math., 146(1-3):299–302, 1995

work page 1995

[5] [4]

M. Cheung. Computational proof of Rota’s basis conjecture fo r matroids of rank 4. educ.jmu.edu/~duceyje/undergrad/2012/mike.pdf, 2012. unpublished

work page 2012

[6] [5]

Dong and J

S. Dong and J. Geelen. Improved Bounds for Rota’s Basis Conjec ture. Combinatorica, 39(2):265–272, 2019

work page 2019

[7] [6]

A. A. Drisko. On the number of even and odd Latin squares of ord er p + 1. Adv. Math., 128(1):20–35, 1997

work page 1997

[8] [7]

Friedman and S

B. Friedman and S. McGuinness. The Alon-Tarsi conjecture: a p erspective on the main results. Discrete Math., 342(8):2234–2253, 2019

work page 2019