REVIEW 2 major objections 4 minor 2 cited by
A note on finding large transversals efficiently
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This note proves that every n×n array where no symbol appears more than βn times contains a transversal of size (1 − β/4 − o(1))n, and describes a deterministic polynomial-time algorithm that finds one.
desk verdict Real advance with a new deterministic method; proof has a repairable counting gap in Claim 2.2. 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 engine is an iterative construction of pairs (I(ω), S(I(ω))) for each newly added symbol ω: I(ω) is a small set of row/column indices and S(I(ω)) is a permutation on the submatrix A_{I(ω)}. The construction maintains four properties (A1)–(A4) that ensure Extend(S(I(ω))) contains all diagonal symbols plus an extra copy of ω. A pair of indices {i,j} 'inserts' a symbol ω when the diagonal symbols at i and j are already in the collection and the four sets R(i), R(j), R(I(A_{i,i})), R(I(A_{j,j})) are pairwise disjoint, where R(x) is the set of diagonal positions sharing x's symbol unless that set is large. The key counting lemma, Claim 2.2, bounds the number of 'useless' pairs per index via the bound (2.2), which limits how many index sets R(I(ω)) can contain a fixed row index; combining this with the density deficit on the diagonal yields the per-round growth |Ω_t| ≥ εβn/12. This bound on useless pairs is what makes the greedy maximal collection large enough to force termination within O(τ) rounds.
What would settle it
Run the deterministic algorithm on a large equi-n square (say n = $10^{4}$) and check the size of the transversal it outputs; a transversal of size well below (3/4 − ε)n for many instances would disprove the theorem, as would a direct verification that the bound (2.2) fails for t = 1 by more than a constant factor.
Extended reading notes
Core claim
The central discovery is Theorem 1.5: for every ε > 0 and 0 < β < 1, there is an n0 such that any β-bounded n-square with n ≥ n0 contains a transversal of size at least (1 − β/4 − ε)n, and such a transversal can be found deterministically in polynomial time. The proof is algorithmic: starting from the largest transversal contained in the main diagonal, it repeats a greedy 'insertion' step that, as long as the current transversal is too small, adds at least εβn/12 new distinct symbols per round. After at most τ = 12/(εβ) rounds it either reaches the target size or produces a larger transversal outright. Taking β = 1 gives Theorem 1.4, a transversal of size (3/4 − ε)n in every equi-n square, which improves on the previous existential 2n/3 bound and on the algorithmic bounds derived from the local lemma whenever β ≥ 0.14.
Load-bearing premise
The linchpin is the bound that after t rounds each row index belongs to at most 4^t C of the index sets R(I(ω)); if this count were substantially larger, the number of pairs inserting new symbols could shrink and the process might stall before reaching the promised transversal size.
Editorial extensions
If this is right
- For equi-n squares, the theorem guarantees a transversal of at least (3/4 − ε)n, improving the previous existential bound of 2n/3 and giving a polynomial-time construction.
- Whenever β ≥ 0.14, the new bound (1 − β/4 − o(1))n beats the guarantees obtained via the Moser–Tardos local lemma distribution in the earlier algorithmic literature.
- The algorithm is deterministic and runs in O(n^2) per round for at most O(1/εβ) rounds, giving a total running time polynomial in n with a mild dependence on ε and β.
- The short elementary proof provides a clean alternative to probabilistic arguments for large transversals, and may serve as a test case for constructive versions of other density-type conjectures.
- For β = 1 the result restores a meaningful version of Stein's conjecture: equi-n squares, while not necessarily containing n−1 transversals, still contain transversals that omit only a quarter of the cells.
Reading between the lines
- The greedy insertion framework might generalise to other rainbow-type problems, such as finding large rainbow matchings in edge-coloured graphs under local frequency restrictions, where pairwise disjointness conditions similar to (C3) appear.
- The constant β/4 is likely not optimal; sharper bounds on the number of useless pairs could push the guarantee toward n − o(n) for β close to 0, though known counterexamples cap any improvement at n − O(log n) for equi-n squares.
- One could test the algorithm's practical performance on random equi-n squares: if it typically outputs transversals much larger than the guaranteed (3/4)n, that would suggest stronger bounds hold in typical instances.
- The proof only uses the global β-boundedness in the counting of triple intersections, so the same argument should work for arrays with a bounded number of 'heavy' symbols appearing more than βn times, as long as the total density deficit remains.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies large transversals in n×n symbol arrays. A transversal is a set of entries with distinct rows, columns, and symbols. The main result, Theorem 1.5, asserts that for every 0<β<1 and every ε>0, every β-bounded n-square (i.e., no symbol appears more than βn times) with n sufficiently large contains a transversal of size at least (1−β/4−ε)n, and such a transversal can be found by a deterministic polynomial-time algorithm. The proof builds a transversal greedily by iteratively constructing disjoint sets of symbols Ω_t together with index sets I(ω) and permutations S(I(ω)) satisfying four properties (A1)–(A4). The engine of the argument is Claim 2.2, which guarantees that |Ω_t| grows by at least εβn/12 in each of τ=12/(εβ) rounds, provided the current diagonal has fewer than (1−β/4−ε)n distinct symbols. Theorem 1.4, the (3/4−o(1))n bound for equi-n squares, follows by taking β=1.
Significance. If the proof is correct after repair, Theorem 1.5 gives a simple deterministic polynomial-time algorithm with a clean constant-factor improvement over previous algorithmic bounds for β-bounded squares when β≥0.14. The argument is self-contained and does not rely on the probabilistic method; it supplies a concrete iterative construction with explicit constants. The paper also gives credit to the independent concurrent work [4], which obtains stronger asymptotics for equi-n squares, and carefully frames the contribution as the simplicity and efficiency of the method. These strengths make the paper potentially valuable despite the fact that the main result is superseded for the equi-n case by [4].
major comments (2)
- [§2, proof of Claim 2.2 (useless-pair count)] The statement 'each ℓ ∈ [n] witnesses the uselessness of at most (4 choose 2) 4^t C pairs' is not justified by the displayed bounds (2.1) and (2.2). For a fixed ℓ, the dominant failure mode of condition (C3) is ℓ ∈ R(I(A_{i,i})) ∩ R(I(A_{j,j})) for a pair (i,j) with A_{i,i}, A_{j,j} ∈ Ω_{<t}. By (2.2) with index t−1, the set of indices i with ℓ ∈ R(I(A_{i,i})) has size at most 4^{t−1}C, so the number of unordered such pairs is at most (4^{t−1}C)^2, not 4^t C. The other cross cases contribute lower-order terms for t≥2. This missing factor changes the correction term in the lower bound on |Ω_t| from O(4^t C) to O(C^2 16^t). Since C=4^τ depends only on ε and β, the final inequality can be restored by taking n0 larger; however, as written the proof of Claim 2.2 is incomplete at a load-bearing point.
- [§2, proof of (2.2) (induction inequality)] The displayed induction step for (2.2) uses the inequality 2(C+4^{t−1}C)+4^{t−1}C ≤ 4^t C, which is false at t=1 because it gives 5C > 4C. The intended recurrence is f(t) ≤ 2f(t−1)+C, which yields f(t) ≤ (2^t−1)C ≤ 4^t C for all t≥1; the t=1 case is also special because for ω∈Ω_0 the index set I(ω) is empty, so the J2 term disappears. This is a repairable arithmetic slip, but a central displayed inequality in the proof is currently false and should be corrected.
minor comments (4)
- [§2, first paragraph of the proof of Theorem 1.5] The sentence 'let A be an equi-n-square' should read 'let A be a β-bounded n-square', since Theorem 1.5 concerns all β-bounded squares and equi-n is only the special case β=1.
- [§2, proof of Claim 2.2 (displayed algebra)] The expressions 'n2_t', 'εβn2/2', and 'εβn2/10' should be typeset as n_t^2, εβn^2/2, and εβn^2/10 to avoid confusion between subscripts and exponents.
- [Abstract and title] The title contains a typographical artifact: 'EFFICIENTL Y' should be 'EFFICIENTLY'.
- [§2, proof of Claim 2.1, Case 3] The inequality |I(ω)| ≤ 4^t ≤ 4^τ = C is correct, but the sentence 'there exist a copy' should be 'there exists a copy' for grammatical clarity.
Circularity Check
No significant circularity: the proof is self-contained and derives the result from first principles; the noted issues are proof gaps, not circular reasoning.
full rationale
The derivation in the paper is fully self-contained. Theorem 1.5 is proved by an explicit deterministic construction: starting from the diagonal of a β-bounded square, the algorithm iteratively builds index sets I(ω) and permutations S(I(ω)) using the definitions of transversals, inserting pairs, and the maximality of the chosen triples Y_t. The lower bound on |Ω_t| in Claim 2.2 is obtained from counting arguments based on (2.1), (2.2), the β-boundedness assumption, and the maximality of Y_t. No assumption in the proof includes the target result, and no external result is cited as a load-bearing input for the main theorem. The constants τ and C are chosen explicitly in the proof rather than fitted to data. The proof does contain a likely arithmetic slip at t=1 in the induction proving (2.2), and the bound on useless pairs may undercount by a constant factor, but these are correctness issues in a specific estimate and do not make the conclusion equivalent to an input by construction. The mention of independent work by Chakraborti et al. is contextual and not used in the proof. There are no self-citations that carry the argument. Therefore the paper does not exhibit circularity.
Assumptions & free parameters
free parameters (2)
- tau =
12/(epsilon beta)
- C =
4 tau = 48/(epsilon beta)
assumptions (2)
- standard math Standard counting and set-theoretic arguments, including union bounds and greedy maximality, are used throughout.
- domain assumption Permuting rows and columns does not change the multiset of symbols or the existence of transversals.
Cite this review
Pith. "Pith review of A note on finding large transversals efficiently." pith.science (2026). https://pith.science/paper/QQRTULQG
@misc{pith2026241205891,
author = {Pith},
title = {Pith review of: A note on finding large transversals efficiently},
year = {2026},
howpublished = {\url{https://pith.science/paper/QQRTULQG}},
note = {Machine review of arXiv:2412.05891}
}
abstract
In an $n \times n$ array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than $\beta n$ times, the array contains a transversal of size $(1-\beta/4-o(1))n$. In particular, if the array is filled with $n$ symbols, each appearing $n$ times (an equi-$n$ square), we get transversals of size $(3/4-o(1))n$. Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals.
Forward citations
Cited by 2 Pith papers
-
Almost-full transversals in equi-$n$-squares
There exists epsilon > 0 such that every equi-n-square contains n - n^(1-epsilon) disjoint transversals of size n - n^(1-epsilon), while some equi-n-squares have no transversal larger than n - (1/(2*sqrt(2)) + o(1))*sqrt(n).
-
Restricted subgraphs of edge-colored graphs and applications
A survey that maps the results and methods for finding rainbow subgraphs in edge-colored graphs, and their applications across discrete mathematics, coding theory, and computer science.
Reference graph
Works this paper leans on
-
[4]
D. Chakraborti, M. Christoph, Z. Hunter, R. Montgomery, and T. Petrov, Almost-full transversals in equi- n-squares, Personal communication
-
[1]
R. Aharoni, E. Berger, D. Kotlar, and R. Ziv, On a conjecture of Stein , Abh. Math. Semin. Univ. Hambg. 87 (2017), 203–211
work page 2017
-
[2]
R. Bissacot, R. Fernández, A. Procacci, and B. Scoppola, An improvement of the Lovász local lemma via cluster expansion, Combin. Probab. Comput. 20 (2011), no. 5, 709–719
work page 2011
-
[3]
R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory , Cambridge University Press, 1991
1991
-
[5]
P. Erdős and J. Spencer, Lopsided Lovász local lemma and Latin transversals , Discrete Applied Math. 30 (1991), no. 151-154, 10–1016
work page 1991
-
[6]
D. G. Harris, New bounds for the Moser-Tardos distribution , Random Struct. Algorithms 57 (2020), no. 1, 97–131
work page 2020
-
[7]
D. G. Harris and A. Srinivasan, Algorithmic and enumerative aspects of the Moser-Tardos dis tribution, ACM Trans. Algorithms 13 (2017), no. 3, 1–40
work page 2017
-
[8]
R. Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large eve n n, arXiv preprint arXiv:2310.19779 (2023)
arXiv 2023
Show all 12 references
-
[9]
R. A. Moser and G. Tardos, A constructive proof of the general Lovász local lemma , Journal of the ACM (JACM) 57 (2010), no. 2, 1–15
2010
-
[10]
Pokrovskiy and B
A. Pokrovskiy and B. Sudakov, A counterexample to Stein ’s Equi- n-square conjecture, Proc. Am. Math. Soc. 147 (2019), no. 6, 2281–2287
2019
-
[11]
H. J. Ryser, Neuere probleme der kombinatorik , Vorträge über Kombinatorik, Oberwolfach (1967), 69–91
1967
-
[12]
S. K. Stein, Transversals of Latin squares and their generalizations. , Pacific J. Math. 59 (1975), 567–575. MA: Institute of Science and Technology Austria (ISTA). PM: Universitat Politècnica de Catalunya (UPC), Barcelona , Spain. Email address : michael.anastos@ist.ac.at, pmo...
1975
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.