A Weak Condition for Limited Augmented Zarankiewicz Numbers
arXiv:2607.07071
The authors define a weaker version of the limited augmented Zarankiewicz number by replacing the opposite‑cell condition with an acyclic dependency rule and a simplified local prohibition, show that the original irreducibility proof still applies, and explore the necessity of these new conditions.
Abstract
This paper introduces the weak augmented Zarankiewicz number and the weak limited augmented Zarankiewicz number , which are combinatorial extensions of the classical Zarankiewicz number obtained by relaxing the original admissibility conditions for augmented bipartite graphs. We show that the resulting weak framework still guarantees irreducibility of the associated doubly simple biquadratic forms, with SOS rank equal to the total number of edges. This yields the inequality chain \[ \mathrm{BSR}(m,n) \geq z_{wA}(m,n) \geq z_{wL}(m,n) \geq z_L(m,n) \geq z(m,n). \] We provide three complementary constructions demonstrating the power of the weak framework. First, a construction using degenerate 2-edges yields , giving . Second, a construction on the incidence graph of with 14 nondegenerate 2-edges gives , improving the previously known bound. Third, a critical construction with complementary 2-cycles gives , yielding and demonstrating that complementary 2-cycles are safe.