Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.04111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909011141459968 |
|---|---|
| author | Qi, Liqun Cui, Chunfeng Xu, Yi |
| author_facet | Qi, Liqun Cui, Chunfeng Xu, Yi |
| contents | The limited augmented Zarankiewicz number $z_L(m,n)$ satisfies $\operatorname{BSR}(m,n)\ge z_L(m,n)\ge z(m,n)$, where $\operatorname{BSR}(m,n)$ is the maximum SOS rank of $m\times n$ biquadratic forms and $z(m,n)$ is the classical Zarankiewicz number.
Our main result is a general lower bound for $z_L(m,n)$ based on the incidence graph of the complete graph $K_{4t}$. For every integer $t\ge 1$, let $m = \binom{4t}{2}$ and $n = 4t$. Then $$z_L(m,n) \;\ge\; 2\binom{4t}{2} + 4t^2 - 2t.$$ Consequently, $$ \operatorname{BSR}(m,n) \;\ge\; 2\binom{4t}{2} + 4t^2 - 2t. $$ Since $z = 2\binom{4t}{2} = Θ(t^2)$, the gap satisfies $z_L - z \ge 4t^2 - 2t = Θ(t^2) = Θ(m)$, i.e., it grows linearly in $m$. Moreover, $$ \frac{z_L - z}{z} \;\ge\; \frac{4t^2}{16t^2 - 4t} \;\longrightarrow\; \frac{1}{4} \quad \text{as } t\to\infty, $$ so the gap is asymptotically at least $25\%$ of $z$ -- a non-negligible constant fraction.
For $t=1$ we obtain $z_L(6,4)\ge 14$, and we prove that this bound is tight, i.e., $z_L(6,4)=14$. For $t=2$ and $t=3$ we obtain $z_L(28,8)\ge 68$ and $z_L(66,12)\ge 162$, respectively, improving previously known bounds.
We also determine the exact values of $z_L(m,n)$ for all $m,n\le 5$: $z_L(5,3)=9$, $z_L(5,4)=12$, and $z_L(5,5)=14$, confirming that previously known lower bounds are tight. These results serve as base cases for a \emph{lifting method} that constructs admissible limited augmented graphs on $(m+1)\times(n+1)$ from optimal ones on $m\times n$. Applying this method, we obtain new lower bounds: \[ z_L(6,3)\ge 10,\qquad z_L(6,5)\ge 17,\qquad z_L(6,6)\ge 19, \] where $z(6,3)=9$, $z(6,5)=14$, and $z(6,6)=16$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04111 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A General Lower Bound for the Limited Augmented Zarankiewicz Number based upon Complete Graphs Qi, Liqun Cui, Chunfeng Xu, Yi Combinatorics The limited augmented Zarankiewicz number $z_L(m,n)$ satisfies $\operatorname{BSR}(m,n)\ge z_L(m,n)\ge z(m,n)$, where $\operatorname{BSR}(m,n)$ is the maximum SOS rank of $m\times n$ biquadratic forms and $z(m,n)$ is the classical Zarankiewicz number. Our main result is a general lower bound for $z_L(m,n)$ based on the incidence graph of the complete graph $K_{4t}$. For every integer $t\ge 1$, let $m = \binom{4t}{2}$ and $n = 4t$. Then $$z_L(m,n) \;\ge\; 2\binom{4t}{2} + 4t^2 - 2t.$$ Consequently, $$ \operatorname{BSR}(m,n) \;\ge\; 2\binom{4t}{2} + 4t^2 - 2t. $$ Since $z = 2\binom{4t}{2} = Θ(t^2)$, the gap satisfies $z_L - z \ge 4t^2 - 2t = Θ(t^2) = Θ(m)$, i.e., it grows linearly in $m$. Moreover, $$ \frac{z_L - z}{z} \;\ge\; \frac{4t^2}{16t^2 - 4t} \;\longrightarrow\; \frac{1}{4} \quad \text{as } t\to\infty, $$ so the gap is asymptotically at least $25\%$ of $z$ -- a non-negligible constant fraction. For $t=1$ we obtain $z_L(6,4)\ge 14$, and we prove that this bound is tight, i.e., $z_L(6,4)=14$. For $t=2$ and $t=3$ we obtain $z_L(28,8)\ge 68$ and $z_L(66,12)\ge 162$, respectively, improving previously known bounds. We also determine the exact values of $z_L(m,n)$ for all $m,n\le 5$: $z_L(5,3)=9$, $z_L(5,4)=12$, and $z_L(5,5)=14$, confirming that previously known lower bounds are tight. These results serve as base cases for a \emph{lifting method} that constructs admissible limited augmented graphs on $(m+1)\times(n+1)$ from optimal ones on $m\times n$. Applying this method, we obtain new lower bounds: \[ z_L(6,3)\ge 10,\qquad z_L(6,5)\ge 17,\qquad z_L(6,6)\ge 19, \] where $z(6,3)=9$, $z(6,5)=14$, and $z(6,6)=16$. |
| title | A General Lower Bound for the Limited Augmented Zarankiewicz Number based upon Complete Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.04111 |