The Second-Order Augmented Zarankiewicz Number
Abstract
The second-order Zarankiewicz number z2(m,n) and the biquadratic sum-of-squares rank BSR(m,n) are related by the unconditional hierarchy BSR(m,n) ≥ z2(m,n) ≥ zSL(m,n) ≥ zRL(m,n) ≥ zwL(m,n) ≥ z(m,n). We introduce the \emph{second-order augmented Zarankiewicz number} z2A(m,n), obtained from z2(m,n) by deleting the requirement that the configuration be \emph{limited}, so that BSR(m,n) ≥ z2A(m,n) ≥ z2(m,n). Although the defining class is enlarged, z2A still obeys the universal cell bound of Löfberg and Qi, because that bound uses only the C4-freeness of the one-edge graph. We prove BSR(4,4) ≥ z2A(4,4) = 11 > 10 = z2(4,4) = zRL(4,4), the first recorded separation between the second-order number and its augmented variant. This result also gives a better lower bound for BSR(4,4). The lower bound is witnessed by an explicit non-limited 4×4 configuration of displayed length $11$ whose recursive-line closure satisfies (RW3+); the matching upper bound excludes $12$ by the universal cell bound together with an exact finite classification of the $161$ twelve-square configurations, and z2(4,4)=zRL(4,4)=10 is the exact value of Xu and Yan.
Related
- Second Order Zarankiewicz Number
- Asymptotic equivalence and exact values for second-order Zarankiewicz numbers
- Overtake and the recursive-line equality for second-order Zarankiewicz numbers
- Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families
- Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
BibTeX
@misc{qi2026secondorder,
title = {{The Second-Order Augmented Zarankiewicz Number}},
author = {Liqun Qi and Chunfeng Cui},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04448},
eprint = {2610.04448},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04448},
}
RIS
TY - UNPB
TI - The Second-Order Augmented Zarankiewicz Number
AU - Liqun Qi
AU - Chunfeng Cui
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04448
UR - https://arxiv.org/abs/2610.04448
AB - The second-order Zarankiewicz number z_2(m,n) and the biquadratic sum-of-squares rank BSR(m,n) are related by the unconditional hierarchy BSR(m,n) ≥ z_2(m,n) ≥ z_SL(m,n) ≥ z_RL(m,n) ≥ z_wL(m,n) ≥ z(m,n). We introduce the \emph{second-order augmented Zarankiewicz number} z_2A(m,n), obtained from z_2(m,n) by deleting the requirement that the configuration be \emph{limited}, so that BSR(m,n) ≥ z_2A(m,n) ≥ z_2(m,n). Although the defining class is enlarged, z_2A still obeys the universal cell bound of Löfberg and Qi, because that bound uses only the C_4-freeness of the one-edge graph. We prove BSR(4,4) ≥ z_2A(4,4) = 11 > 10 = z_2(4,4) = z_RL(4,4), the first recorded separation between the second-order number and its augmented variant. This result also gives a better lower bound for BSR(4,4). The lower bound is witnessed by an explicit non-limited 4×4 configuration of displayed length $11$ whose recursive-line closure satisfies (RW3^+); the matching upper bound excludes $12$ by the universal cell bound together with an exact finite classification of the $161$ twelve-square configurations, and z_2(4,4)=z_RL(4,4)=10 is the exact value of Xu and Yan.
ER -