Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
Abstract
There is a natural connection between the SOS rank problem for bi-quadratic forms and the Zarankiewicz extremal problem for C4-free bipartite graphs. The classical Zarankiewicz number z(m,n) controls the bipartite skeleton associated with monomial squares. Allowing two cells to form a single bilinear square leads to augmented Zarankiewicz configurations and the second-order Zarankiewicz number z2(m,n). Unlike zRL and zSL, defined through recursive sufficient conditions, z2 maximizes over all irreducible displayed SOS decompositions without imposing (RW 3+). Hence, to prove z2(m,n)<=R, one must prove that every simple limited configuration with more displayed squares is reducible; failure of a sufficient condition cannot serve as a counterargument. We prove z2(4,4)=10, z2(7,4)=19, z2(8,4)=21, z2(5,5)=17, and obtain z2=zSL=zRL in all these cases. The extremal irreducible 6x4 configurations with 16 displayed squares form a single isomorphism class under row and column relabeling, whereas the extremal irreducible 7x4 configurations with 19 displayed squares form exactly three isomorphism classes. The four-column results form a structural chain: classify lower-order extremal configurations first, then use hereditary irreducibility under deletion of complete squares to constrain the next order. Finite exhaustive steps use candidate pruning, a necessary compatibility graph, clique enumeration, and orbit reduction, with a verifiable reducibility or irreducibility proof for each remaining orbit. For 5x5, there are two ordinary extremal skeletons; finite exclusion leaves only two highly symmetric 18-square candidates. They define the same ten-square polynomial, which admits an explicit nine-square representation, yielding the upper bound for z2(5,5).
Related
- New Bounds for Limited Zarankiewicz Numbers from K5t Blocks
- 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{xu2026exact,
title = {{Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers}},
author = {Yi Xu and Xihong Yan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18429},
eprint = {2609.18429},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18429},
}
RIS
TY - UNPB
TI - Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
AU - Yi Xu
AU - Xihong Yan
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18429
UR - https://arxiv.org/abs/2609.18429
AB - There is a natural connection between the SOS rank problem for bi-quadratic forms and the Zarankiewicz extremal problem for C4-free bipartite graphs. The classical Zarankiewicz number z(m,n) controls the bipartite skeleton associated with monomial squares. Allowing two cells to form a single bilinear square leads to augmented Zarankiewicz configurations and the second-order Zarankiewicz number z2(m,n). Unlike zRL and zSL, defined through recursive sufficient conditions, z2 maximizes over all irreducible displayed SOS decompositions without imposing (RW 3+). Hence, to prove z2(m,n)<=R, one must prove that every simple limited configuration with more displayed squares is reducible; failure of a sufficient condition cannot serve as a counterargument. We prove z2(4,4)=10, z2(7,4)=19, z2(8,4)=21, z2(5,5)=17, and obtain z2=zSL=zRL in all these cases. The extremal irreducible 6x4 configurations with 16 displayed squares form a single isomorphism class under row and column relabeling, whereas the extremal irreducible 7x4 configurations with 19 displayed squares form exactly three isomorphism classes. The four-column results form a structural chain: classify lower-order extremal configurations first, then use hereditary irreducibility under deletion of complete squares to constrain the next order. Finite exhaustive steps use candidate pruning, a necessary compatibility graph, clique enumeration, and orbit reduction, with a verifiable reducibility or irreducibility proof for each remaining orbit. For 5x5, there are two ordinary extremal skeletons; finite exclusion leaves only two highly symmetric 18-square candidates. They define the same ten-square polynomial, which admits an explicit nine-square representation, yielding the upper bound for z2(5,5).
ER -