REVIEW 2 major objections 3 minor 26 references
A congruence obstruction to Roman's bound for Zarankiewicz numbers
T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read A congruence argument proves Roman's bound is never tight throughout a large interval of Zarankiewicz parameters below the design threshold.
desk verdict Real improvement over Roman's bound with a sound central proof; one concrete side-claim error in Theorem D(3) needs repair before acceptance. 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 load-bearing object is the modulus $d=\gcd(s,\binom{s+1}{2})$, which equals $s$ for odd $s$ and $s/2$ for even $s$. It is the largest modulus that cannot tell a column of size $s+1$ apart from a column of size $s+2$: a point of the first lies in $s$ of its $s$-subsets, a point of the second in $\binom{s+1}{2}$ of them, and $d$ divides both. On any profile that meets the bound, the local slack $\rho_x$ (the unused coverage at point $x$, summed over all $s$-sets through $x$) is forced to the single residue $\mu\equiv \lambda\binom{m-1}{s-1}\pmod d$ for every $x$ not in the exceptional column. The global identity $\sum_x \rho_x=sD$, together with $0\le \rho_x\le D$ and the fact that non-negative integers in one residue class are at least that residue, yields the contradiction. Two auxiliary functions carry the proof: the slack $\sigma(r)$, which measures how much leftover coverage the budget allows when $c=qs+r$, and the penalty $p(v)$, which measures how far a column of size $v$ overspends relative to the line through the two efficient sizes; together they classify the only profiles that could attain the bound.
What would settle it
Run an exact computation at one covered instance: for $s=4$, $t=2$, $m=28$, determine $z(28,n;4,2)$ for each $n$ from $1365$ to $4094$; the theorem predicts every value is at most $\mathrm{Rom}-1$, so a single value equal to $\mathrm{Rom}$ refutes Theorem B. The known small case $s=3$, $t=3$, $m=6$, $n=9$, where Roman's bound is attained and the hypotheses fail, serves as a control showing the arithmetic conditions are doing real work.
Extended reading notes
Core claim
The central claim is Theorem B: for $s\ge 3$, admissible $m$, and $n=T-c$ with $1\le c\le sT/(s+2)$, if either $1\le \sigma(r)<d$ and $m\mu\ne s\sigma(r)$, or $\mu\ne 0$ and $m\mu>s\sigma(r)$, then no matrix attains Roman's bound; $z(m,T-c;s,t)\le \mathrm{Rom}(m,T-c)-1$. Theorem A first identifies Roman's bound in this whole range with the counting bound $(s+1)(T-c)+\lfloor 2c/s\rfloor$, so the bound is exactly what the budget inequality and convexity give, and any improvement must come from a non-linear obstruction. The proof's core is the rigidity classification of extremal profiles: all but at most one column have size $s+1$ or $s+2$, and the leftover coverage $\rho_x$ at each point $x$ satisfies $\rho_x\equiv \mu \pmod d$, with $d$ and $\mu$ fixed by the parameters. Summing the local slacks over the $m$ points contradicts the total slack allowed by the profile. Where an $s$-$\!(m,s+1,t-1)$ design exists and $c=(s+1)/2$, deleting $c$ blocks from the design gives the matching construction, so the upper bound is exact: $z=(s+1)(T-c)$.
Load-bearing premise
The argument depends on the rigidity classification that any matrix attaining Roman's bound must have all but at most one column of size $s+1$ or $s+2$; if a more varied column-size profile could attain the counting bound, the congruence obstruction would not apply.
Editorial extensions
If this is right
- For every admissible $m$ with $\mu\ne 0$ and $m>s\sigma_{\max}/\mu$, Roman's bound fails at every $n$ with $2T/(s+2)\le n<T$, an interval of length $\Theta(m^s)$ rather than finitely many exceptional points.
- For odd $s$, the residue-class alternative supplies failures at all $c\equiv (s+1)/2\pmod s$ in the range, and this is exactly the situation in which an $s$-$\!(m,s+1,t-1)$ design exists, where the classical design argument is silent.
- For $s=4$, $t=2$, $m=28$, the second alternative covers all $2730$ values of $n$ between $1365$ and $4094$, giving the first complete non-attainment interval for an even $s$.
- The linear relaxation over all subset variables collapses under symmetrisation to the counting bound, so throughout the range Roman's bound, the counting bound, and that relaxation have the same optimum; any improvement, including Theorem B itself, is an integrality obstruction.
- At the parameters of the exact-value theorem, the refined linear program of Section 8 still returns Roman's bound, so the one-unit deficit there is invisible to that program.
Reading between the lines
- Iterating the local-slack congruence at pairs or triples of points, rather than single points, is a natural next step; it would constrain the joint distribution of the $\rho_x$ and might cover the currently silent cases where $\mu=0$, such as $s=4$, $t=3$.
- The proof produces a deficit of exactly one, but exact small values already show deficits of two; if the true deficit grows with $c$ near the upper endpoint, a new mechanism is needed, and the collapse of the subset relaxation suggests that mechanism will be integrality rather than a stronger linear bound.
- The matching construction in the exact-value theorem, deleting blocks from a design, suggests a general design-minus-$c$-blocks-plus-enlargements construction; if such a construction exists, exact values would follow on an entire arithmetic progression of $n$, not just at the smallest $c$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Zarankiewicz numbers z(m,n;s,t) and the regime just below the design threshold T = (t-1) C(m,s)/(s+1). Theorem A shows that in the interval n = T-c with 1 <= c <= sT/(s+2), Roman's 1975 bound coincides exactly with the elementary counting bound (s+1)(T-c) + floor(2c/s), so it contains no information beyond the budget inequality and convexity. Theorem B then proves that, under a congruence obstruction on the local coverage slacks, Roman's bound is never attained in this range: z(m,T-c;s,t) <= Rom(m,T-c) - 1, provided either hypothesis (7) or (8) holds. Theorem C gives the exact value z = (s+1)(T-c) = Rom - 1 at c = (s+1)/2 when an s-(m,s+1,t-1) design exists. Theorem D analyses the slack function and the availability of the two hypotheses. The final sections relate the obstruction to linear programming: the full subset relaxation collapses to the counting bound (Proposition 8.1), while the refined Davies-Gill-Horsley program is analysed exactly for s=t=3 in Proposition 8.5.
Significance. If the main claims stand, this is a substantial advance on a problem that has been dominated by Roman's bound for fifty years. The core argument is elementary and self-contained: it derives non-attainment from double counting, a rigidity classification of extremal column profiles, and a residue computation, with no fitted parameters. Theorem B gives a closed-form improvement valid on an interval of length Theta(m^s), and Theorem C provides genuinely exact values at a specific deficiency below the threshold. The linear-programming analysis (Proposition 8.1 and Proposition 8.5) is a useful clarification of why the obstruction is integrality-based rather than visible to the subset relaxation. The main weakness is a false nonemptiness claim in the proof of Theorem D(3), which is used to advertise the generality of hypothesis (8); this does not appear to invalidate Theorem B, but it needs a substantive repair.
major comments (2)
- [Section 3, proof of Theorem D(3)] The proof asserts that the congruence class of admissible m with m ≡ s (mod (s-1)!d) is nonempty because 'admissibility is itself a congruence condition on m; one intersects the two.' This is false. For s = 5, t = 2 (so lambda = 1), we have d = 5 and (s-1)!d = 120. For every m ≡ 5 (mod 120), m-1 ≡ 4 (mod 8) and m-3 ≡ 2 (mod 8), so the numerator of C(m,5) has 2-adic valuation exactly 3; this cancels the factor 2^3 in the denominator 120, making C(m,5) odd. Hence 6 does not divide C(m,5), T = C(m,5)/6 is not an integer, and no such m is admissible. The intersection of the residue class with the admissible set is therefore empty for these parameters. The stated nonemptiness does not follow, and the proof that Hypothesis (8) is available for arbitrary s with d not dividing lambda is incomplete. This does not invalidate Theorem B itself, since admissible m with mu != 0 exist elsewhere (for example m = 10 for s = 5, lambda = 1), but the written justification in Theorem D(3) must be repaired, either by an explicit existence argument or by weakening the claim.
- [Remark 5.3] The sentence 'Hypothesis (8) cannot hold there' at the endpoint c = sT/(s+2) is too strong. If an s-(m,s+2,lambda) design exists then Lemma 4.2 forces mu = 0, so (8) fails; but if no such design exists, mu may be nonzero and (8) may well hold at that endpoint. This does not create a conflict with Theorem B, because in the latter case Roman's bound is already not attained by the classical design criterion, but the wording is inaccurate and should be replaced by a conditional statement.
minor comments (3)
- [Section 3, proof of Theorem D(3)] The phrase 'admissibility is itself a congruence condition on m' conflates a union of residue classes with a single residue class; the intersection of two such conditions can be empty, as the counterexample in the major comment shows. The exposition would be clearer if the existence of admissible m in the relevant class were not asserted without proof.
- [Proposition 8.5] The 'if and only if' statement concerns feasibility of the point x* for the Davies-Gill-Horsley program, not equality of the program's optimal value with Rom. The distinction is already implicit in Remark 8.7 (where x* is infeasible yet floor E = Rom), but it could be stated explicitly at the proposition to prevent misreading.
- [Throughout] The manuscript contains numerous OCR/formatting artifacts in the provided text, such as garbled subscripts and broken equations, which should be corrected in the final version.
Circularity Check
No significant circularity: Roman's bound, the rigidity classification, the congruence obstruction, and the LP comparison are each derived from independent counting identities rather than from the target result.
full rationale
The derivation chain is self-contained. Theorem A compares Roman's piecewise-linear expression (3) directly with the elementary counting bound (10) obtained from the budget inequality (1) and two-slope convexity (Lemma 2.1); no parameter is fitted to the conclusion. Lemma 3.2's rigidity classification follows from the penalty function (14) and the slack identity (15), with the exceptional-column restriction derived from the values of p(s), p(s-1), and p(s+3), not assumed as an ansatz. Lemma 4.1 is a double count of point-s-set incidences, and Theorem B combines these ingredients with hypotheses (7) and (8) purely as sufficient conditions; it never imports the non-attainment conclusion as an input. Theorem C uses external design-existence theorems only in the forward direction to supply a matching configuration, and Section 8's Proposition 8.1 is an explicit symmetrization proof that the subset relaxation equals the counting relaxation. There is no load-bearing self-citation and no renamed empirical pattern. The only flagged issue is a non-circular gap in the proof of Theorem D(3): the assertion that the admissible class m ≡ s (mod (s-1)!d) is nonempty by intersecting two congruence conditions is not justified and in fact fails for s=5, t=2, where every m ≡ 5 mod 120 has 6 ∤ C(m,5). This is a correctness or availability issue for one residue class, not a circular step; Theorem B remains valid for admissible m with μ ≠ 0, so the central results survive.
Assumptions & free parameters
assumptions (5)
- domain assumption T = λ C(m,s)/(s+1) is an integer (m is admissible).
- standard math Roman's inequality (3) is a valid external upper bound.
- domain assumption Existence of s-(m,s+1,t-1) designs for the parameters of Theorem C (Keevash; Glock, Kühn, Lo, Osthus; Hanani for s=3).
- standard math Convexity of the binomial coefficient function v maps to C(v,s).
- domain assumption Classical criterion: Roman's bound is attained at an integral Roman point iff the corresponding design exists.
Cite this review
Pith. "Pith review of A congruence obstruction to Roman's bound for Zarankiewicz numbers." pith.science (2026). https://pith.science/paper/ZXZOCTTG
@misc{pith2026260807607,
author = {Pith},
title = {Pith review of: A congruence obstruction to Roman's bound for Zarankiewicz numbers},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZXZOCTTG}},
note = {Machine review of arXiv:2608.07607}
}
read the original abstract
Let z(m,n;s,t) be the largest number of ones in an m x n zero-one matrix with no s x t all-ones submatrix. Roman's 1975 inequality remains the best general upper bound for s>=3, but it is not attained on a large part of the range just below the design threshold T=(t-1)C(m,s)/(s+1). The proof has two steps. First, for n=T-c with 1<=c<=sT/(s+2), Roman's bound equals the elementary counting bound (s+1)(T-c)+floor(2c/s), adding nothing beyond a budget inequality and convexity. Second, attainment forces all but at most one column to have size s+1 or s+2; each such column has a point lying in a number of s-sets divisible by d=gcd(s,C(s+1,2)), pinning the leftover coverage there to a single residue mu mod d, which a global count rules out. With r=c mod s and slack sigma(r) depending only on s, we prove z(m,T-c;s,t) <= Rom(m,T-c)-1 whenever 1<=sigma(r)<d and m*mu != s*sigma(r), or mu != 0 and m*mu > s*sigma(r). The first case is an odd-s phenomenon confined to one residue class, giving order-m^s values of n; the second needs mu != 0 but covers the whole interval once m exceeds a threshold depending only on s and mu. For s=4, t=2, m=28 it covers all 2730 values of n; when c=(s+1)/2 and an s-(m,s+1,t-1) design exists, z=(s+1)(T-c) exactly. Finally we relate the obstruction to linear programming: the relaxation over all 2^m subset variables collapses, under symmetrisation, to the counting bound, so no linear relaxation of the covering constraints alone can beat the bound of Chen, Horsley, and Mammoliti (arXiv:2310.12685, "Zarankiewicz numbers near the triple system threshold"). For the refined program of Davies, Gill, and Horsley, its optimum is still attained at the Roman vertex on an explicit sub-family, and we record where their program does better.
Reference graph
Works this paper leans on
-
[1]
New bounds for Zarankiewicz numbers via reinforced LLM evolutionary search, 2026
Jay Bhan, Nicole Nobili, and Patrick Langer. New bounds for Zarankiewicz numbers via reinforced LLM evolutionary search, 2026. Preprint; not peer reviewed
work page 2026
-
[2]
Exact values for unbalanced Zarankiewicz numbers
Guangzhou Chen, Daniel Horsley, and Adam Mammoliti. Exact values for some unbalanced Zarankiewicz num- bers.Journal of Graph Theory, 106(1):81–109, 2024. arXiv:2202.05507
work page Pith review arXiv 2024
-
[3]
Zarankiewicz numbers near the triple system threshold
Guangzhou Chen, Daniel Horsley, and Adam Mammoliti. Zarankiewicz numbers near the triple system threshold. Journal of Combinatorial Designs, 32(9):556–576, 2024. arXiv:2310.12685
work page Pith review arXiv 2024
-
[4]
Discrete Mathematics and its Applications
CharlesJ.ColbournandJeffreyH.Dinitz, editors.Hand- book of Combinatorial Designs. Discrete Mathematics and its Applications. Chapman and Hall/CRC, Boca Raton, 2nd edition, 2007
work page 2007
-
[5]
Alex F. Collins, Alexander W. N. Riasanovsky, John C. Wallace, and Stanisław P. Radziszowski. Zarankiewicz numbers and bipartite Ramsey numbers.Journal of Algorithms and Computation, 47(1):63–78, 2016
work page 2016
-
[6]
Some remarks on the Zarankiewicz problem
David Conlon. Some remarks on the Zarankiewicz problem.Mathematical Proceedings of the Cam- bridge Philosophical Society, 173(1):155–161, 2022. arXiv:2007.12816
work page Pith review arXiv 2022
-
[7]
Teilweise Lösung eines verallgemeinerten Problems von K
Karel Čulík. Teilweise Lösung eines verallgemeinerten Problems von K. Zarankiewicz.Annales Polonici Math- ematici, 3:165–168, 1956
work page 1956
-
[8]
Gábor Damásdi, Tamás Héger, and Tamás Szőnyi. The Zarankiewicz problem, cages, and geometries.Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 56(1):3–37, 2013
work page 2013
Show all 26 references
-
[9]
Improved upper bounds on Zarankiewicz numbers.Discrete Math- ematics, 349(5):114924, 2026
Sara Davies, Peter Gill, and Daniel Horsley. Improved upper bounds on Zarankiewicz numbers.Discrete Math- ematics, 349(5):114924, 2026. arXiv:2411.18842
2026
-
[10]
An upper bound on Zarankiewicz’ prob- lem.Combinatorics, Probability and Computing, 5(1):29– 33, 1996
Zoltán Füredi. An upper bound on Zarankiewicz’ prob- lem.Combinatorics, Probability and Computing, 5(1):29– 33, 1996
1996
-
[11]
The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F.Memoirs of the American Mathematical Society, 284(1406), 2023
Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Os- thus. The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F.Memoirs of the American Mathematical Society, 284(1406), 2023. arXiv:1611.06827
2023 arXiv
-
[12]
Henning, and Or- trud R
Wayne Goddard, Michael A. Henning, and Or- trud R. Oellermann. Bipartite Ramsey numbers and Zarankiewicznumbers.Discrete Mathematics, 219(1):85– 95, 2000
2000
-
[13]
Richard K. Guy. A many-facetted problem of Zarankiewicz. InThe Many Facets of Graph Theory, volume 110 ofLecture Notes in Mathematics, pages 129–
-
[14]
On quadruple systems.Canadian Journal of Mathematics, 12:145–157, 1960
Haim Hanani. On quadruple systems.Canadian Journal of Mathematics, 12:145–157, 1960
1960
-
[15]
A class of three-designs.Journal of Combinatorial Theory, Series A, 26(1):1–19, 1979
Haim Hanani. A class of three-designs.Journal of Combinatorial Theory, Series A, 26(1):1–19, 1979
1979
-
[16]
On a combinatorical problem
Carl Hyltén-Cavallius. On a combinatorical problem. Colloquium Mathematicum, 6(1):61–65, 1958
1958
-
[17]
Robert W. Irving. A bipartite Ramsey problem and the Zarankiewicz numbers.Glasgow Mathematical Journal, 19(1):13–26, 1978
1978
-
[18]
The existence of designs, 2014
Peter Keevash. The existence of designs, 2014. See also arXiv:2411.18291 for a shorter proof
2014 arXiv
-
[19]
Sós, and Pál Turán
Tamás Kővári, Vera T. Sós, and Pál Turán. On a problem of K. Zarankiewicz.Colloquium Mathematicum, 3:50–57, 1954
1954
-
[20]
A new result on the problem of Zarankiewicz.Journal of Combinatorial Theory, Series A, 31(2):126–130, 1981
Michael Mörs. A new result on the problem of Zarankiewicz.Journal of Combinatorial Theory, Series A, 31(2):126–130, 1981
1981
-
[21]
A contribution to the Zarankiewicz problem.Linear Algebra and its Applications, 432(6):1405–1411, 2010
Vladimir Nikiforov. A contribution to the Zarankiewicz problem.Linear Algebra and its Applications, 432(6):1405–1411, 2010
2010
-
[22]
Über ein Problem von K
István Reiman. Über ein Problem von K. Zarankiewicz. Acta Mathematica Academiae Scientiarum Hungaricae, 9:269–273, 1958
1958
-
[23]
A problem of Zarankiewicz.Journal of Combinatorial Theory, Series A, 18(2):187–198, 1975
Steven Roman. A problem of Zarankiewicz.Journal of Combinatorial Theory, Series A, 18(2):187–198, 1975
1975
-
[24]
An attack on Zarankiewicz’s problem through SAT solving, 2022
Jeremy Tan. An attack on Zarankiewicz’s problem through SAT solving, 2022. Version 2, 19 April 2022
2022
-
[25]
Problem p 101.Colloquium Mathematicum, 2:301, 1951
Kazimierz Zarankiewicz. Problem p 101.Colloquium Mathematicum, 2:301, 1951. 12
1951
-
[148]
Springer, Berlin, 1969
1969
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.