A Computational Study of Limited Augmented Zarankiewicz Numbers in the Incidence-Graph Family of Complete Graphs

Gaohang Yu; Xu Yi

arxiv: 2605.29658 · v1 · pith:SSUQQASLnew · submitted 2026-05-28 · 🧮 math.CO

A Computational Study of Limited Augmented Zarankiewicz Numbers in the Incidence-Graph Family of Complete Graphs

Xu Yi , Gaohang Yu This is my paper

Pith reviewed 2026-06-29 06:39 UTC · model grok-4.3

classification 🧮 math.CO

keywords limited augmented Zarankiewicz numbersincidence graphscomplete graphsZarankiewicz problembipartite saturation numbersinteger linear programmingadmissible familiesextremal graph theory

0 comments

The pith

Limited augmented Zarankiewicz numbers equal 14 for (6,4) and 26 for (10,5) exactly in incidence graphs of complete graphs, with lower bounds 43, 64 and 88 for larger pairs.

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

The paper computes new values for limited augmented Zarankiewicz numbers z_L in the incidence graphs of complete graphs K_{q+1}. It combines exact 0-1 integer linear programming on the smallest instances with a constructive search procedure that is then checked for admissibility on larger instances. This yields the exact determinations z_L(6,4)=14 and z_L(10,5)=26 together with the lower bounds z_L(15,6)≥43, z_L(21,7)≥64 and z_L(28,8)≥88 arising from verified admissible families. These results improve the ordinary Zarankiewicz numbers and therefore raise the known lower bounds on the bipartite saturation numbers BSR(m,n) inside the same family. A reader would care because the numbers quantify the largest admissible edge sets that avoid certain forbidden configurations in this concrete bipartite setting.

Core claim

By exact 0-1 ILP computation on the smallest cases and by constructive search followed by exact admissibility verification on the larger cases, the limited augmented Zarankiewicz numbers in the incidence-graph family satisfy z_L(6,4)=14, z_L(10,5)=26, z_L(15,6)≥43, z_L(21,7)≥64 and z_L(28,8)≥88; the first two values are exact while the three lower bounds are witnessed by explicitly verified admissible families containing |E2|=13, |E2|=22 and |E2|=32 edges respectively, and all five quantities improve the corresponding classical Zarankiewicz numbers.

What carries the argument

The limited augmented Zarankiewicz number z_L(m,n) in the incidence graph of K_{q+1}, obtained by maximising a second edge set E2 subject to an admissibility condition that is verified exactly after search or ILP.

If this is right

Each reported value improves the corresponding classical Zarankiewicz number.
The results strengthen the available lower bounds for BSR(m,n) inside the incidence-graph family.
The three lower bounds rest on explicitly constructed admissible families with 13, 22 and 32 edges in E2.
The families used for the lower bounds are nondegenerate.

Where Pith is reading between the lines

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

Similar search-plus-verification pipelines could be applied to obtain bounds at still larger parameters in the same family.
The gap between the new lower bounds and any matching upper bounds may guide future exact computations or theoretical arguments.
Structural features of the admissible families might suggest patterns that extend beyond the incidence-graph setting.

Load-bearing premise

The search procedure followed by exact verification really produces admissible and nondegenerate families that attain the stated sizes.

What would settle it

An explicit admissible family larger than 14 edges for the (6,4) case, or a proof that no admissible family of size 14 exists.

read the original abstract

Let $G_1$ denote the incidence graph of the complete graph $K_{q+1}$. We study limited augmented Zarankiewicz numbers in this family by combining exact 0--1 ILP computations for the smallest cases with a constructive search procedure followed by exact admissibility verification in the larger cases considered here. We obtain \[ z_L(6,4)=14,\qquad z_L(10,5)=26,\qquad z_L(15,6)\ge 43,\qquad z_L(21,7)\ge 64,\qquad z_L(28,8)\ge 88. \] The first two values are exact. The three lower bounds arise from explicitly verified admissible families with $|E_2|=13$, $|E_2|=22$, and $|E_2|=32$, respectively; the families used to obtain these bounds are nondegenerate in the sense of [8]. In each case, the resulting value improves the corresponding classical Zarankiewicz number and hence strengthens the available lower bounds for BSR(m,n) within this family.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper supplies two new exact values and three improved lower bounds for these limited augmented Zarankiewicz numbers in incidence graphs of complete graphs, obtained via ILP plus verified constructions.

read the letter

The main takeaway is that this paper pins down two exact values for the limited augmented Zarankiewicz number in the incidence graphs of complete graphs and supplies three new lower bounds that beat the ordinary Zarankiewicz numbers. Specifically, they report z_L(6,4) equals 14, z_L(10,5) equals 26, and then lower bounds of 43, 64, and 88 for the next sizes.

