Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

Almost-full transversals in equi-$n$-squares

T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Every equi-n-square has many disjoint transversals that each cover all but a vanishing fraction of cells.

desk verdict Main theorem is a real advance and the proof appears sound; the secondary construction has a repairable gap in the arbitrary leftover colouring. read the letter →

arxiv 2412.07733 v1 pith:2E7N6AKM submitted 2024-12-10 math.CO

Debsoumya Chakraborti , Micha Christoph , Zach Hunter , Richard Montgomery , Teo Petrov This is my paper · ORCID
classification math.CO MSC 05B1505C7005C6505D15
keywords equi-n-squaretransversalLatinsquarehypergraphmatchingpartialsemi-randommethodchromaticindexSteinconjecture
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

An equi-$n$-square is an $n\times n$ array in which each of $n$ symbols appears exactly $n$ times. The paper proves that, for some fixed $\varepsilon>0$, every equi-$n$-square contains at least $n - n^{1-\varepsilon}$ disjoint transversals, each with at least $n - n^{1-\varepsilon}$ cells, where a transversal is a set of cells sharing no row, column, or symbol. This settles the asymptotic version of a 1975 conjecture: although a transversal of size $n-1$ is not guaranteed, a transversal covering all but a vanishing fraction of the array always is, and in fact almost the whole array can be packed with such transversals. The paper also constructs equi-$n$-squares in which every transversal omits at least $(1/(2\sqrt{2})+o(1))\sqrt{n}$ cells, showing that the $n-\Omega(\sqrt{n})$ scale is a real obstruction to sharper guarantees.

What carries the argument

The load-bearing device is a bounded-dependence random matching algorithm. The square is converted into an auxiliary bipartite multigraph whose vertices are columns and symbols and whose edges correspond to blocks of cells sharing a column and symbol; because of the degree and codegree conditions this multigraph splits into few matchings. The algorithm pairs these matchings, deletes a small set of edges to split each union into paths and cycles of controlled length, and then randomly selects one of the two parity classes inside each short component, producing a large random matching in which the appearance of any edge depends on only a bounded number of other random choices. McDiarmid's bounded-difference inequality concentrates the resulting degree and codegree statistics, after which a defect Hall argument finds a large matching in the row-column auxiliary graph; this matching is automatically a transversal. To get many disjoint transversals, the residual hypergraph after the random selection is colored with $(1+n^{-\xi})n$ colors using a near-optimal list-colouring theorem for hypergraphs with bounded codegrees, and the color classes are the almost-full transversals.

What would settle it

To falsify Theorem 1.1 it would be enough to produce, for arbitrarily large $n$, an equi-$n$-square whose largest transversal has at most $n - n/\log n$ cells: for every fixed $\varepsilon>0$, $n^{1-\varepsilon} < n/\log n$ for large $n$, so such a square would contradict the guaranteed transversal of size $n - n^{1-\varepsilon}$.

Watch

Extended reading notes

Core claim

Taken on its own terms, the paper's central claim is Theorem 1.1: there is an absolute $\varepsilon>0$ such that every equi-$n$-square contains $n - n^{1-\varepsilon}$ disjoint transversals of size at least $n - n^{1-\varepsilon}$. Because $n^{1-\varepsilon}/n\to 0$, this gives the first proof that equi-$n$-squares always have a transversal of size $(1-o(1))n$, answering the 2019 question of whether the original conjecture holds asymptotically. The theorem is deduced from a hypergraph formulation in which the square becomes an $n$-regular $3$-partite $3$-uniform hypergraph on $3n$ vertices, with only the row-column pairs required to have codegree at most $1$; the proof works under substantially weaker codegree hypotheses. In addition, Theorem 1.2 modifies an earlier construction to produce equi-$n$-squares whose largest transversal has size at most $n - (1/(2\sqrt{2})+o(1))\sqrt{n}$, the first construction with a square-root loss.

Load-bearing premise

The argument assumes that the auxiliary multigraph formed from blocks of the hypergraph has maximum degree at most $D^\mu$, so that it can be split into few matchings and recombined in short random pieces; if the codegree pattern allowed this auxiliary degree to be large, the concentration step would have no bounded-dependence structure to exploit.

Editorial extensions

If this is right

  • The asymptotic form of the original conjecture is true: every equi-$n$-square has a transversal of size $(1-o(1))n$ cells.
  • The square's cells are almost decomposable: the $n^2$ cells can be covered by disjoint transversals up to $O(n^{2-\varepsilon})$ leftover cells, so the failure of exact decomposition is a vanishing fraction.
  • The lower-bound construction shows that one cannot in general guarantee a transversal of size $n - o(\sqrt{n})$; the $n-\Omega(\sqrt{n})$ scale is a genuine barrier.
  • In hypergraph language, an $n$-regular $3$-partite $3$-uniform hypergraph on $3n$ vertices whose only restriction is codegree at most $1$ between two of the parts has an almost-perfect matching decomposition.
  • Since the proof tolerates codegrees up to $n^{1-\mu}$, the same almost-decomposition conclusion holds for squares with many repeated symbols per row-column pair.

