New Lower Bounds for the Limited Augmented Zarankiewicz Number Based on Complete Graphs

The limited augmented Zarankiewicz number provides a combinatorial lower bound for the maximum SOS rank of biquadratic forms and refines the classical Zarankiewicz number by allowing admissible augmented edges. In this paper, new lower bounds for this number are established by using incidence graphs of complete graphs. An infinite family of constructions based on complete graphs is presented, showing that the gap between the limited augmented Zarankiewicz number and the classical Zarankiewicz number can grow linearly with the size of the graph. Several small cases are also studied in detail. In particular, exact values are obtained for the cases 6×4, 5×3, and 5×4, and an improved lower bound is given for the 5×5 case. In addition, a lifting method is introduced to construct admissible limited augmented graphs on larger parameter pairs from suitable smaller ones, leading to further lower bounds. These results strengthen the connection between extremal bipartite graph theory and SOS-rank lower bounds for biquadratic forms.