The approach mixes exact 0-1 integer linear programming on the smallest cases with a constructive search that finds admissible families for the larger ones, followed by exact verification of those families. They also confirm the families are nondegenerate according to the definition in reference [8]. This leads to improvements on the lower bounds for the bipartite subgraph Ramsey numbers BSR(m,n) within this particular family.

What the paper does well is stick to verifiable methods. The ILP solves are exact for small instances, and the lower bounds rest on explicit constructions rather than probabilistic arguments. Mentioning the verification steps and the nondegeneracy condition shows they are paying attention to the details that matter for these problems.

The soft spots are mostly practical. There is no accompanying code, no raw ILP models, and no listing of the actual edge sets used in the constructions. That means a reader has to take the authors' word on the verification, even though they describe it as exact. The gains themselves are incremental and limited to this one infinite family of graphs, so they are unlikely to change how people think about the general Zarankiewicz problem.

This work is really only of interest to specialists in extremal graph theory who are already looking at augmented or limited versions of these numbers in incidence graphs. A general reader in combinatorics would not get much from it.

I would recommend sending it to peer review. The claims are concrete and the methods are standard enough that a referee can evaluate them properly, perhaps by requesting the computational details if needed. It is not a major advance, but it adds solid data points to the literature.

Referee Report

1 major / 0 minor

Summary. The paper studies limited augmented Zarankiewicz numbers z_L(q+1,q) in the incidence-graph family of complete graphs K_{q+1}. It combines exact 0-1 ILP computations for the smallest cases with a constructive search procedure followed by exact admissibility verification for larger cases, obtaining the exact values z_L(6,4)=14 and z_L(10,5)=26 together with the lower bounds z_L(15,6)≥43, z_L(21,7)≥64 and z_L(28,8)≥88 arising from explicitly verified admissible families with |E2|=13, |E2|=22 and |E2|=32 respectively. These improve the corresponding classical Zarankiewicz numbers and thereby strengthen lower bounds for BSR(m,n) in this family.

Significance. If the reported ILP solutions and admissibility verifications are correct, the paper supplies improved explicit lower bounds on a specific infinite family of Zarankiewicz numbers that are directly relevant to bipartite subgraph Ramsey numbers. The methodological combination of exact ILP on small instances with constructive, exactly verified families on larger instances is standard and appropriate for this class of problems.

major comments (1)

[Abstract] Abstract: the central numerical claims rest on exact 0-1 ILP for the two smallest cases and on explicit constructions whose admissibility is stated to have been verified exactly, yet the manuscript supplies neither the ILP formulation, the solver output, the explicit families, nor the verification procedure. This absence is load-bearing for the reported exact values and lower bounds.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of the significance of our results and for the constructive comment on reproducibility. We address the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central numerical claims rest on exact 0-1 ILP for the two smallest cases and on explicit constructions whose admissibility is stated to have been verified exactly, yet the manuscript supplies neither the ILP formulation, the solver output, the explicit families, nor the verification procedure. This absence is load-bearing for the reported exact values and lower bounds.

Authors: We agree that the current manuscript does not include the ILP formulation, solver outputs, explicit families, or verification procedure. In the revised version we will add a dedicated section (or appendix) presenting the 0-1 ILP model, the solver outputs confirming the exact values z_L(6,4)=14 and z_L(10,5)=26, the explicit edge sets E2 for the three larger constructions, and the step-by-step admissibility verification procedure. This will make all reported results fully reproducible. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper reports numerical values obtained via external 0-1 ILP solvers for the exact cases z_L(6,4)=14 and z_L(10,5)=26, together with explicit constructions whose admissibility is verified exactly and stated to satisfy the nondegeneracy condition from reference [8]. No analytic derivation, parameter fitting, or self-referential step exists that reduces any claimed result to its own inputs by construction. The method relies on independent computational verification rather than any internal loop or imported uniqueness theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract contains no explicit free parameters, axioms, or invented entities; all content is computational output from standard ILP and search procedures.

pith-pipeline@v0.9.1-grok · 5721 in / 1057 out tokens · 22885 ms · 2026-06-29T06:39:18.037824+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages · 1 internal anchor

[1]

Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

B. Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

2004
[2]

Zarankiewicz numbers near the triple system threshold

G. Chen, D. Horsley and A. Mammoliti, “Zarankiewicz numbers near the triple system threshold”,Journal of Combinatorial Design32(2024) 556-576

2024
[3]

The Sum of squares rank of biquadratic forms and the Zarankiewicz number

C. Cui, L. Qi and Y. Xu, “The Sum of squares rank of biquadratic forms and the Zarankiewicz number”, February 2026, arXiv:2602.07844v2

work page arXiv 2026
[4]

A many-facetted problem of Zarankiewicz

R.K. Guy, “A many-facetted problem of Zarankiewicz”, in: G. Chartrand and S.F. Kapoor eds.,The Many Facets of Graph Theory, Springer, Berlin. 1969, pp. 129-141

