The Second-Order Augmented Zarankiewicz Number

Source abstract

The second-order Zarankiewicz number $z_2(m,n)$ and the biquadratic sum-of-squares rank $\mathrm{BSR}(m,n)$ are related by the unconditional hierarchy $$\mathrm{BSR}(m,n)\ \ge\ z_2(m,n)\ \ge\ z_{SL}(m,n)\ \ge\ z_{RL}(m,n) \ \ge\ z_{wL}(m,n)\ \ge\ 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 $$\mathrm{BSR}(m,n)\ \ge\ z_{2A}(m,n)\ \ge\ 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 $$\mathrm{BSR}(4,4)\ \ge\ 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 $\mathrm{BSR}(4,4)$. The lower bound is witnessed by an explicit non-limited $4\times4$ configuration of displayed length $11$ whose recursive-line closure satisfies $(\mathrm{RW}3^+)$; 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.