Pith. sign in

REVIEW 1 major objections 5 minor 27 references

The paper proves that no 43×43 zero-one matrix can contain 300 ones without containing an all-one 2×2 submatrix — so z(43;2) ≤ 299 — and constructs a 284-one example inside the projective plane of order 7, bracketing the true value in [284,

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-05 00:16 UTC pith:4N2SPQHB

load-bearing objection A repairable but serious flaw in a local-spectrum definition leaves the proof of z(43;2)<=299 incomplete as printed, though the underlying argument looks sound and the result is new. the 1 major comments →

arxiv 2608.01606 v1 pith:4N2SPQHB submitted 2026-08-03 math.CO cs.DM

An Improved Upper Bound on the Zarankiewicz Number z(43;2)

Ankan Sadhu This is my paper
classification math.CO cs.DM MSC 05C3505B1505B2505D05
keywords Zarankiewicz numberfour-cycle-free bipartite graphleavedegree profileprojective plane of order 6transversal design TD(6,6)mutually orthogonal Latin squaresReiman bound
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper attacks a classical extremal question: how many ones can a 43×43 zero-one matrix hold while avoiding an all-one 2×2 submatrix? The known bound caps this at 300, because a projective plane of order six (which would attain 301) provably does not exist. The paper proves the next cap: no 300-one configuration exists, so the maximum is at most 299. The mechanism is a pure counting argument on the leave — the pairs of columns never covered together — which reduces any hypothetical 300-edge graph to four candidate degree patterns, three of which collapse locally and the last of which forces a transversal design TD(6,6), equivalently four mutually orthogonal Latin squares of order six, contradicting Tarry's theorem. A separate explicit construction inside the projective plane of order seven gives a 284-one matrix, so the true value now lies in [284, 299]; the upper-bound proof is claimed to be checkable entirely by hand.

Core claim

The central claim is Theorem 1.1: there is no 43×43 zero–one matrix with 300 ones and no all-one 2×2 submatrix, hence z(43;2) ≤ 299, together with Proposition 1.2's explicit 284-edge construction in PG(2,7), giving 284 ≤ z(43;2) ≤ 299. The engine is the leave identity |E(L)| = (13 − Σ e_i²)/2, which fixes the size of the uncovered-column-pair graph in terms of the degree profile alone. For a hypothetical 300-edge graph this leaves exactly 27 admissible degree profiles per side; a local-spectrum compatibility test cuts these to four pairs; three are eliminated because a degree-six column would need to draw its rows from the six degree-eight rows, giving two columns that share six neighbours.

What carries the argument

The leave L: the graph on the column side whose edges are exactly the pairs of columns contained in no common row. Its size is forced by pure degree bookkeeping, |E(L)| = (13 − Σ e_i²)/2 where e_i = deg(row i) − 7; this identity turns a 300-edge configuration into one of 27 possible degree profiles per side. Two combinatorial tests then carry the argument. The local spectrum S(R) asks which column degrees can coexist with a row profile R while respecting the leave budget, and prunes the 27 profiles to four compatible pairs. For the surviving near-regular profile 7^42 6^1, the star lemma shows the leave is exactly a star centred at the unique degree-six column with the six neighbours of the u

Load-bearing premise

The load-bearing premise is an unstated tightening in Section 3: Definition 3.2's condition allows a column's leave degree up to the full total B(R), but Table 1's spectra are computed with leave degree capped at B(R)/2 (half the leave edges), and the elimination of profiles containing degree-4 or degree-5 columns in Lemma 3.3 depends on that tighter cap.

What would settle it

Recompute Table 1 using the inequality exactly as stated in Definition 3.2 (leave degree between 0 and B(R), not B(R)/2): for profile P24, equation (8) then admits a degree-6 column while the table lists S(P24) = {7}; if any profile containing a degree 4, 5, 9, or 10 also acquires an admissible spectrum entry, the four-pair conclusion of Lemma 3.3 breaks. The opposite test is immediate: a single verified 43×43 zero-one matrix with 300 ones and no all-one 2×2 submatrix would refute Theorem 1.1 outright.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • The true value z(43;2) is now pinned to the interval [284, 299], the tightest bracket recorded for this parameter; the previous recorded cap was 300, inherited from the nonexistence of a projective plane of order six.
  • The upper bound carries a hand-checkable certificate: every step of the profile enumeration, leave counting, and star-lemma argument is claimed verifiable without a computer, so the result can be audited line by line.
  • The obstruction at n=43 is shown to be the classical order-six obstruction itself: the last remaining candidate configuration would realize four mutually orthogonal Latin squares of order six, which Tarry's theorem forbids.
  • Proposition 7.1 generalizes the mechanism: for every q ≥ 2 with v = q²+q+1, a four-cycle-free graph whose two sides both have profile (q+1)^{v−1} q^1 forces a TD(q,q), hence q−2 mutually orthogonal Latin squares of order q; so wherever the required MOLS do not exist, such near-regular graphs cannot exist either.
  • The Section 6 construction is a finite certificate: two explicit deletion lists inside PG(2,7) determine the 284-edge graph completely, so the lower bound is independently checkable and can serve as the starting point for the open question of whether 299 is attained.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The leave-budget identity is generic: at any n = q²+q+1 where Reiman's bound is integral and no plane exists, the same identity fixes the leave size before any profile enumeration begins, so the bottleneck of the method is the size of the profile catalogue rather than the counting itself — q=10 (n=111) is out of manual reach for exactly that reason.
  • The constructed 284-edge graph has surviving degree sequence 8^1 7^24 6^18 on one side, far from the near-regular 7^42 6^1 profile the upper-bound argument targets; that asymmetry suggests the lower bound may be slack, and a better-chosen deletion pair in PG(2,7) could push the interval upward (the paper makes no optimality claim for 284).
  • Read together, the two halves suggest a dichotomy for C4-free graphs within one or two edges of the Reiman bound at q²+q+1: such graphs are either plane-like or net-like (TD-forcing), so exact values at these special n are ultimately governed by MOLS existence rather than by exhaustive search.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper studies the Zarankiewicz number z(43;2), the maximum number of ones in a 43x43 zero-one matrix with no all-one 2x2 submatrix. The main result (Theorem 1.1) is that z(43;2) <= 299, a one-edge improvement over the previously known bound 300 obtained from Reiman's inequality together with the nonexistence of a projective plane of order six. The proof is case-analytic: assuming a hypothetical 300-edge configuration, the row and column degree profiles are shown to lie among 27 possible profiles (Lemma 3.1); local leave-degree constraints reduce the compatible profile pairs to four (Lemma 3.3); three pairs are eliminated using the leave budget, and the remaining near-regular profile P26 forces a TD(6,6), equivalently four mutually orthogonal Latin squares of order six, contradicting Tarry's theorem. The paper also gives an explicit 284-edge construction inside PG(2,7), proving 284 <= z(43;2) <= 299 (Proposition 1.2). A separate proposition generalizes the TD-forcing mechanism to q > 6.

Significance. If the proof is valid, the result is a genuine improvement to the Zarankiewicz table at n=43, the first accessible order where the Reiman bound is not tight due to the nonexistence of a projective plane. The method is elementary and largely hand-checkable, uses no computer search for the upper bound, and gives an explicit construction for the lower bound. The reduction to a transversal design from a one-edge-deficient configuration is elegant and is formulated in a general way (Proposition 7.1), which may be of independent interest. The paper is carefully written, with reproducible scripts mentioned for the finite checks, and the use of Tarry's theorem is a standard external benchmark rather than a fitted or circular input.

major comments (1)
  1. [Definition 3.2, Eq. (8)] The local spectrum condition is stated as 0 <= 42 - sum u_j(a_j-1) <= B(R), with B(R) = 13 - sum e_i^2. This is not the correct upper bound for a leave degree. The leave graph L has |E(L)| = B(R)/2, so any vertex degree satisfies deg_L(y) <= B(R)/2. As written, Eq. (8) admits values that Table 1 deliberately excludes. For example, for P26 = 7^42 6^1, B=12, the choice of five 7-rows gives leave degree 12, so c=5 would be admitted, although a graph with six edges cannot have a vertex of degree 12; Table 1 correctly lists S(P26)={6,7}. Similarly for P24 = 8^1 7^41 5^1, B=8, a degree-6 column using the 8-row and five 7-rows has leave degree 5, so Eq. (8) admits c=6, while Table 1 lists S(P24)={7}. Since Lemma 3.3, Step 3 relies on the table's spectra to eliminate profiles containing degrees 4 and 5, the proof as printed is incomplete. The fix is local: replace B(R) in Eq. (8) by B(R)/2, and
minor comments (5)
  1. [Definition 3.2] After correcting the upper bound to B(R)/2, the sentence explaining the meaning of the definition should state explicitly that the leave has exactly B(R)/2 edges and hence no vertex can have degree larger than this.
  2. [Section 6, Step 4] The count of 52 common incidences between the deleted point set and the deleted line set is stated as a 'direct check' but no table or breakdown is provided. Since the two explicit lists are given, a short explanation of how to count these 52 incidences (or a supplementary table) would improve verifiability.
  3. [Table 1] The exponent notation in the Profile column is compressed and difficult to parse, especially without spacing separating degree from multiplicity. Using superscript notation (e.g., 7^42 6^1) in the table would greatly improve readability.
  4. [Lemma 3.1] The proof says 'enumerating admissible pairs' yields the stated counts, but the enumeration is not shown. This is acceptable for a finite check, but a brief description of the enumeration method (e.g., partitions of P and P+1 with parts at most 3 and square-sum at most 13) would make the proof more self-contained.
  5. [Section 7, Remark 7.2] The remark correctly notes the limitation that Proposition 7.1 does not automatically imply a two-edge improvement for general q. The phrasing is clear and appropriately cautious.

Circularity Check

0 steps flagged

No significant circularity: the derivation is self-contained and rests on independent external classical results.

full rationale

The paper's central derivation is a constraint proof. It assumes a 300-edge configuration, defines e_i by r_i = 7 + e_i, derives exact identities sum e_i = -1 and sum e_i^2 <= 13, enumerates 27 admissible degree profiles, defines local spectra via the leave identity, and then filters incompatible profile pairs. Each step follows from the printed equations and Table 1; there is no fitted parameter later called a prediction. The elimination of profile pairs uses only the local spectra and degree-set containments, and the surviving case constructs a TD(6,6) algebraically, which then contradicts Tarry's theorem. Tarry's result and Reiman's bound are external classical facts, not inputs tailored to the conclusion, and the paper does not rely on any self-citation. The lower bound is an explicit inclusion-exclusion construction inside PG(2,7) with the point and line deletion lists fully specified, so it is independently checkable rather than circular. The only concern a reviewer might raise is an internal consistency issue in Definition 3.2 (the bound B vs B/2 in the local spectrum condition) but that is a correctness flaw, not a circularity: the table is not derived from the theorem being proved. Since no claim reduces by definition, by fitted data, or by a self-citation chain, the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The central claim rests on standard external theorems plus one hidden assumption about the leave graph. No free parameters are fitted and no new entities are postulated. The hidden bound on leave degree is the only load-bearing premise that is not explicitly justified in the text.

axioms (4)
  • standard math Reiman's bound and the uniqueness of extremal configurations as incidence graphs of projective planes.
    Invoked in Section 1.1 to get z(43;2)<=301 and then z(43;2)<=300; relies on [19,15,26].
  • standard math Tarry's theorem: no pair of orthogonal Latin squares of order 6 exists.
    Used in the proof of Theorem 1.1 to contradict the TD(6,6) obtained in Lemma 5.4; cited as [24,22].
  • standard math A transversal design TD(k,n) is equivalent to k-2 mutually orthogonal Latin squares of order n.
    Used in Theorem 1.1 and Proposition 7.1; cited as [25,5].
  • domain assumption The leave graph L has exactly B(R)/2 edges, so no vertex of L can have degree exceeding B(R)/2.
    This unstated bound is needed to make Table 1 consistent with Definition 3.2; the written equation (8) only says deg_L(y) <= B(R), which is weaker and would admit extra local degrees, for example for profile P24.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of An Improved Upper Bound on the Zarankiewicz Number z(43;2)." pith.science (2026). https://pith.science/paper/4N2SPQHB

@misc{pith2026260801606,
  author       = {Pith},
  title        = {Pith review of: An Improved Upper Bound on the Zarankiewicz Number z(43;2)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4N2SPQHB}},
  note         = {Machine review of arXiv:2608.01606}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The Zarankiewicz number z(43;2) is the largest number of edges in a four-cycle-free bipartite graph with two parts of size 43. Reiman's bound gives z(43;2) <= 301, with equality only for the incidence graph of a projective plane of order six; no such plane exists, so z(43;2) <= 300. We prove z(43;2) <= 299. The argument is elementary and uses no computer search: a counting identity for the leave of the configuration shows that a hypothetical 300-edge graph admits one of exactly twenty-seven degree profiles per side, of which only four combinations are locally compatible. Three force two vertices to share six neighbours; the fourth forces a transversal design TD(6,6), hence four mutually orthogonal Latin squares of order six, contradicting Tarry's theorem. We also give an explicit 284-edge construction inside PG(2,7), so that 284 <= z(43;2) <= 299.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 2 internal anchors

  1. [1]

    R. J. R. Abel and F. E. Bennett. Improvements for lower bounds of mutually orthogonal Latin squares.arXiv preprint arXiv:2412.00480, 2024. A. Sadhu An improved bound onz(43; 2)10

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  2. [2]

    R. C. Bose, S. S. Shrikhande, and E. T. Parker. Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture.Canadian Journal of Mathematics, 12:189–203, 1960

    work page 1960

  3. [3]

    R. H. Bruck. Finite nets. II. Uniqueness and imbedding.Pacific Journal of Mathematics, 13(2):421–457, 1963

    work page 1963

  4. [4]

    R. H. Bruck and H. J. Ryser. The nonexistence of certain finite projective planes. Canadian Journal of Mathematics, 1(1):88–93, 1949

    work page 1949

  5. [5]

    C. J. Colbourn and J. H. Dinitz, editors.Handbook of Combinatorial Designs. Chapman and Hall/CRC, Boca Raton, 2 edition, 2006

    work page 2006

  6. [6]

    Zarankiewicz numbers and bipartite Ramsey numbers.Journal of Algorithms and Computation, 47:63–78, 2016

    A.F.Collins, A.W.N.Riasanovsky, J.C.Wallace, andS.P.Radziszowski. Zarankiewicz numbers and bipartite Ramsey numbers.Journal of Algorithms and Computation, 47:63–78, 2016

    work page 2016

  7. [7]

    Damásdi, T

    G. Damásdi, T. Héger, and T. Szőnyi. The Zarankiewicz problem, cages, and geometries. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 56:3–37, 2013

    work page 2013

  8. [8]

    Davies, P

    S. Davies, P. Gill, and D. Horsley. Improved upper bounds on Zarankiewicz numbers. Discrete Mathematics, 349:114924, 2026

    work page 2026

  9. [9]

    Dembowski.Finite Geometries

    P. Dembowski.Finite Geometries. Springer, Berlin, 1968

    work page 1968

  10. [10]

    Dybizbański, T

    J. Dybizbański, T. Dzido, and S. P. Radziszowski. On some Zarankiewicz numbers and bipartite Ramsey numbers for quadrilateral.Ars Combinatoria, 119:275–287, 2015

    work page 2015

  11. [11]

    L. Euler. Recherches sur une nouvelle espèce de quarrés magiques.Verhandelingen uitgegeven door het Zeeuwsch Genootschap der Wetenschappen te Vlissingen, 9:85–239, 1782

    work page

  12. [12]

    Füredi and M

    Z. Füredi and M. Simonovits. The history of degenerate (bipartite) extremal graph problems. InErdős Centennial, volume 25 ofBolyai Society Mathematical Studies, pages 169–264. Springer, Berlin, 2013

    work page 2013

  13. [13]

    Y. Gao. The largest pure partial planes of order 6 have size 25.Electronic Journal of Combinatorics, 25(4):#P4.10, 2018

    work page 2018

  14. [14]

    R. K. Guy. A many-facetted problem of Zarankiewicz. InThe Many Facets of Graph Theory, volume 110 ofLecture Notes in Mathematics, pages 129–148. Springer, Berlin, 1969

    work page 1969

  15. [15]

    Hyltén-Cavallius

    C. Hyltén-Cavallius. On a combinatorial problem.Colloquium Mathematicum, 6:59–65, 1958

    work page 1958

  16. [16]

    Kővári, V

    T. Kővári, V. T. Sós, and P. Turán. On a problem of K. Zarankiewicz.Colloquium Mathematicum, 3:50–57, 1954

    work page 1954

  17. [17]

    C. W. H. Lam. The search for a finite projective plane of order 10.American Mathematical Monthly, 98(4):305–318, 1991

    work page 1991

  18. [18]

    C. W. H. Lam, L. Thiel, and S. Swiercz. The non-existence of finite projective planes of order 10.Canadian Journal of Mathematics, 41(6):1117–1123, 1989. A. Sadhu An improved bound onz(43; 2)11

    work page 1989

  19. [19]

    I. Reiman. Über ein Problem von K. Zarankiewicz.Acta Mathematica Academiae Scientiarum Hungaricae, 9:269–273, 1958

    work page 1958

  20. [20]

    S. Roman. A problem of Zarankiewicz.Journal of Combinatorial Theory, Series A, 18(2):187–198, 1975

    work page 1975

  21. [21]

    J. Singer. A theorem in finite projective geometry and some applications to number theory.Transactions of the American Mathematical Society, 43(3):377–385, 1938

    work page 1938

  22. [22]

    D. R. Stinson. A short proof of the nonexistence of a pair of orthogonal Latin squares of order six.Journal of Combinatorial Theory, Series A, 36(3):373–376, 1984

    work page 1984

  23. [23]

    J. Tan. An attack on Zarankiewicz’s problem through SAT solving.arXiv preprint arXiv:2203.02283, 2022

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  24. [24]

    G. Tarry. Le problème des 36 officiers.Comptes Rendus de l’Association Française pour l’Avancement des Sciences, 29:170–203, 1900

    work page 1900

  25. [25]

    R. M. Wilson. Concerning the number of mutually orthogonal Latin squares.Discrete Mathematics, 9(2):181–198, 1974

    work page 1974

  26. [26]

    S. D. Winter, J. Schillewaert, and J. Verstraëte. An extremal characterization of projective planes.Electronic Journal of Combinatorics, 15:#R143, 2008

    work page 2008

  27. [27]

    Zarankiewicz

    K. Zarankiewicz. Problem P 101.Colloquium Mathematicum, 2:301, 1951

    work page 1951

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.