1969
[5]

On a problem of K. Zarankiewicz

T. K˝ ov´ ari, V. S¨ os, and P. Tur´ an, “On a problem of K. Zarankiewicz”,Colloquium Mathematicum3(1954) 50-57

1954
[6]

Practical graph isomorphism

B. D. McKay, “Practical graph isomorphism”,Congressus Numerantium30(1981) 45-87

1981
[7]

Sum of squares decompositions and rank bounds for biquadratic forms

L. Qi, C. Cui and Y. Xu, “Sum of squares decompositions and rank bounds for biquadratic forms”, Mathematics14(2026) No. 635. 11

2026
[8]

Biquadratic SOS rank and augmented Zarankiewicz number

L. Qi, C. Cui and Y. Xu, “Biquadratic SOS rank and augmented Zarankiewicz number”,Mathematics14 (2026) No. 1552

2026
[9]

A General Lower Bound for the Limited Augmented Zarankiewicz Number based upon Complete Graphs

L. Qi, C. Cui and Y. Xu, “A general lower bound for the limited augmented Zarankiewicz number based upon complete graphs”, May 2026, arXiv:2604.04111v4

work page internal anchor Pith review Pith/arXiv arXiv 2026
[10]

¨Uber ein Problem von K. Zarankiewicz

I. Reiman, “ ¨Uber ein Problem von K. Zarankiewicz”,Acta Mathematica Academiae Scientiarum Hungar- icae9(1958) 269-273

1958
[11]

Narrowing the gap: SOS ranks of 4×3 biquadratic forms and a lower bound of 8

Y. Xu, C. Cui and L. Qi, “Narrowing the gap: SOS ranks of 4×3 biquadratic forms and a lower bound of 8”, February 2026, arXiv:2602.21570v1

work page arXiv 2026
[12]

Problem P 101

K. Zarankiewicz, “Problem P 101”,Colloquium Mathematicum2(1951) 301. 12

1951

[1] [1]

Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

B. Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

2004

[2] [2]

Zarankiewicz numbers near the triple system threshold

G. Chen, D. Horsley and A. Mammoliti, “Zarankiewicz numbers near the triple system threshold”,Journal of Combinatorial Design32(2024) 556-576

2024

[3] [3]

The Sum of squares rank of biquadratic forms and the Zarankiewicz number

C. Cui, L. Qi and Y. Xu, “The Sum of squares rank of biquadratic forms and the Zarankiewicz number”, February 2026, arXiv:2602.07844v2

work page arXiv 2026

[4] [4]

A many-facetted problem of Zarankiewicz

R.K. Guy, “A many-facetted problem of Zarankiewicz”, in: G. Chartrand and S.F. Kapoor eds.,The Many Facets of Graph Theory, Springer, Berlin. 1969, pp. 129-141

1969

[5] [5]

On a problem of K. Zarankiewicz

T. K˝ ov´ ari, V. S¨ os, and P. Tur´ an, “On a problem of K. Zarankiewicz”,Colloquium Mathematicum3(1954) 50-57

1954

[6] [6]

Practical graph isomorphism

B. D. McKay, “Practical graph isomorphism”,Congressus Numerantium30(1981) 45-87

1981

[7] [7]

Sum of squares decompositions and rank bounds for biquadratic forms

L. Qi, C. Cui and Y. Xu, “Sum of squares decompositions and rank bounds for biquadratic forms”, Mathematics14(2026) No. 635. 11

2026

[8] [8]

Biquadratic SOS rank and augmented Zarankiewicz number

L. Qi, C. Cui and Y. Xu, “Biquadratic SOS rank and augmented Zarankiewicz number”,Mathematics14 (2026) No. 1552

2026

[9] [9]

A General Lower Bound for the Limited Augmented Zarankiewicz Number based upon Complete Graphs

L. Qi, C. Cui and Y. Xu, “A general lower bound for the limited augmented Zarankiewicz number based upon complete graphs”, May 2026, arXiv:2604.04111v4

work page internal anchor Pith review Pith/arXiv arXiv 2026

[10] [10]

¨Uber ein Problem von K. Zarankiewicz

I. Reiman, “ ¨Uber ein Problem von K. Zarankiewicz”,Acta Mathematica Academiae Scientiarum Hungar- icae9(1958) 269-273

1958

[11] [11]

Narrowing the gap: SOS ranks of 4×3 biquadratic forms and a lower bound of 8

Y. Xu, C. Cui and L. Qi, “Narrowing the gap: SOS ranks of 4×3 biquadratic forms and a lower bound of 8”, February 2026, arXiv:2602.21570v1

work page arXiv 2026

[12] [12]

Problem P 101

K. Zarankiewicz, “Problem P 101”,Colloquium Mathematicum2(1951) 301. 12

1951