{"id":"fc00b47d-cf05-4c95-857e-bbb3ba135424","arxiv_id":"2412.05891","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Every beta-bounded n-square has a transversal of size (1 - beta/4 - o(1)) n, findable by a deterministic polynomial-time algorithm.","lead":"This paper proves that any n x n array where each symbol appears at most beta n times contains a transversal (a set of entries with distinct rows, columns, and symbols) of size at least (1 - beta/4 - o(1)) n, and gives a deterministic polynomial-time algorithm to find it. The result improves previous bounds for equi-n squares and for the algorithmic search of large transversals.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 2.2 undercounts useless pairs: a fixed ℓ can witness roughly (4^{t-1}C)^2 pairs via R(I(A_i,i))∩R(I(A_j,j)), not 4^tC, so the |Ω_t| growth bound is not proven as written; the error is constant-scale and repairable by enlarging n0.","rationale":"The paper proves Theorem 1.5 by iterating a growth step (Claim 2.2) that requires a lower bound on the number of usable insertion triples. The weakest point is the bound on useless pairs, exactly where the reader located the problem. My independent count confirms that the paper's bound (4 choose 2)4^tC is too small: for a fixed ℓ, the intersection of two R(I(A_i,i))-type sets can contain up to (4^{t-1}C)^2 pairs. This is a genuine error in the written proof, not a mere typo, because it changes the subtracted term by a factor that grows like C·4^t. However, the corrected bound is still O(n) in total, and after dividing by 5n it contributes only a constant. The proof's final line uses 'n sufficiently large', so the constant can be absorbed by choosing n0 large enough, provided one also adjusts τ if needed. Thus the central claim is not falsified by this concern; the paper needs a corrected useless-pair count and a correspondingly larger n0. I also checked the (2.2) induction slip: the displayed inequality at t=1 is false, but a standard recurrence proves the stronger f(t) ≤ 2^tC, so (2.2) itself is sound. The additional note about independent work by Chakraborti et al. does not undermine Theorem 1.5's independent algorithmic contribution. Overall, the reader's conditional verdict is appropriate: the result is plausible and likely correct, but the proof as written is incomplete and should be repaired before acceptance.","tokens_in":6417,"tokens_out":32487,"duration_ms":302886,"concrete_test":"Independently recompute the per-ℓ useless-pair bound in Claim 2.2. For fixed ℓ, define B_ℓ = {i : A_i,i ∈ Ω_{<t} and ℓ ∈ R(I(A_i,i))}; by (2.2) with s = t−1, |B_ℓ| ≤ 4^{t-1}C. Count pairs (i,j) with i,j ∈ B_ℓ as witnesses of a failed (C3) via R(I(A_i,i))∩R(I(A_j,j)); this gives at most (4^{t-1}C)^2 pairs, not 4^tC. Then rerun the |Ω_t| lower-bound chain with the corrected total useless-pair bound, replacing 4^tCn by Θ(C^2 16^t)·n, and check whether for n ≥ n0(ε,β) the conclusion |Ω_t| ≥ εβn/12 still follows. If the corrected constant can be absorbed into n0, the theorem stands after a constant-factor repair; if the linear term εβn is overwhelmed, Claim 2.2 collapses and with it the iteration argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The engine of Theorem 1.5 is Claim 2.2, which asserts |Ω_t| ≥ εβn/12. A key step in its proof is the assertion that each ℓ ∈ [n] witnesses the uselessness of at most (4 choose 2)4^tC pairs (i,j) with A_i,i,A_j,j ∈ Ω_{<t}. This is too small. For a fixed ℓ, the dominant failure mode of (C3) is ℓ ∈ R(I(A_i,i)) ∩ R(I(A_j,j)). By (2.2) with s = t−1, the set B_ℓ = {i : ℓ ∈ R(I(A_i,i))} has size at most 4^{t-1}C. Hence the number of unordered pairs (i,j) from B_ℓ is at most (4^{t-1}C)^2 = 16^{t-1}C^2, not 4^tC. The other cross cases (e.g., ℓ ∈ R(i) ∩ R(I(A_j,j))) contribute at most C·4^{t-1}C, which is smaller for t ≥ 2. Therefore the total number of useless pairs can be as large as n·K with K ≈ C^2·16^t, exceeding the paper's n·4^tC by a factor roughly C·4^t. This weakens the lower bound on available triples before the maximality argument. The concern is real but not fatal: K is a constant depending only on ε and β, so the extra term K/5 in the final inequality can be absorbed by taking n0 larger. Separately, the displayed induction step for (2.2) contains an arithmetic slip at t=1 (2(C+4^{t-1}C)+4^{t-1}C ≤ 4^tC is false), but (2.2) itself can be proved with the sharper recurrence f(t) ≤ 2f(t−1)+C, so that slip is typographical. The load-bearing gap is the useless-pair count, which must be corrected before the proof is complete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6879,"tokens_out":6657,"duration_ms":59494,"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":[{"comment":"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.","section":"§2, proof of Claim 2.2 (useless-pair count)"},{"comment":"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.","section":"§2, proof of (2.2) (induction inequality)"}],"minor_comments":[{"comment":"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.","section":"§2, first paragraph of the proof of Theorem 1.5"},{"comment":"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.","section":"§2, proof of Claim 2.2 (displayed algebra)"},{"comment":"The title contains a typographical artifact: 'EFFICIENTL Y' should be 'EFFICIENTLY'.","section":"Abstract and title"},{"comment":"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.","section":"§2, proof of Claim 2.1, Case 3"}],"recommendation":"major_revision","confidential_remarks":"The two issues in Claim 2.2 are repairable and do not appear to affect the truth of Theorem 1.5. The useful-pair-count problem changes a constant that can be absorbed by enlarging n0, and the induction slip in (2.2) can be fixed with a standard recurrence. The paper would be strengthened by explicitly rewriting these two steps. I also note that the independent result [4] supersedes the equi-n portion, so the journal fit should be assessed against the β-bounded algorithmic contribution, which remains of independent interest."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this note proves a real improvement and introduces a genuinely different deterministic method. The main theorem, (1−β/4−o(1))n transversals in β-bounded squares, beats the local-lemma-based bounds for β ≥ 0.14, and the equi-n case gives 3/4−o(1)n. The iterative construction with index sets and permutations is new and worth knowing.\n\nThe paper is well-written and self-contained. The definitions (P1), (P2), R(i), etc. are clear, and the algorithm is simple enough to describe in a short note. The citation pattern is proper, including an honest acknowledgment of the independent work by Chakraborti et al. that gets n−o(n) for equi-n squares.\n\nHowever, there are two specific issues in the proof of Claim 2.2, the engine of the paper. The first is a genuine undercount: for a fixed ℓ, the number of useless pairs that ℓ witnesses is claimed to be at most 6·4^t C, but the dominant failure mode is ℓ ∈ R(I(A_i,i)) ∩ R(I(A_j,j)), giving on the order of (4^{t−1}C)^2 pairs, not 4^t C. This is a real gap in the written proof. The second is an arithmetic slip in the induction step for (2.2) at t=1; that one looks typographical, and the bound (2.2) itself can be proved with a sharper recurrence. Neither issue looks fatal: the extra term is a constant depending on ε and β, so enlarging n0 absorbs it. But the proof as written is not correct.\n\nOne minor note: the text says C := 4τ in the introduction; the proof uses C = 4^τ. Presumably a rendering issue, but the authors should make sure it's unambiguous.\n\nBottom line: the result is likely correct and the method is a genuine contribution. The paper deserves serious refereeing; it should be accepted after the authors repair the counting in Claim 2.2. I'd bring it to reading group to discuss the method.","headline":"Real advance with a new deterministic method; proof has a repairable counting gap in Claim 2.2.","tokens_in":7416,"tokens_out":14484,"would_cite":true,"duration_ms":126591,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B15","05D15","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["transversals","equi-n squares","β-bounded squares","Latin squares","deterministic algorithm","greedy insertion","Stein's conjecture"],"falsifier":"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.","tokens_in":6225,"feed_emoji":"🧩","tokens_out":9030,"duration_ms":78552,"temperature":0.7,"pith_summary":"This paper tackles the problem of finding large transversals—sets of cells with distinct rows, columns, and symbols—in n×n arrays whose symbols are not too frequent. It establishes that if no symbol occurs more than βn times (a β-bounded square), then a transversal of size (1 − β/4 − o(1))n always exists, and, crucially, that such a transversal can be produced by a deterministic algorithm with polynomial running time. For equi-n squares, where each of n symbols appears exactly n times, the result specialises to transversals of size (3/4 − ε)n, improving earlier existential bounds and offering a constructive version of a weakened Stein conjecture. Because the proof is short and elementary, it also serves as a clean benchmark for algorithmic approaches to dense transversals.","feed_headline":"New algorithm finds large transversals in symbol-rich grids","feed_subtitle":"For squares where no symbol appears too often, it finds a transversal missing at most β/4 + ε of the n cells.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Stein's conjecture that every equi-n square has a transversal of size n−1 is the motivating open problem; the paper aims to save a weakened version.","marker":"[12]"},{"why":"Pokrovskiy and Sudakov's counterexample shows Stein's conjecture is false, motivating the search for approximate transversals.","marker":"[10]"},{"why":"Aharoni, Berger, Kotlar, and Ziv used topological methods to prove existence of transversals of size 2n/3 in equi-n squares; the new Theorem 1.4 improves this existential bound.","marker":"[1]"},{"why":"Erdős and Spencer introduced β-bounded squares and the lopsided local lemma for full transversals, setting the stage for this problem.","marker":"[5]"},{"why":"Harris's new bounds for the Moser–Tardos distribution give an algorithmic guarantee that Theorem 1.5 improves whenever β ≥ 0.14.","marker":"[6]"},{"why":"Harris and Srinivasan's algorithmic work on the Moser–Tardos distribution for large transversals is another previous bound that the new result outperforms in the stated regime.","marker":"[7]"}],"fun_headline_variants":["Deterministic algorithm finds transversals of size (1−β/4−ε)n","Equi-n squares get transversals of size (3/4−ε)n via new algorithm","Improving on 2n/3: near 3/4 transversals in equi-n arrays","Polynomial-time greedy insertion finds large transversals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic algorithm finds transversals of size (1−β/4−ε)n","Equi-n squares get transversals of size (3/4−ε)n via new algorithm","Improving on 2n/3: near 3/4 transversals in equi-n arrays","Polynomial-time greedy insertion finds large transversals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000931,"raw_usage":{"total_tokens":3936,"prompt_tokens":846,"completion_tokens":3090,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":3000}},"tokens_in":462,"tokens_out":3090,"duration_ms":23228,"temperature":1.0,"reasoning_tokens":3000,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:16:22.002144+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Stein's conjecture that every equi-n square has a transversal of size n−1 is the motivating open problem; the paper aims to save a weakened version."},{"cited_title":"Pokrovskiy and B","cited_arxiv_id":null,"evidence_quote":"Pokrovskiy and Sudakov's counterexample shows Stein's conjecture is false, motivating the search for approximate transversals."},{"cited_title":"Aharoni, E","cited_arxiv_id":null,"evidence_quote":"Aharoni, Berger, Kotlar, and Ziv used topological methods to prove existence of transversals of size 2n/3 in equi-n squares; the new Theorem 1.4 improves this existential bound."},{"cited_title":"Erdős and J","cited_arxiv_id":null,"evidence_quote":"Erdős and Spencer introduced β-bounded squares and the lopsided local lemma for full transversals, setting the stage for this problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Harris's new bounds for the Moser–Tardos distribution give an algorithmic guarantee that Theorem 1.5 improves whenever β ≥ 0.14."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Harris and Srinivasan's algorithmic work on the Moser–Tardos distribution for large transversals is another previous bound that the new result outperforms in the stated regime."}],"review_version":1}