REVIEW 2 major objections 3 minor 6 references
Most binary matrices have no small defining set
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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})$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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})$.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Section 3, Theorem 7] 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.
- [Abstract and Theorem 1] 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.
minor comments (3)
- [Abstract] 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.
- [Equation (2)] 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.
- [Throughout] 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.
Circularity Check
No circularity: the derivation rests on external theorems; the identified issue is a hypothesis-verification gap, not a circular reduction.
full rationale
I walked the derivation chain of Theorem 1. The argument reduces the existence of small defining sets to the Cavenagh-Ramadurai characterization (Theorem 5, reference [3]) and to a concentration property (Theorem 9), which is proved by comparing the conditional probability in the binomial random graph model with the unconditional probability, using the external asymptotic enumeration formula of Canfield-Greenhill-McKay (Theorem 7, reference [1]) and Chernoff bounds (Theorem 8, reference [6]). None of the cited results is by the present authors, and none is introduced by fitting a parameter to the target data. The lower bound on P_lambda(E_{s,t}) in equation (2) is a direct application of the external enumeration estimate; even if that estimate's hypotheses are not restated completely (the undefined constant A in Theorem 7 and the unused inequality in Theorem 1), that is a rigor/completeness issue, not circularity. No step defines the target quantity in terms of itself, no fitted quantity is renamed as a prediction, and no load-bearing claim is supported only by a self-citation. Therefore no significant circularity is present.
Assumptions & free parameters
assumptions (5)
- domain assumption Theorem 5 of [3]: D is a defining set for M iff M\D can be row- and column-permuted into good form, meaning a South-East walk has only zeros or empties above and only ones or empties below.
- domain assumption Theorem 7 of [1] (Canfield, Greenhill, McKay): asymptotic enumeration of dense bipartite graphs with given degree sequence, N(s,t) = binom(mn,λmn)^{-1} ∏_i binom(n,s_i) ∏_j binom(m,t_j) exp(-O((mn)^{2ε})), valid under the hypotheses of Theorem 1.
- domain assumption Cavenagh's theorem (cited as [2] and [4]): the complement of a critical set is a defining set.
- standard math Chernoff concentration bounds for sums of independent Bernoulli random variables (Theorem 8).
- standard math Stirling's approximation applied to binomial coefficients, with error terms that are absorbed into O(mn^{2ε}+nm^{2ε}); this includes dropping the factor for the event that the edge count is exactly λmn in the binomial model, which is O(m^{-1/2}) and hence absorbs into the O(mn^{2ε}) error.
Cite this review
Pith. "Pith review of Most binary matrices have no small defining set." pith.science (2026). https://pith.science/paper/5OZ7KHDX
@misc{pith2026190801267,
author = {Pith},
title = {Pith review of: Most binary matrices have no small defining set},
year = {2026},
howpublished = {\url{https://pith.science/paper/5OZ7KHDX}},
note = {Machine review of arXiv:1908.01267}
}
abstract
Consider a matrix $M$ chosen uniformly at random from a class of $m \times n$ matrices of zeros and ones with prescribed row and column sums. A partially filled matrix $D$ is a $\mathit{defining}$ $\mathit{set}$ for $M$ if $M$ is the unique member of its class that contains the entries in $D$. The $\mathit{size}$ of a defining set is the number of filled entries. A $\mathit{critical}$ $\mathit{set}$ is a defining set for which the removal of any entry stops it being a defining set. For some small fixed $\epsilon>0$, we assume that $n\le m=o(n^{1+\epsilon})$, and that $\lambda\le1/2$, where $\lambda$ is the proportion of entries of $M$ that equal $1$. We also assume that the row sums of $M$ do not vary by more than $\mathcal{O}(n^{1/2+\epsilon})$, and that the column sums do not vary by more than $\mathcal{O}(m^{1/2+\epsilon})$. Under these assumptions we show that $M$ almost surely has no defining set of size less than $\lambda mn-\mathcal{O}(m^{7/4+\epsilon})$. It follows that $M$ almost surely has no critical set of size more than $(1-\lambda)mn+\mathcal{O}(m^{7/4+\epsilon})$. Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when $\lambda=1/2$ and $n=m=2^k$ for an integer $k$.
Reference graph
Works this paper leans on
-
[1]
E. R. Canfield, C. Greenhill and B. D. McKay, Asymptotic enumera tion of dense 0-1 matrices with specified line sums, J. Combin. Theory Ser. A , 115 (2008), 32–66
work page 2008
-
[2]
N. J. Cavenagh, Defining sets and critical sets in (0 , 1)-matrices, J. Combin. Designs , 21 (2013), 253–266
work page 2013
-
[3]
N. J. Cavenagh and R. Ramadurai, Constructing (0 , 1)-matrices with large minimal defining sets, Linear Alg. Appl. , 537 (2018), 38–47
work page 2018
-
[4]
N. J. Cavenagh and L. K. Wright, The maximum, spectrum and sup remum for critical set sizes in (0 , 1)-matrices, J. Combin. Designs , 27 (2019), 522–536
work page 2019
-
[5]
C. Greenhill, B. D. McKay and X. Wang, Asymptotic enumeration of sparse 0–1 ma- trices with irregular row and column sums, J. Combin. Theory Ser. A , 113 (2006), 291–324
work page 2006
-
[6]
M. Mitzenmacher and E. Upfal, Probability and computing – randomized algorithms and probabilistic analysis, Cambridge University Press, Cambridge UK, 2005, pp. 64–67. 7
work page 2005
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.