Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families

Source abstract

Let $n\ge6$, $m=\binom n2$, and consider the complete-graph incidence family on $K_n$: columns are vertices, rows are edges, and the one-edge graph is the incidence graph. We study the second-order, signed, and recursive-line Zarankiewicz numbers $z_2,z_{SL},z_{RL}$ of this family. The universal cell bound of Löfberg and Qi gives $$z_2(m,n)\le Z(n):=\left\lfloor\frac{n(n-1)(n+2)}4\right\rfloor,$$ with $Z(n)=n(n-1)(n+2)/4$ for $n$ even or $n\equiv1\pmod4$, and $Z(n)=(n(n-1)(n+2)-2)/4$ for $n\equiv3\pmod4$. We show that this bound is attained, with $z_2=z_{SL}=z_{RL}=Z(n)$, for even $n=2q$ with $q$ an odd prime, and for odd $n=2p+1$ with $p$ odd. The construction is a nested perfect (resp.\ near-perfect) one-factorization; the parity of $p$ controls whether the grid saturates with a hole. The grid bookkeeping is made exact: $H=0$ for even $n$ and for $n\equiv1\pmod4$, and $H=1$ for $n\equiv3\pmod4$; in particular $(n(n-1)(n+2)-1)/4$ never gives the value. We also settle four additional orders by explicit configurations whose $(\mathrm{RW}3^+)$ certificate closures we record: $n=8,12$ (even, $q$ even) and $n=9,13$ (odd, $p$ even), giving $140,462,198,585$ respectively. The $n=13$ and $n=12$ configurations are obtained from the certified $n=14$ construction by deleting the star of a vertex and re-pairing the orphaned cells. The remaining orders, the smallest of which is $n=16$, are stated as a conjecture.