New Bounds for Limited Zarankiewicz Numbers from K5t Blocks
Abstract
The restricted augmented Zarankiewicz number zL(m,n) yields core combinatorial lower bounds for the maximal SOS rank of biquadratic forms. All previously known infinite admissible graph families rely on K4t incidence graphs, attaining an asymptotic relative gap limit of 1/4. This work develops a new infinite family built from K5t incidence bipartite graphs with ℤ5 cyclic labeling for block partitions. We construct valid nondegenerate intra-block and inter-block 2-edges, derive a quadratic closed-form lower bound of zL, and prove its relative gap converges asymptotically to 2/5. Full enumeration for t=1 verifies the exact value zL(10,5)=23. Under nondegenerate and generalized C4-free constraints, the ratio 2/5 is shown to be the maximal asymptotic ratio attainable under this block framework. Our results expand the library of extremal bipartite graphs and sharpen lower bounds for biquadratic SOS rank, with further open problems for general Kkt constructions outlined in closing.
Related
- Polychromatic blocks and explicit lower bounds for multicolour van der Waerden numbers
- A Twelve-Row Seed and a One-Row Extension for Five-Column Recursive-Line Zarankiewicz Numbers
- Density and separation for augmented Zarankiewicz numbers
- Asymptotic equivalence and exact values for second-order Zarankiewicz numbers
- Recursive-Line Zarankiewicz Numbers with Four Columns
BibTeX
@misc{liu2026bounds,
title = {{New Bounds for Limited Zarankiewicz Numbers from $K_5t$ Blocks}},
author = {Hanxin Liu and Yisheng Song},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07227},
eprint = {2609.07227},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07227},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - New Bounds for Limited Zarankiewicz Numbers from K_5t Blocks
AU - Hanxin Liu
AU - Yisheng Song
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07227
UR - https://arxiv.org/abs/2609.07227
AB - The restricted augmented Zarankiewicz number z_L(m,n) yields core combinatorial lower bounds for the maximal SOS rank of biquadratic forms. All previously known infinite admissible graph families rely on K_4t incidence graphs, attaining an asymptotic relative gap limit of 1/4. This work develops a new infinite family built from K_5t incidence bipartite graphs with ℤ_5 cyclic labeling for block partitions. We construct valid nondegenerate intra-block and inter-block 2-edges, derive a quadratic closed-form lower bound of z_L, and prove its relative gap converges asymptotically to 2/5. Full enumeration for t=1 verifies the exact value z_L(10,5)=23. Under nondegenerate and generalized C_4-free constraints, the ratio 2/5 is shown to be the maximal asymptotic ratio attainable under this block framework. Our results expand the library of extremal bipartite graphs and sharpen lower bounds for biquadratic SOS rank, with further open problems for general K_kt constructions outlined in closing.
ER -