Overtake and the recursive-line equality for second-order Zarankiewicz numbers
Abstract
We study two questions about the second-order Zarankiewicz numbers. The first is the recursive-line equality z2(m,n)=zRL(m,n), known to hold in every computed case and conjectured in general. The second, here called \emph{overtake}, is the strict inequality z2A(m,n)>z2(m,n) between the second-order augmented number and the second-order number. Both are governed by the number Hlimited(m,n) of unoccupied cells in a limited extremal configuration. We prove that the first increase z2→ z2+1 already costs three unoccupied cells, forcing a unit of one-edge deficit, and the cell identity then bounds the excess z2A−z2 by ⌊(Hlimited−1)/2⌋. In particular, when the recursive-line hole count is at most two, no overtake occurs. We conjecture the sharp budget ⌊ Hlimited/3⌋ and that Hlimited≥5 is the threshold for an overtake. In the computed range n≤7, no overtake occurs at any order, the sole exception being the known case (4,4). The recursive-line equality z2=zRL is verified at every order in the range where both values are determined; the orders at which it remains unsettled are (12,4) and (14,4) at width four, (11,5) at width five, and (8,7) at width seven.
Related
- A Twelve-Row Seed and a One-Row Extension for Five-Column Recursive-Line Zarankiewicz Numbers
- Recursive-Line Zarankiewicz Numbers with Four Columns
- Asymptotic equivalence and exact values 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{ouyang2026overtake,
title = {{Overtake and the recursive-line equality for second-order Zarankiewicz numbers}},
author = {Chen Ouyang and Liqun Qi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22875},
eprint = {2610.22875},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22875},
}
RIS
TY - UNPB
TI - Overtake and the recursive-line equality for second-order Zarankiewicz numbers
AU - Chen Ouyang
AU - Liqun Qi
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22875
UR - https://arxiv.org/abs/2610.22875
AB - We study two questions about the second-order Zarankiewicz numbers. The first is the recursive-line equality z_2(m,n)=z_RL(m,n), known to hold in every computed case and conjectured in general. The second, here called \emph{overtake}, is the strict inequality z_2A(m,n)>z_2(m,n) between the second-order augmented number and the second-order number. Both are governed by the number H_limited(m,n) of unoccupied cells in a limited extremal configuration. We prove that the first increase z_2→ z_2+1 already costs three unoccupied cells, forcing a unit of one-edge deficit, and the cell identity then bounds the excess z_2A−z_2 by ⌊(H_limited−1)/2⌋. In particular, when the recursive-line hole count is at most two, no overtake occurs. We conjecture the sharp budget ⌊ H_limited/3⌋ and that H_limited≥5 is the threshold for an overtake. In the computed range n≤7, no overtake occurs at any order, the sole exception being the known case (4,4). The recursive-line equality z_2=z_RL is verified at every order in the range where both values are determined; the orders at which it remains unsettled are (12,4) and (14,4) at width four, (11,5) at width five, and (8,7) at width seven.
ER -