Reading between the lines

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

  • The matching algorithm's reliance on bounded-length paths and cycles suggests a general recipe: whenever a highly regular structure can be decomposed into a few matchings, randomly recombining short alternating components gives concentration in settings where global independence fails; this could apply to other packing problems in dense hypergraphs.
  • The constant $1/(2\sqrt{2})$ in Theorem 1.2 is plausibly optimal; if the paper's Conjecture 1.3 is true, then $n-C\sqrt{n}$ is the exact order of the worst-case missing cells, and the block-pairing construction would be the natural extremal example.
  • The hypergraph theorem needs only one of the three pairwise codegree conditions from the Latin-square setting. A testable extension is whether even that condition can be dropped, or replaced by a bipartiteness condition on large codegrees as in Theorem 4.3, without losing the almost-decomposition conclusion.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper proves two main results about equi-n-squares. Theorem 1.1 shows that for some fixed epsilon > 0, every equi-n-square contains at least n - n^{1-epsilon} pairwise disjoint transversals, each of size at least n - n^{1-epsilon}; this positively answers the asymptotic form of Stein's conjecture asked by Pokrovskiy and Sudakov. Theorem 1.2 gives, for every n, an equi-n-square with no transversal larger than n - (sqrt(2)/2 + o(1)) sqrt(n), improving the previous n - O(log n) counterexample. The proof of Theorem 1.1 is carried out at the level of 3-uniform hypergraphs: a bounded-dependence random matching lemma (Lemma 4.5) is used to build a random subhypergraph with controlled degrees and codegrees, and a list-colouring theorem of Molloy and Reed is then applied to obtain an almost-perfect decomposition into matchings. Section 2 contains the elementary construction for Theorem 1.2, Section 3 sketches the random matching idea, and Section 4 gives the full proof of Theorem 1.1.

Significance. If Theorem 1.1 is correct, it is a substantial advance in a central problem on transversals: it confirms the approximate Stein conjecture and, moreover, establishes an almost-decomposition of every equi-n-square into almost-full transversals. This is considerably stronger than the previously known (3/4 - o(1))n bound. The lower-bound construction in Theorem 1.2 is also a genuine improvement and is very natural. The proof of Theorem 1.1 introduces a bounded-dependence random matching technique that is likely to be useful elsewhere. The paper is careful with concentration estimates and explicitly derives the required edge-loss bounds; the main theorem is not obtained by curve-fitting constants but rests on previously established results (Molloy-Reed, McDiarmid, Hall, Chernoff). However, the general-n construction in Section 2 has a concrete gap as written, and one step in the proof of Lemma 4.5 is stated in a way that appears formally empty; both are repairable but need attention.

major comments (2)
  1. [Section 2, proof of Theorem 1.2 for general n] The pairing of boxes is inconsistent with the claim that there are 2ab pairs. The three listed pairings cover 2b diagonal boxes, b(b-1) boxes from the symmetric pairs with 1 <= i < j <= b, and 4b(a-b) boxes from the vertical pairs, for a total of 4ab - 3b^2 + b boxes. Since the grid has 4ab boxes, this leaves 3b^2 - b boxes unpaired, contradicting the sentence 'using that there will be 2ab <= n pairs of boxes'. The natural correction is to take symmetric pairs for all 1 <= i < j <= 2b, as in the special case n = 2m^2, but as written the unpaired boxes inside S' are left to the subsequent arbitrary colouring. That arbitrary colouring need not satisfy the locality assertion in Claim 2.2 that every non-blue colour used in C_j does not appear in S' \ C_j; without this assertion, the pigeonhole step 'C_j uses a+b-1 non-blue colours ... T' misses out on at least one colour' is unsupported. Theorem 1.2 is therefore not proven as written; it is repairable, but the construction and Claim 2.2 need to be corrected together.
  2. [Section 4.1, Claim 4.9] The proof of Claim 4.9 defines X^h using conditions that refer to H^h_2, but H^h_2 was already chosen to satisfy D1-D3. Hence every bullet in the definition of X^h holds for every vertex, X^h is empty, and the claimed probability bound on X^h is vacuous. The intended argument is evidently to define X^h using H^h_1, with the inequalities and quantifiers arranged so that X^h contains a vertex whenever one of the local codegree, degree, or block-size constraints fails for H^h_1, then to use Claims 4.6-4.8 to bound |X^h|, delete the edges incident to X^h, and invoke maximality of H^h_2. As printed, however, the edge-loss control from H^h_1 to H^h_2 is not formally established. This is a load-bearing step in Lemma 4.5, so it must be rewritten.
