{"id":"29343448-21ce-4f2f-af66-02dd6e1fb22b","arxiv_id":"1908.01267","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Almost all m×n binary matrices with prescribed row and column sums have no defining set smaller than λmn - O(m^{7/4+ε}), where λ≤1/2 is the density.","lead":"The paper proves that almost every binary matrix with fixed row and column sums has no small defining set: you must specify nearly all of its 1-entries before the matrix is uniquely determined. It matters because defining sets and critical sets are fundamental in combinatorics and design theory, and this is the first general almost-all result beyond a constructed square case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Enumeration estimate Theorem 7 is invoked without a self-contained statement: parameter A is undefined and the inequality in Theorem 1 is never shown to be a hypothesis of [1].","rationale":"I agree with the reader: the weakest point is the imported enumeration result. I checked the rest of the argument and did not find an internal contradiction that would invalidate Lemma 6 or the Chernoff comparison; the conditioning step has a minor notational/probabilistic slip in the equality for P_lambda(E), but the dropped factor is polynomial and is absorbed by the O in the exponent, so it does not change the asymptotic conclusion. The load-bearing uncertainty is whether Theorem 7, as stated, really follows from [1] for all sequences satisfying Theorem 1. The undefined A and the unexplained (1-2lambda)^2 inequality make this impossible for a reader to verify. Since the proof can likely be repaired by citing [1] precisely, CONDITIONAL remains the right verdict; acceptance should wait until Theorem 7 is restated with complete hypotheses and the inequality in Theorem 1 is either used or removed.","tokens_in":7632,"tokens_out":28987,"duration_ms":296709,"concrete_test":"Consult Canfield, Greenhill and McKay [1] and transcribe the exact theorem that Theorem 7 is meant to quote, with all symbols (in particular, A) and hypotheses stated explicitly. Then test the extremal parameter range allowed by Theorem 1, e.g., n=2^ell, m=2^{ceil(ell(1+epsilon/2))}, lambda=1/2-m^{-delta} chosen so the displayed inequality is tight, and check every hypothesis of [1] for this family, including any bound such as max_i |s_i-lambda n| <= A and any condition of the form Delta^2/(lambda(1-lambda)mn) -> 0. If a hypothesis fails, compute the resulting multiplicative error in N(s,t); if the lower bound on P_lambda(E_{s,t}) is no longer exp(-O(mn^{2epsilon}+nm^{2epsilon})), the ratio argument in Theorem 9 has a genuine gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central probabilistic step is the lower bound (2) on P_lambda(E_{s,t}), obtained by applying the asymptotic enumeration formula of [1] and dividing by binom(mn,lambda mn). This is load-bearing because Theorem 9 is proved entirely by comparing P_lambda(P) with this bound; if the true P_lambda(E_{s,t}) were materially smaller than claimed, the ratio would not tend to zero. The paper states this estimate as Theorem 7, but that theorem is not self-contained: it refers to a parameter A 'defined as in Theorem 1', and Theorem 1 contains no such parameter. It also does not state the hypotheses of the Canfield-Greenhill-McKay theorem that are being imported, and the proof never verifies that the degree sequences allowed by Theorem 1 satisfy them. In particular, Theorem 1 includes the inequality (1-2lambda)^2/(4lambda(1-lambda))(1+5m/6n+5n/6m) <= (log m)/3, but Theorem 9 never invokes it and the abstract omits it. If that inequality is a hypothesis of [1], its role must be made explicit; if it is not, its presence is unexplained. A secondary issue is that the displayed equality P_lambda(E_{s,t}) = N(s,t)/binom(mn,lambda mn) drops the probability factor lambda^{lambda mn}(1-lambda)^{(1-lambda)mn}; after Stirling this is only a polynomial factor, so I do not treat it as the main threat. The unresolved question is whether the imported formula applies to the full range of s,t admitted by Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies defining sets in random binary matrices with prescribed row and column sums. The main result, Theorem 1, asserts that for near-square dimensions with density λ bounded away from zero and at most 1/2, with row and column sums close to their averages, and with an auxiliary inequality involving λ and the aspect ratio, almost all matrices in A(s,t) have no defining set of size smaller than λmn − O(m^{7/4+ε}). The proof combines a deterministic lemma (Lemma 6) that converts a discrepancy bound on all submatrices into a lower bound on the size of any defining set, a characterization of defining sets by South-East walks (Theorem 5), and a probabilistic concentration argument (Theorem 9) for edge counts in a random bipartite graph with the given degree sequence. The probabilistic step conditions a binomial random graph on the event of having the prescribed degree sequence, and uses an asymptotic enumeration formula from Canfield–Greenhill–McKay (Theorem 7) to lower-bound the probability of that event.","tokens_in":7908,"tokens_out":36076,"duration_ms":328694,"significance":"If the hypotheses are read exactly as in Theorem 1, the result is a substantial generalization of the Cavenagh–Ramadurai construction to almost-all matrices with prescribed margins, and it has attractive corollaries on the maximum size of defining sets and on critical sets. The deterministic part is clean: Lemma 6 gives an explicit error term and is self-contained. The probabilistic argument is standard and plausible, and it is not circular, since the imported enumeration formula and defining-set characterization come from external sources. The main weakness is that the key enumeration estimate is not stated with its hypotheses, so the central probability lower bound is not verifiable as written. The paper would be acceptable after a careful restatement and verification of the imported theorem.","major_comments":[{"comment":"The enumeration estimate that supplies the lower bound (2) on P_λ(E_{s,t}) is not stated with its hypotheses. The sentence 'Let m, n, s, t, λ, A, and ε be defined as in Theorem 1' is impossible because Theorem 1 contains no parameter A. More importantly, the hypotheses of the external theorem from [1] are not listed, and the proof of Theorem 9 does not verify that the degree sequences admitted by Theorem 1 satisfy them. In particular, the inequality (1-2λ)^2/(4λ(1-λ))(1+5m/6n+5n/6m) ≤ (log m)/3 is assumed in Theorem 1 but is never invoked in the proof of Theorem 9; if it is part of the hypotheses of [1], its role must be made explicit, and if it is not, its presence is unexplained. Since (2) is the denominator in the ratio P_λ(P)/P_λ(E_{s,t}), this is a gap in the central argument.","section":"Section 3, Theorem 7"},{"comment":"The abstract states weaker hypotheses than Theorem 1, omitting 'λ bounded away from zero' and the auxiliary inequality (1-2λ)^2/(4λ(1-λ))(1+5m/6n+5n/6m) ≤ (log m)/3. The inequality is not an idle technicality: for λ bounded away from 1/2, it restricts m/n to be O(log m), which is much stronger than the abstract's m=o(n^{1+ε}). Thus the abstract's claim 'under these assumptions' is false for some parameter ranges covered by its stated assumptions. The authors should either include the missing hypotheses in the abstract or prove the theorem under the weaker assumptions stated there.","section":"Abstract and Theorem 1"}],"minor_comments":[{"comment":"The abstract says the result generalises Cavenagh and Ramadurai 'who examined the case when λ=1/2 and n=m=2^k', but their theorem concerns Λ^k_{2k}, so this should read 'n=m=2k' to match Corollary 2 and the cited result.","section":"Abstract"},{"comment":"The displayed equality P_λ(E_{s,t}) = N(s,t)/(mn choose λmn) omits the probability weight λ^{λmn}(1-λ)^{(1-λ)mn} that is needed when computing the probability of a fixed graph under G(n,m,λ). The missing factor is only polynomial after Stirling's approximation, so the conclusion is not endangered, but the equality should be corrected and the lower bound should be justified in that form.","section":"Equation (2)"},{"comment":"There are several typographical and rendering issues, such as 'parti ally' in the abstract, the use of '/greaterorequalslant' for ≥ in the proof of Lemma 6, and the undefined parameter A in Theorem 7. These should be cleaned up in revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The underlying approach is sound and the result is likely salvageable, but the central enumeration theorem is not stated accurately and the abstract overstates the hypotheses. I do not see a fundamental obstruction; the main work is to restate the quoted theorem from [1] with its exact hypotheses, verify that they are implied by Theorem 1, and align the abstract with the theorem. For these reasons I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something genuinely new: it takes the Cavenagh-Ramadurai construction of a single matrix with large minimal defining set and proves an almost-all statement for any class A(s,t) with regular margins, density bounded away from 0 and at most 1/2, and m,n near square. That is a real step beyond the power-of-two square case. The engine is a clean probabilistic argument: condition the binomial random graph on having degree sequence (s,t), split the bad event into large and small subarrays, and use Chernoff plus the Canfield-Greenhill-McKay enumeration formula. The structure is sensible and the core derivation in Lemma 6 is solid.\n\nThe soft spots are presentation gaps. Theorem 7 invokes a parameter A 'defined as in Theorem 1', but no such A exists in Theorem 1. More importantly, the enumeration estimate is imported without stating the hypotheses under which [1] applies. Theorem 1 includes the inequality (1-2λ)^2/(4λ(1-λ))(1+5m/6n+5n/6m) ≤ (log m)/3, yet the proof never invokes it and the abstract omits it. Either that inequality is a hypothesis for the enumeration formula, in which case its role needs to be explicit, or it is not needed, in which case its presence is confusing. The concern that the full range of s,t admitted by Theorem 1 may not satisfy the CGM conditions is legitimate; I cannot verify it from the paper as written. The dropped factor λ^{λmn}(1-λ)^{(1-λ)mn} in Pλ(E_{s,t}) is a Stirling-level correction, so I do not treat that as a threat.\n\nNone of this looks fatal. The theorem is likely true and the proof strategy is sound; the paper just needs to state the imported theorem cleanly and verify or adjust the hypotheses. The abstract should also align with Theorem 1.\n\nWho is this for? People working on defining sets, critical sets, and asymptotic enumeration of binary matrices. It deserves a serious referee. I would send it out, with a request that the referee check the application of the CGM formula carefully.","headline":"Genuine almost-all generalization of Cavenagh-Ramadurai with a sound probabilistic core; the main fix needed is a clean statement of the imported enumeration hypotheses.","tokens_in":8554,"tokens_out":1754,"would_cite":true,"duration_ms":16238,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B20","05C80","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A random binary matrix with nearly constant row and column sums, near-square dimensions, and density bounded away from 0 almost surely has no defining set smaller than $\\lambda mn - O(m^{7/4+\\epsilon})$, making the set of all ones…","keywords":["defining sets","critical sets","(0,1)-matrices","prescribed row and column sums","random bipartite graphs","asymptotic enumeration","probabilistic method","South-East walk"],"falsifier":"For a fixed small $\\epsilon$ and a specific balanced degree sequence, determine by computation whether every matrix in the class has a defining set of size at least $\\lambda mn-C\\cdot m^{7/4+\\epsilon}$ for the implicit constant $C$; a single smaller defining set would refute the claimed error term. More directly, enumerate $N(s,t)$ for degree sequences on the allowed boundary, for example with $|s_i-\\bar s|=n^{1/2+\\epsilon}$, and compare with the product-of-binomial estimate in Theorem 7: a ratio not close to 1 shows the conditioning step fails.","tokens_in":7369,"feed_emoji":"🎲","tokens_out":13522,"duration_ms":122449,"temperature":0.7,"pith_summary":"Defining sets are the smallest partially filled arrays that force a matrix once the row and column sums are known. The paper proves that for almost every sufficiently regular binary matrix, no such forcing set can be much smaller than the trivial choice consisting of all entries equal to 1. Under mild assumptions on the dimensions and on how far the row and column sums deviate from their averages, the minimum defining-set size is $\\lambda mn - O(m^{7/4+\\epsilon})$, where $\\lambda$ is the density of ones. The result also bounds the size of critical sets, and it upgrades an earlier special construction for square constant-sum matrices to a statement about almost all matrices in a broad family.","feed_headline":"Random binary matrices almost always need near-maximal defining sets","feed_subtitle":"The full set of ones is nearly optimal: the smallest defining set only misses it by O(m^(7/4+ε)).","key_machinery":"The proof rests on the South-East walk characterisation of defining sets: after permuting rows and columns, a matrix with a defining set removed is in good form exactly when a monotone path separates all filled zeros above the path from all filled ones below it. Lemma 6 turns this into a counting argument: whenever every subarray has number of ones within $\\Delta(m,n)$ of its expectation, every defining set has size at least $\\lambda mn-O(m^{7/4}+m^{1/4}\\Delta(m,n))$. The main probabilistic work, Theorem 9, shows that for almost all matrices with the prescribed degree sequence every subarray deviates from its expected number of ones by $O(mn^{1/2+\\epsilon}+nm^{1/2+\\epsilon})$. This is proved by conditioning the independent-edge random bipartite graph with edge probability $\\lambda$ on having the target degree sequence, using the asymptotic enumeration formula from [1] to lower-bound the conditioning probability and using exponential tail bounds plus a union bound over all row and column subsets to upper-bound the deviation probability.","core_discovery":"Theorem 1 is the central claim. Fix a sufficiently small $\\epsilon>0$; let $n\\le m=o(n^{1+\\epsilon})$, let $s$ and $t$ be positive integer vectors with equal sums, and put $\\lambda=\\bar s/n=\\bar t/m\\le 1/2$, bounded away from zero, with $|s_i-\\bar s|=O(n^{1/2+\\epsilon})$ and $|t_j-\\bar t|=O(m^{1/2+\\epsilon})$ uniformly. If the auxiliary inequality $\\frac{(1-2\\lambda)^2}{4\\lambda(1-\\lambda)}(1+\\frac{5m}{6n}+\\frac{5n}{6m})\\le \\frac{\\log m}{3}$ holds, then almost all matrices in $A(s,t)$ have no defining set of size less than $\\lambda mn-O(m^{7/4+\\epsilon})$. Equivalently, $\\mathrm{sds}(M)=\\lambda mn-O(m^{7/4+\\epsilon})$ for almost all such matrices, since the full set of ones is always a defining set of size exactly $\\lambda mn$. It follows that $\\max\\mathrm{sds}(s,t)=\\lambda mn-O(m^{7/4+\\epsilon})$, and that almost no matrix in $A(s,t)$ has a critical set larger than $(1-\\lambda)mn+O(m^{7/4+\\epsilon})$.","pith_inferences":["Editorial inference: the restriction $\\lambda\\le 1/2$ is a notational convenience; exchanging zeros and ones would carry the same argument through for $\\lambda>1/2$ with $\\lambda$ replaced by $1-\\lambda$.","Editorial inference: the auxiliary inequality stated in Theorem 1 is never used in the proof; testing whether it is redundant, or whether it is actually needed for the enumeration formula's validity, would sharpen the boundary of the theorem.","Editorial inference: the proof strategy is transferable. Any random matrix model whose independent-edge version has a comparable degree-sequence probability and a comparable discrepancy bound should inherit the same defining-set lower bound for almost all of its members.","Editorial inference: the assumption that $\\lambda$ is bounded away from zero exists because the enumeration formula used here covers dense matrices; extending sparse-enumeration results to intermediate densities would likely remove that restriction."],"forward_implications":["For almost all matrices in $A(s,t)$, the size of the smallest defining set is exactly $\\lambda mn-O(m^{7/4+\\epsilon})$, because the all-ones defining set supplies the matching upper bound.","The maximum over $A(s,t)$ of the smallest defining-set size satisfies $\\max\\mathrm{sds}(s,t)=\\lambda mn-O(m^{7/4+\\epsilon})$ under the same hypotheses.","For every pair $m,n$ with $n\\le m=o(n^{1+\\epsilon})$, the extremal value over all binary matrices is $\\max\\mathrm{sds}(m,n)=mn/2-O(m^{7/4+\\epsilon})$.","Almost all matrices in $A(s,t)$ have no critical set of size more than $(1-\\lambda)mn+O(m^{7/4+\\epsilon})$, since the complement of a critical set is itself a defining set.","In the constant-sum square case $m=n=2^k$, almost all matrices in $\\Lambda^k_{2k}$ have no defining set smaller than $2k^2-O(k^{7/4+\\epsilon})$."],"supporting_citations":[{"why":"Supplies the asymptotic enumeration formula for bipartite graphs with prescribed degree sequences, the key estimate used to condition the random graph on its degree sequence.","marker":"[1]"},{"why":"Establishes that the complement of a critical set is a defining set, converting the lower bound on defining sets into the asserted critical-set bound.","marker":"[2]"},{"why":"Provides the South-East walk characterization of defining sets and the earlier square constant-sum result that this paper generalises.","marker":"[3]"},{"why":"Cited together with [2] for the behaviour of critical sets in (0,1)-matrices used in Corollary 4.","marker":"[4]"},{"why":"Provides the exponential tail bounds used to control subarray discrepancies over all pairs of row and column subsets.","marker":"[6]"}],"fun_headline_variants":["Almost all binary matrices need near-maximal defining sets","Binary matrices almost always require nearly full defining sets","Small defining sets are rare for random binary matrices","Defining sets for binary matrices are typically near-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the asymptotic enumeration formula quoted as Theorem 7 applies, with its stated error, to every degree sequence allowed by Theorem 1; the paper never restates the formula's exact hypotheses, and the additional inequality in Theorem 1 is never used in the proof, so the formula's range of validity is the point of collapse.","fun_headline_variants_meta":{"raw":{"variants":["Almost all binary matrices need near-maximal defining sets","Binary matrices almost always require nearly full defining sets","Small defining sets are rare for random binary matrices","Defining sets for binary matrices are typically near-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000404,"raw_usage":{"total_tokens":2202,"prompt_tokens":1144,"completion_tokens":1058,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":996}},"tokens_in":760,"tokens_out":1058,"duration_ms":10523,"temperature":1.0,"reasoning_tokens":996,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:21:30.740600+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed small $\\epsilon$ and a specific balanced degree sequence, determine by computation whether every matrix in the class has a defining set of size at least $\\lambda mn-C\\cdot m^{7/4+\\epsilon}$ for the implicit constant $C$; a single smaller defining set would refute the claimed error term. More directly, enumerate $N(s,t)$ for degree sequences on the allowed boundary, for example with $|s_i-\\bar s|=n^{1/2+\\epsilon}$, and compare with the product-of-binomial estimate in Theorem 7: a ratio not close to 1 shows the conditioning step fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the asymptotic enumeration formula for bipartite graphs with prescribed degree sequences, the key estimate used to condition the random graph on its degree sequence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that the complement of a critical set is a defining set, converting the lower bound on defining sets into the asserted critical-set bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the South-East walk characterization of defining sets and the earlier square constant-sum result that this paper generalises."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Cited together with [2] for the behaviour of critical sets in (0,1)-matrices used in Corollary 4."},{"cited_title":"Mitzenmacher and E","cited_arxiv_id":null,"evidence_quote":"Provides the exponential tail bounds used to control subarray discrepancies over all pairs of row and column subsets."}],"review_version":1}