Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families
Abstract
For n≥6, m=binom n2, let the complete-graph incidence family on Kn have the vertices of Kn as columns, its edges as rows, and the incidence graph as one-edge graph. The universal cell bound of Löfberg and Qi gives z2(m,n)≤ Z(n):=⌊ n(n−1)(n+2)/4⌋. We implement the nested one-factorization construction of that family and determine exactly what it certifies. For n=2q with q an odd prime, q≥5, the construction has no hole and the cross-factor transfer equations apply verbatim, giving z2=zSL=zRL=Z(n); n=6 is settled by a separate cyclic witness. For odd n=2p+1 the near-perfect one-factorization yields Hamilton paths closed into odd cycles, and the transfer argument breaks: that scheme certifies only R(Gp)≤ Z(n). The orders n=7,8,9,12,13,16,17,18,20,21 are settled by explicit configurations of a different shape, each attaining the cell bound and satisfying (RW3+), obtained from a larger configuration by deleting vertex stars and repairing the restricted grid. At each of these orders z2=zSL=zRL=Z(n); all remaining orders are conjectural. The first settled order n=7 is the only one whose grid has a hole, grounded by a zero-companion rule. Machine-readable configurations and a certificate checker accompany the paper.
Related
- Asymptotic equivalence and exact values for second-order Zarankiewicz numbers
- Overtake and the recursive-line equality for second-order Zarankiewicz numbers
- Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
- 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
BibTeX
@misc{chen2026exact,
title = {{Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families}},
author = {Yannan Chen and Johan Löfberg and Liqun Qi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25974},
eprint = {2609.25974},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25974},
}
RIS
TY - UNPB
TI - Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families
AU - Yannan Chen
AU - Johan Löfberg
AU - Liqun Qi
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.25974
UR - https://arxiv.org/abs/2609.25974
AB - For n≥6, m=binom n2, let the complete-graph incidence family on K_n have the vertices of K_n as columns, its edges as rows, and the incidence graph as one-edge graph. The universal cell bound of Löfberg and Qi gives z_2(m,n)≤ Z(n):=⌊ n(n−1)(n+2)/4⌋. We implement the nested one-factorization construction of that family and determine exactly what it certifies. For n=2q with q an odd prime, q≥5, the construction has no hole and the cross-factor transfer equations apply verbatim, giving z_2=z_SL=z_RL=Z(n); n=6 is settled by a separate cyclic witness. For odd n=2p+1 the near-perfect one-factorization yields Hamilton paths closed into odd cycles, and the transfer argument breaks: that scheme certifies only R(G_p)≤ Z(n). The orders n=7,8,9,12,13,16,17,18,20,21 are settled by explicit configurations of a different shape, each attaining the cell bound and satisfying (RW3^+), obtained from a larger configuration by deleting vertex stars and repairing the restricted grid. At each of these orders z_2=z_SL=z_RL=Z(n); all remaining orders are conjectural. The first settled order n=7 is the only one whose grid has a hole, grounded by a zero-companion rule. Machine-readable configurations and a certificate checker accompany the paper.
ER -