minor comments (3)
  1. [Section 2, proof of Theorem 1.2] The notation m is reused in the special case n = 2m^2 and in the general construction with a different meaning; this is not mathematically wrong but is easy to confuse.
  2. [Section 4.1, final paragraph of Lemma 4.5] The expression e(H^0_2) is used in the last display, although H^0_2 was defined much earlier as equal to H_1; a short reminder of this identification would improve readability.
  3. [Section 4.2, proof of Theorem 4.3] The phrase 'by an application of Markov's lemma' is nonstandard; the step uses the probabilistic method and Chernoff/local lemma bounds. It would be clearer to state explicitly that the favourable events have positive joint probability and that the small exceptional set has size at most |H|.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.1 is derived from an external list-colouring theorem and a self-contained probabilistic construction; the authors' self-citations are contextual and not load-bearing.

full rationale

I walked the derivation chain for the central claim, Theorem 1.1. It is deduced from Theorem 4.3, which is proved from Lemma 4.5 and Corollary 4.2. Corollary 4.2 rests on the Molloy--Reed list-colouring theorem (Theorem 4.1), an external result with stated hypotheses, and Lemma 4.5 is developed self-containedly through the block decomposition B1--B3, the auxiliary multigraph K, the random matching process, and the concentration estimates in Claims 4.6--4.11, using McDiarmid's inequality and Chernoff bounds. The constants are chosen by a hierarchy with no fitting step: the inequalities epsilon << gamma << mu << eta are ordering assumptions, not parameters calibrated to the target conclusion. The only self-citations occur in the introduction: [8] (Montgomery's proof of the Ryser--Brualdi--Stein conjecture for large even n) is mentioned as context, and [10] (Montgomery--Pokrovskiy--Sudakov on Ringel's conjecture) is described as high-level inspiration; neither is used as a premise in the proof of Theorem 1.1 or Theorem 4.3. I also checked the auxiliary degree bound highlighted by the reader: the claim that K has maximum degree at most k follows from the edge-disjointness of the m-edge blocks at each vertex, together with the chosen hierarchy, rather than from any circular assumption. The one concrete weakness I found is in the proof of Theorem 1.2 for general n: after the paired boxes are coloured, the remaining cells are coloured 'arbitrarily', and Claim 2.2 uses the assertion that each non-blue colour in C_j 'does not appear in S' \ C_j'; this locality property is shown for the paired colours but not for the leftover arbitrary colours. This is a correctness gap in Theorem 1.2 as written, not a circularity, because the claim is asserted for a construction step rather than derived from the conclusion it is meant to prove. Overall, the central result is self-contained against external benchmarks, so the circularity score is 0.

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

The proof uses no fitted parameters: the constants epsilon, mu, eta, gamma, and xi are existential choices with a fixed hierarchy, not numbers calibrated to data. The external results used are standard theorems in combinatorics and probability. No new particles, forces, dimensions, or unexplained entities are introduced.

assumptions (5)
  • standard math Theorem 4.1 (Molloy and Reed): every k-uniform hypergraph with maximum codegree B and maximum degree Delta has list chromatic index at most (1 + C_k(B/Delta)^(1/k)(log(Delta/B))^4)Delta.
    Used as the input to Corollary 4.2, which bounds the chromatic index of the random subhypergraphs H''_i and hence of H'.
  • standard math McDiarmid's bounded differences inequality (Lemma 4.4).
    Applied throughout Section 4 to prove concentration of row degrees, codegrees, and edge counts in the random matching process.
  • standard math Hall's matching theorem and its defect version.
    Used in the proof sketch to match columns to blocks and to find a large matching in the auxiliary graph L, which translates to a transversal.
  • standard math Chernoff bounds and the Lovasz local lemma.
    Used in the proof of Theorem 4.3 to control the number of subhypergraphs containing each edge and to maintain degree and codegree bounds after redistribution.
  • domain assumption The translation from an equi-n-square to an n-regular 3-partite 3-uniform hypergraph with row-column codegree exactly 1.
    This standard representation is the foundational modeling step. It makes the high-codegree graph in Theorem 4.3 bipartite, since high codegrees only occur between symbols and rows or between symbols and columns.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Almost-full transversals in equi-$n$-squares." pith.science (2026). https://pith.science/paper/2E7N6AKM

@misc{pith2026241207733,
  author       = {Pith},
  title        = {Pith review of: Almost-full transversals in equi-$n$-squares},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2E7N6AKM}},
  note         = {Machine review of arXiv:2412.07733}
}
abstract

