{"id":"9fe27aad-ac6d-4c26-9269-a499ba2b3801","arxiv_id":"2412.07733","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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).","lead":"Every equi-n-square, an n by n array where each of n symbols appears n times, is shown to contain almost n disjoint transversals of size almost n. The same paper constructs arrays where any transversal must miss Omega(sqrt(n)) cells, showing Stein's approximate conjecture is the right statement.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central Theorem 1.1 proof withstands scrutiny; the one concrete gap is in Theorem 1.2's general-n construction, where the arbitrary leftover colouring is not shown to satisfy the locality condition on which Claim 2.2 depends.","rationale":"The central theorem of the paper, Theorem 1.1, appears mathematically sound. The proof of Lemma 4.5 is intricate, but the reader's identified weakest assumption is actually secure: edge-disjointness of the m-edge blocks gives maximum degree at most D/m <= k in the auxiliary multigraph K, so the subsequent splitting into k matchings and the bounded-dependence random choices are justified. The later stages of the argument, including the use of Corollary 4.2 to colour the subhypergraphs H''_i and the final decomposition argument in Theorem 1.1, are consistent with the stated constants. Thus no load-bearing concern about the central claim was found.\n\nThe paper as a whole, however, contains a genuine missing-support issue in Theorem 1.2. The general-n construction fills the uncoloured cells 'arbitrarily', but the proof of Claim 2.2 requires that each non-blue colour appearing in C_j not appear elsewhere in S'. For the paired colours this property is automatic for the j <= 2b considered, but for leftover colours it depends entirely on how the arbitrary colouring is chosen. The text supplies no such choice or verification, so the claimed n - Omega(sqrt n) obstruction is not fully proved. The gap is likely fixable by a careful placement of leftover colours inside individual C_j strips and top-up cells outside S', but that construction must be written out. For this reason the overall verdict should be CONDITIONAL rather than unconditional acceptance, even though the main theorem itself holds up.","tokens_in":21110,"tokens_out":36580,"duration_ms":336932,"concrete_test":"Repair or refute the general-n construction of Theorem 1.2 by explicitly prescribing the leftover colouring: place the n - 2ab top-up cells of each paired colour in S \\ S', and partition the roughly 1.5 b^2 leftover colours among the strips C_j so that each leftover colour's n cells lie entirely within unpaired boxes of a single C_j. Verify the capacity count |unpaired cells of C_j| >= n for each assigned colour; if this holds, Claim 2.2's 'does not appear in S' \\ C_j' assertion is restored and Theorem 1.2 follows. If such a placement cannot be made, the current arbitrary-colouring argument is genuinely invalid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"No significant objection to the paper's central claim, Theorem 1.1, was identified. The reader's nominated weak spot, the degree bound on the auxiliary multigraph K in Lemma 4.5, checks out: for each v, the m-edge blocks in B with v in U_B and the blocks in B_v are edge-disjoint subsets of the at most D edges incident to v, so the degree of v in K is at most D/m, which is at most k = D^mu. This justifies the k-edge-colouring of K and the bounded-dependence random matching construction. The concentration estimates in Claims 4.6-4.11 and the deduction of Theorems 4.3 and 1.1 are internally consistent.\n\nThe real concrete gap is in the proof of Theorem 1.2 for general n. After pairing some boxes, the remaining cells, including the unpaired boxes inside the subsquare S', are coloured 'arbitrarily'. Claim 2.2 uses the assertion that every non-blue colour used in C_j 'does not appear in S' \\ C_j'. This holds for the paired colours for the j <= 2b considered, because each non-blue pair lies inside the relevant C_j. It is not shown, however, for the leftover colours: an arbitrary assignment may place the same colour both inside C_j and outside C_j, in which case a transversal can use that colour outside C_j and the pigeonhole counting in Claim 2.2 no longer forces a missed colour in C_j. Since no explicit construction of the leftover colouring with the required locality property is given, Theorem 1.2 is incomplete as written; it appears repairable but needs a further argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21419,"tokens_out":19679,"duration_ms":171479,"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":[{"comment":"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.","section":"Section 2, proof of Theorem 1.2 for general n"},{"comment":"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.","section":"Section 4.1, Claim 4.9"}],"minor_comments":[{"comment":"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.","section":"Section 2, proof of Theorem 1.2"},{"comment":"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.","section":"Section 4.1, final paragraph of Lemma 4.5"},{"comment":"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|.","section":"Section 4.2, proof of Theorem 4.3"}],"recommendation":"major_revision","confidential_remarks":"The main theorem, Theorem 1.1, is an important result and the proof appears to withstand scrutiny modulo the clarification of Claim 4.9. The concrete gap in Theorem 1.2 is very likely a typo in the pairing range ('b' instead of '2b'), but since the manuscript as it stands leaves unpaired boxes inside S' and then claims a locality property for all non-blue colours, the theorem is incomplete in the submitted version. I would not reject the paper; a revision that corrects the pairing count and rewrites Claim 4.9 would make the two stated theorems both rigorous. The paper deserves a careful reading after revision, especially of the dense final part of Lemma 4.5."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the main result is genuine and the proof holds up under scrutiny: Theorem 1.1 answers Pokrovskiy and Sudakov's asymptotic question, gives n - n^{1-o(1)} disjoint almost-full transversals, and the bounded-dependence random matching lemma is a real innovation, not just a repackaged Rödl nibble. The hierarchy of constants is existential and there's no sign of post-hoc fitting. I checked the reader's nominated weak spot in Lemma 4.5 — the degree bound on K — and it checks out: the m-edge blocks are edge-disjoint subsets of the D edges at a vertex, so degree at most D/m ≤ D^{1-μ} = k. The concentration claims (4.6–4.11) and the deduction of Theorems 4.3 and 1.1 are internally consistent. This is a serious proof.\n\nThe one concrete gap is smaller and secondary: the proof of Theorem 1.2 for general n. After pairing the boxes, the leftover cells in the unpaired boxes are coloured arbitrarily. Claim 2.2 uses that every non-blue colour used in C_j does not appear in S' \\ C_j. That locality is true for the paired colours, but it is not shown for an arbitrary leftover colouring, and an arbitrary colour could appear both inside and outside C_j. Then the pigeonhole step only forces a colour to be missed inside C_j; the transversal could use that same colour outside C_j, so the claim no longer gives a colour missed by T'. This looks repairable — one would need to assign leftover colours carefully, or add a separate argument — but as written Theorem 1.2 is incomplete.\n\nEverything else checks out. The construction for n = 2m^2 is clean and correct, the literature is cited properly, and the paper is honest about its limitations and the Alon–Kim obstruction.\n\nWho is this for? Anyone working on Latin squares, transversals, or hypergraph matching. It deserves a serious referee: the main theorem is important, and the referee time should be spent on the Section 2 general-n construction and on verifying the bounded-dependence machinery. I'd send it to review and flag Theorem 1.2's gap to the authors.","headline":"Main theorem is a real advance and the proof appears sound; the secondary construction has a repairable gap in the arbitrary leftover colouring.","tokens_in":21976,"tokens_out":3924,"would_cite":true,"duration_ms":31276,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B15","05C70","05C65","05D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every equi-n-square has many disjoint transversals that each cover all but a vanishing fraction of cells.","keywords":["equi-n-square","transversal","Latin square","hypergraph matching","partial transversal","semi-random method","chromatic index","Stein conjecture"],"falsifier":"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}$.","tokens_in":20897,"feed_emoji":"🔢","tokens_out":10019,"duration_ms":90220,"temperature":0.7,"pith_summary":"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.","feed_headline":"Equi-n-squares almost decompose into large disjoint transversals","feed_subtitle":"Every symbol-balanced square has a transversal covering all but o(n) cells, and nearly a full set of them.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the conjecture that every equi-n-square has a transversal of size $n-1$, the target that this paper rescues in asymptotic form.","marker":"[14]"},{"why":"Constructs equi-n-squares with no transversal of size $n-(\\log n)/42$ and poses the asymptotic question answered here.","marker":"[12]"},{"why":"Gives the $2n/3$ lower bound for all equi-n-squares, the strongest prior general guarantee that Theorem 1.1 improves.","marker":"[1]"},{"why":"Gives the $(3/4-o(1))n$ lower bound, the immediate previous record for large transversals in equi-n-squares.","marker":"[3]"},{"why":"Supplies the near-optimal list chromatic index bound used to color the residual hypergraph into few matchings.","marker":"[7]"},{"why":"Supplies the bounded-difference concentration inequality used throughout the random matching argument.","marker":"[6]"}],"fun_headline_variants":["Nearly full transversals in every equi-n-square","Equi-n-squares always have n - o(n) transversals","Stein's conjecture holds asymptotically","Disjoint large transversals in symbol-balanced squares","Answering Pokrovskiy-Sudakov: almost-full transversals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Nearly full transversals in every equi-n-square","Equi-n-squares always have n - o(n) transversals","Stein's conjecture holds asymptotically","Disjoint large transversals in symbol-balanced squares","Answering Pokrovskiy-Sudakov: almost-full transversals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000313,"raw_usage":{"total_tokens":1825,"prompt_tokens":1041,"completion_tokens":784,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":657,"completion_tokens_details":{"reasoning_tokens":704}},"tokens_in":657,"tokens_out":784,"duration_ms":8052,"temperature":1.0,"reasoning_tokens":704,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:33:00.589470+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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}$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the conjecture that every equi-n-square has a transversal of size $n-1$, the target that this paper rescues in asymptotic form."},{"cited_title":"Pokrovskiy and B","cited_arxiv_id":null,"evidence_quote":"Constructs equi-n-squares with no transversal of size $n-(\\log n)/42$ and poses the asymptotic question answered here."},{"cited_title":"Aharoni, E","cited_arxiv_id":null,"evidence_quote":"Gives the $2n/3$ lower bound for all equi-n-squares, the strongest prior general guarantee that Theorem 1.1 improves."},{"cited_title":"Molloy and B","cited_arxiv_id":null,"evidence_quote":"Supplies the near-optimal list chromatic index bound used to color the residual hypergraph into few matchings."},{"cited_title":"McDiarmid","cited_arxiv_id":null,"evidence_quote":"Supplies the bounded-difference concentration inequality used throughout the random matching argument."}],"review_version":1}