Optimization Models and Computational Bounds for Limited Augmented Zarankiewicz Numbers in the Incidence-Graph Family of Complete Graphs

Abstract

Let $G_1$ denote the incidence graph of the complete graph $K_{q+1}$. We study limited augmented Zarankiewicz numbers in this family through structured 0--1 optimization models for admissible 2-edge augmentation. For the original framework, we combine exact ILP formulations for the smallest instances with constructive search followed by exact admissibility verification for larger instances. This yields \[ {z_L(6,4)=14,\qquad z_L(10,5)=26,\qquad z_L(15,6)\ge 43,\qquad z_L(21,7)\ge 64,\qquad z_L(28,8)\ge 88.} \] The first two values are exact, whereas the latter three are rigorous lower bounds obtained from explicitly verified admissible families. We then formulate the global weak problem determined by \((S),(W2),(W2'),(W3)\). On the larger incidence-family cases, the corresponding global exact optimization problem is currently computationally out of reach, and our computations provide the certified lower bounds \[ {z_{WL}(6,4)=14,\quad z_{WL}(10,5)\ge 29,\quad z_{WL}(15,6)\ge 46,\quad z_{WL}(21,7)\ge 65,\quad z_{WL}(28,8)\ge 90.} \] On the fourteen literal-grid benchmarks from $(4,3)$ through $(7,7)$, by contrast, the global weak problem is solved exactly. Across this exact benchmark block, the weak framework is never worse than the strong framework and is strictly better in several cases. These computations improve the corresponding classical Zarankiewicz numbers and therefore strengthen available lower bounds for $\mathrm{BSR}(m,n)$ within this family.