OpenAlex ·
Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.25974
- Original
- Read it at the publisher
- Topics
Abstract
For $n\ge6$, $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)\le Z(n):=\lfloor n(n-1)(n+2)/4\rfloor$. 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\ge5$, 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)\le 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 $(\mathrm{RW}3^+)$, 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A linear-in-$q$ range of dimensions for the MDS conjecture over $\mathbb F_q$ in odd characteristic
Minimal representations of topology-preserving quantum-like states
Sampling Line-Graph Colorings with Constant Extra Colors
Irrational Seshadri constants from dihedral orbits
A 27 x 27 x 27 counterexample to Comon's conjecture
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.