In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi-$n$-square (an $n\times n$ array filled with $n$ symbols where each symbol appears exactly $n$ times) has a transversal of size $n-1$. That is, it should have a collection of $n-1$ entries that share no row, column, or symbol. In 2017, Aharoni, Berger, Kotlar, and Ziv showed that equi-$n$-squares always have a transversal with size at least $2n/3$. In 2019, Pokrovskiy and Sudakov disproved Stein's conjecture by constructing equi-$n$-squares without a transversal of size $n-\frac{\log n}{42}$, but asked whether Stein's conjecture is approximately true. I.e., does an equi-$n$-square always have a transversal with size $(1-o(1))n$? We answer this question in the positive. More specifically, we improve both known bounds, showing that there exist equi-$n$-squares with no transversal of size $n-\Omega(\sqrt{n})$ and that every equi-$n$-square contains $n-n^{1-\Omega(1)}$ disjoint transversals of size $n-n^{1-\Omega(1)}$.

Figures

Figures reproduced from arXiv: 2412.07733 by the authors.

Figure 1
Figure 1. a) Our construction in the simplified case when n = 2m2 with m = 3. b) The boxes comprising C3 in the same equi-n-square with a transversal highlighted – if a light blue square appears in C3 in a transversal then at most 4 of the 5 colours appearing only in C3 can appear. Thus, at least one colour from C3 ∪ C4 is omitted in any transversal. 2 Equi-n-squares with no partial transversal of size n − Ω(√n) To illustrate… view at source ↗
Figure 2
Figure 2. a) A subsquare S in which each column can be decomposed into 4 blocks with size 4 which have the same colour (for ease of visualisation, cells of each colour are often drawn next to each other in natural blocks, but this is not required in general). b) The multigraph K corresponding to S. c) A matching M in K. d) The subsquare S ′ ⊂ S corresponding to the matching M. Any set of cells which share no row or column mus… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Colour-balanced subgraphs

    math.CO 2026-04 unverdicted novelty 7.0 of 10

    Colour-balanced k-edge-coloured K_{2kt} has a perfect matching adjustable to colour-balance by recolouring O(k^2) edges.

  2. Restricted subgraphs of edge-colored graphs and applications

    math.CO 2024-12 conditional novelty 2.0 of 10

    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

14 extracted references · 9 canonical work pages · cited by 2 Pith papers

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, D. Kotlar, and R. Ziv. On a conjecture of Stein. In Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg, volume 87, pages 203–211. Springer, 2017

    work page 2017

  2. [2]

    Alon and J

    N. Alon and J. H. Kim. On the degree, size, and chromatic index of a uniform hypergraph. Journal of Combinatorial Theory, Series A , 77(1):165–170, 1997

    work page 1997

  3. [3]

    Anastos and P

    M. Anastos and P. Morris. A note on finding large transversals efficiently.arXiv preprint: 2412.05891 , 2024

    arXiv 2024

  4. [4]

    R. A. Brualdi and H. J. Ryser. Combinatorial matrix theory . Cambridge University Press, 1991

    1991

  5. [5]

    L. Euler. Recherches sur un nouvelle esp´ ece de quarr´ es magiques. Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen , pages 85–239, 1782

    work page

  6. [6]

    McDiarmid

    C. McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser. , pages 148–188. Cambridge Univ. Press, Cambridge, 1989

    work page 1989

  7. [7]

    Molloy and B

    M. Molloy and B. Reed. Near-optimal list colorings. Random Structures & Algorithms , 17(3-4):376– 402, 2000

    work page 2000

  8. [8]

    Montgomery

    R. Montgomery. A proof of the Ryser-Brualdi-Stein conjecture for large even n. arXiv preprint arXiv:2310.19779, 2023

    arXiv 2023

Show all 14 references
  1. [9]

    Montgomery

    R. Montgomery. Transversals in Latin squares. page 131–158, 2024

    2024

  2. [10]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3):663–720, 2021

    2021

  3. [11]

    Pokrovskiy

    A. Pokrovskiy. Rainbow Subgraphs and their Applications , page 191–214. London Mathematical Society Lecture Note Series. Cambridge University Press, 2022

    2022

  4. [12]

    Pokrovskiy and B

    A. Pokrovskiy and B. Sudakov. A counterexample to Stein’s equi- n-square conjecture. Proceedings of the American Mathematical Society , 147(6):2281–2287, 2019

    2019

  5. [13]

    H. Ryser. Neuere Probleme der Kombinatorik. Vortr¨ age ¨ uber Kombinatorik, Oberwolfach, pages 69–91, 1967

    1967

  6. [14]

    S. K. Stein. Transversals of Latin squares and their generalizations. 1975. 16

    1975

Pith tools

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