January 01, 1970
We extend the augmented bipartite graph framework for biquadratic sum-of-squares (SOS) ranks by introducing 3-edges — triples of cells representing squares of three-term bilinear forms \((x_i y_j + x_k y_l + x_p y_q)^2\). The main challenge is to define suitable generalized cycle-free conditions that are purely combinatorial yet sufficient to guarantee that the SOS rank equals the total number of edges. We give a complete definition that carefully distinguishes occupation by \(1\)/\(2\)-edges from occupation by \(3\)-edges, and introduce a separate condition for \(3\)-edges. The main theorem states that for any generalized cycle-free augmented bipartite graph \(G\) satisfying the simplicity condition (S), the associated triply simple biquadratic form \(P_G\) satisfies \(\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|\). The proof extends the orthogonality method with a novel trick: when a \(2\)-edge and a \(3\)-edge interact, the \(3\)-edge condition must be invoked rather than the \(2\)-edge condition. As concrete applications, we construct a \(10 \times 5\) graph using a column-fully-degenerate \(3\)-edge, showing \(z_{3L}(10,5) \ge 27\) and \(\operatorname{BSR}(10,5) \ge 27\), which separates \(z_{3L}(10,5)\) from \(z_L(10,5)=26\); and a \(15 \times 6\) graph using a half-row-degenerate \(3\)-edge, improving the lower bound for \(\operatorname{BSR}(15,6)\) from \(43\) to \(44\). These are the first explicit applications of \(3\)-edges (both fully degenerate and half-degenerate) to obtain improved lower bounds for \(\operatorname{BSR}(m,n)\).
biquadratic form; sum of squares; SOS rank; Zarankiewicz number; augmented Zarankiewicz number; limited augmented Zarankiewicz number; bipartite graph; \(3\)-edge; \(C_4\)-cycle; generalized cycle-free
14P10 (Real algebraic geometry); 05C35 (Extremal graph theory); 11E25 (Quadratic forms); 15A69 (Multilinear algebra); 90C22 (Semidefinite programming)
For an \(m \times n\) biquadratic form \[P(\mathbf{x},\mathbf{y}) = \sum_{i,k=1}^m \sum_{j,l=1}^n a_{ijkl} \, x_i x_k y_j y_l,\] with symmetry \(a_{ijkl} = a_{kjil} = a_{klij}\), the SOS rank \(\operatorname{sos}(P)\) is the smallest integer \(r\) such that \[P(\mathbf{x},\mathbf{y}) = \sum_{t=1}^r f_t(\mathbf{x},\mathbf{y})^2\] for some bilinear forms \(f_t\). The maximum SOS rank over all \(m \times n\) SOS biquadratic forms is denoted \(\operatorname{BSR}(m,n)\). Understanding the possible values of \(\operatorname{BSR}(m,n)\) is a fundamental problem in real algebraic geometry and polynomial optimization, with connections to low-rank sum-of-squares representations [1], [2].
In a recent breakthrough [3], a combinatorial lower bound for \(\operatorname{BSR}(m,n)\) was established using the limited augmented Zarankiewicz number \(z_L(m,n)\), satisfying \[\operatorname{BSR}(m,n) \ge z_L(m,n) \ge z(m,n),\] where \(z(m,n)\) is the classical Zarankiewicz number (maximum number of edges in a \(C_4\)-free bipartite graph) [4]–[6]. The quantity \(z_L(m,n)\) arises from augmented bipartite graphs that contain both standard \(1\)-edges (representing pure squares \(x_i^2 y_j^2\)) and \(2\)-edges (representing squares of binomials \((x_i y_j + x_k y_l)^2\)). A sufficient condition called generalized \(C_4\)-cycle-free was introduced to guarantee that the SOS rank equals the total number of edges.
The present paper extends this framework to \(3\)-edges: unordered triples of distinct cells \(\{(i,j),(k,l),(p,q)\}\) representing a square of a trinomial \[(x_i y_j + x_k y_l + x_p y_q)^2.\] The main challenge is to define suitable generalized cycle-free conditions that are purely combinatorial yet sufficient to prove that the SOS rank of the associated triply simple biquadratic form \[P_G(\mathbf{x},\mathbf{y}) = \sum_{(i,j)\in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l)\in E_2} (x_i y_j + x_k y_l)^2 + \sum_{(i,j;k,l;p,q)\in E_3} (x_i y_j + x_k y_l + x_p y_q)^2\] equals \(|E_1|+|E_2|+|E_3|\).
Three types of \(3\)-edges arise naturally:
Non-degenerate: all three rows distinct and all three columns distinct.
Half-degenerate: exactly two cells share a row (half-row-degenerate) or exactly two share a column (half-column-degenerate).
Fully degenerate: all three cells in the same row or all three in the same column.
Each type requires careful handling in the definition of dead edges and in the generalized cycle-free conditions.
The main theoretical result (Theorem 1) states that if an augmented bipartite graph \(G = (S,T,E_1\cup E_2\cup E_3)\) satisfies the simplicity condition (S) (no cell appears in more than one edge) and is generalized cycle-free (Definition 1), then \[\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|.\] The proof extends the orthogonality method from [3] but requires a novel trick: when a \(2\)-edge and a \(3\)-edge interact, Condition (iv) (designed for \(3\)-edges) must be invoked rather than Condition (iii) (which only counts occupation by \(1\)-edges and \(2\)-edges). This subtlety is essential for the correctness of the proof and for allowing half-degenerate \(3\)-edges in constructions.
We demonstrate the power of the new framework with two concrete applications:
Using a column-fully-degenerate \(3\)-edge in the \(10 \times 5\) case, we show \[z_{3L}(10,5) \ge 27 \quad\text{and}\quad \operatorname{BSR}(10,5) \ge 27,\] which separates \(z_{3L}(10,5)\) from the limited augmented Zarankiewicz number \(z_L(10,5)=26\).
Using a half-row-degenerate \(3\)-edge in the \(15 \times 6\) case, we improve the lower bound for \(\operatorname{BSR}(15,6)\) from \(43\) to \(44\), showing \[z_{3A}(15,6) \ge 44 \quad\text{and}\quad \operatorname{BSR}(15,6) \ge 44.\]
These are the first explicit constructions where \(3\)-edges (both fully degenerate and half-degenerate) yield better bounds than using only \(1\)-edges and \(2\)-edges.
The remainder of the paper is organized as follows. Section 2 formally defines \(2\)-edges, \(3\)-edges, occupied cells, dead edges, the simplicity condition (S), and the triply simple biquadratic form. Section 3 presents the generalized \(C_4\)-cycle definition (Conditions (i)-(iv)), which is the core combinatorial condition for irreducibility. Section 4 states and proves the main theorem. Section 5 introduces the extremal numbers \(z_{3A}(m,n)\) and \(z_{3L}(m,n)\) and establishes basic inequalities. Sections 6 and 7 present the two applications: a fully degenerate \(3\)-edge for \(10 \times 5\) and a half-degenerate \(3\)-edge for \(15 \times 6\), respectively. Section 8 concludes the paper with a summary and open problems.
Let \(S = [m]\), \(T = [n]\). An augmented bipartite graph with \(3\)-edges is a triple \[G = (S,T, E_1 \cup E_2 \cup E_3)\] where:
\(E_1 \subseteq S \times T\) are \(1\)-edges,
\(E_2\) consists of unordered pairs \(\{(i,j),(k,l)\}\) with \((i,j) \neq (k,l)\) (\(2\)-edges),
\(E_3\) consists of unordered triples \(\{(i,j),(k,l),(p,q)\}\) with all three distinct (\(3\)-edges).
There are two kinds of \(2\)-edges. A \(2\)-edge \((i, j; k, l)\) is called:
non-degenerate if \(i \neq k\) and \(j \neq l\),
row-degenerate if \(i = k\) and \(j \neq l\),
column-degenerate if \(i \neq k\) and \(j = l\).
For \(3\)-edges, we have three types:
Non-degenerate: all three rows distinct and all three columns distinct.
Half-degenerate: exactly two cells share a row (half-row-degenerate) or exactly two share a column (half-column-degenerate).
Fully degenerate: all three cells in the same row (row-fully-degenerate) or all three in the same column (column-fully-degenerate).
A half-row-degenerate \(3\)-edge has the form \((i, j; i, l; p, q)\) with \(i \neq p\) and \(j, l, q\) all distinct. A half-column-degenerate \(3\)-edge has the form \((i, j; k, j; p, q)\) with \(j \neq q\) and \(i, k, p\) all distinct. A row-fully-degenerate \(3\)-edge has the form \((i, j; i, l; i, m)\) with \(j, l, m\) all distinct. A column-fully-degenerate \(3\)-edge has the form \((i, j; k, j; p, j)\) with \(i, k, p\) all distinct.
A cell \((i,j)\) is occupied if it belongs to \(E_1\) or is a half of some \(2\)-edge or \(3\)-edge. A cell pair is occupied if both cells are occupied.
We say that:
A non-degenerate \(2\)-edge is dead if its opposite cell pair is occupied.
A non-degenerate \(3\)-edge is dead if two or three of its opposite cell pairs are occupied.
A half-degenerate \(3\)-edge is dead if both of its two opposite cell pairs are occupied.
Fully degenerate \(3\)-edges have no opposite pairs and are therefore never dead.
No cell appears in more than one edge. That is, \[E_1,\; \bigcup_{e\in E_2} e,\; \bigcup_{e\in E_3} e\] are pairwise disjoint.
The triply simple biquadratic form associated to \(G\) is \[P_G(\mathbf{x},\mathbf{y}) = \sum_{(i,j)\in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l)\in E_2} (x_i y_j + x_k y_l)^2 + \sum_{(i,j;k,l;p,q)\in E_3} (x_i y_j + x_k y_l + x_p y_q)^2.\]
We now extend the generalized \(C_4\)-cycle definition from [3] to include all \(3\)-edge types.
Definition 1. \(G = (S,T,E_1 \cup E_2 \cup E_3)\) is generalized cycle-free if none of the following occur:
There exists a classical \(C_4\)-cycle formed by \(1\)-edges.
There exists a dead non-degenerate \(2\)-edge or a dead non-degenerate or half-degenerate \(3\)-edge. (Fully degenerate \(3\)-edges are never dead.)
There exists a \(2\)-edge \((i, j; p, q)\) (of any type) and a distinct cell \((k, l)\), with \(k \notin \{i,p\}\), \(l \notin \{j,q\}\), such that the five cells \((k, j), (k, l), (k, q), (i, l)\) and \((p, l)\) are all occupied by \(1\)-edges and \(2\)-edges. (If the \(2\)-edge is non-degenerate, these five cells are required to be pairwise distinct; otherwise duplicates are allowed.)
There exists a \(3\)-edge \((i, j; p, q; u, v)\) and a distinct cell \((k, l)\), with \(k \notin \{i,p,u\}\), \(l \notin \{j,q,v\}\), such that the seven cells \((k, j), (k, l), (k, q), (k, v), (i, l), (p, l)\) and \((u, l)\) are all occupied. (If the \(3\)-edge is non-degenerate, these seven cells are required to be pairwise distinct; otherwise duplicates are allowed.)
Theorem 1 (Irreducibility for \(3\)-edge augmented graphs). Let \(G = (S,T,E_1 \cup E_2 \cup E_3)\) be a generalized cycle-free augmented bipartite graph (Definition 1) satisfying the simplicity condition (S). Then the corresponding triply simple biquadratic form \(P_G\) satisfies \[\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|.\]
Proof. We prove that \(\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|\). The upper bound \(\operatorname{sos}(P_G) \le |E_1| + |E_2| + |E_3|\) is trivial because \(P_G\) is explicitly written as a sum of that many squares. The heart of the proof is the lower bound.
Let \(r = \operatorname{sos}(P_G)\). Then there exist bilinear forms \(f_1,\dots,f_r\) such that \(P_G = \sum_{t=1}^r f_t^2\). Write \(f_t(\mathbf{x},\mathbf{y}) = \sum_{i,j} a_{ij}^{(t)} x_i y_j\) and define vectors \(\mathbf{v}_{ij} = (a_{ij}^{(1)},\dots,a_{ij}^{(r)})^\top \in \mathbb{R}^r\). For any cells \((i,j),(k,l)\) we have \[\mathbf{v}_{ij}\cdot \mathbf{v}_{kl} = \text{coefficient of } x_i x_k y_j y_l \text{ in } P_G,\] where the coefficient is taken in the symmetric form with \(a_{ijkl}=a_{klij}\).
Expanding each square in \(P_G\) yields the following relations.
For a \(1\)-edge \((i,j)\in E_1\): \[\|\mathbf{v}_{ij}\|^2 = 1. \qquad (1)\]
For a non-degenerate \(2\)-edge \((i,j;k,l)\in E_2\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{kl}\|^2 = 1,\qquad \mathbf{v}_{ij}\cdot\mathbf{v}_{kl} + \mathbf{v}_{il}\cdot\mathbf{v}_{kj} = 1. \qquad (2)\] For a row-degenerate \(2\)-edge \((i,j;i,l)\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{il}\|^2 = 1,\qquad \mathbf{v}_{ij}\cdot\mathbf{v}_{il}=1. \qquad (2\text{-row})\] For a column-degenerate \(2\)-edge \((i,j;k,j)\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{kj}\|^2 = 1,\qquad \mathbf{v}_{ij}\cdot\mathbf{v}_{kj}=1. \qquad (2\text{-col})\]
For a non-degenerate \(3\)-edge \((i,j;k,l;p,q)\in E_3\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{kl}\|^2 = \|\mathbf{v}_{pq}\|^2 = 1, \qquad (3a)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kl} + \mathbf{v}_{il}\cdot\mathbf{v}_{kj} = 1, \qquad (3b)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{pq} + \mathbf{v}_{iq}\cdot\mathbf{v}_{pj} = 1, \qquad (3c)\] \[\mathbf{v}_{kl}\cdot\mathbf{v}_{pq} + \mathbf{v}_{kq}\cdot\mathbf{v}_{pl} = 1. \qquad (3d)\]
For a half-row-degenerate \(3\)-edge \((i,j;i,l; p,q)\in E_3\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{il}\|^2 = \|\mathbf{v}_{pq}\|^2 = 1, \qquad (3h1)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{il} = 1, \qquad (3h2)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{pq} + \mathbf{v}_{iq}\cdot\mathbf{v}_{pj} = 1, \qquad (3h3)\] \[\mathbf{v}_{il}\cdot\mathbf{v}_{pq} + \mathbf{v}_{iq}\cdot\mathbf{v}_{pl} = 1. \qquad (3h4)\]
For a half-column-degenerate \(3\)-edge \((i,j; k,j; p,q)\in E_3\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{kj}\|^2 = \|\mathbf{v}_{pq}\|^2 = 1, \qquad (3c1)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kj} = 1, \qquad (3c2)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{pq} + \mathbf{v}_{iq}\cdot\mathbf{v}_{pj} = 1, \qquad (3c3)\] \[\mathbf{v}_{kj}\cdot\mathbf{v}_{pq} + \mathbf{v}_{kq}\cdot\mathbf{v}_{pj} = 1. \qquad (3c4)\]
For a row-fully-degenerate \(3\)-edge \((i,j; i,l; i,m)\in E_3\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{il}\|^2 = \|\mathbf{v}_{im}\|^2 = 1, \qquad (3r1)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{il} = 1,\qquad \mathbf{v}_{ij}\cdot\mathbf{v}_{im} = 1,\qquad \mathbf{v}_{il}\cdot\mathbf{v}_{im} = 1. \qquad (3r2)\]
For a column-fully-degenerate \(3\)-edge \((i,j; k,j; p,j)\in E_3\): \[\|\mathbf{v}_{ij}\|^2 = \|\mathbf{v}_{kj}\|^2 = \|\mathbf{v}_{pj}\|^2 = 1, \qquad (3f1)\] \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kj} = 1,\qquad \mathbf{v}_{ij}\cdot\mathbf{v}_{pj} = 1,\qquad \mathbf{v}_{kj}\cdot\mathbf{v}_{pj} = 1. \qquad (3f2)\]
Orthogonality rules for unrelated cells. For any two distinct pairs \((i,j),(k,l)\) that are not the two halves of the same \(2\)-edge or \(3\)-edge, the corresponding coefficient in \(P_G\) is zero. Hence:
If \(\{i,k\}\cap\{j,l\}=\emptyset\) (all indices distinct): \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kl} + \mathbf{v}_{il}\cdot\mathbf{v}_{kj} = 0. \qquad (4)\]
If \(i=k\) and \(j\neq l\) and \((i,j),(i,l)\) are not the halves of a row-degenerate \(2\)-edge: \[\mathbf{v}_{ij}\cdot\mathbf{v}_{il} = 0. \qquad (5)\]
If \(j=l\) and \(i\neq k\) and \((i,j),(k,j)\) are not the halves of a column-degenerate \(2\)-edge: \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kj} = 0. \qquad (6)\]
Recall Definition 1. Because \(G\) is generalized cycle-free:
Condition (ii) implies there is no dead non-degenerate \(2\)-edge and no dead \(3\)-edge. Hence every \(2\)-edge is alive and every \(3\)-edge is alive.
A non-degenerate \(2\)-edge \((i,j;k,l)\) is alive iff at most one of the opposite cells \((i,l),(k,j)\) is occupied.
A non-degenerate \(3\)-edge is alive iff at most one of its three opposite cell pairs is fully occupied.
A half-degenerate \(3\)-edge is alive iff at most one of its two opposite cell pairs is fully occupied.
Convention: A cell that is not occupied is assigned the zero vector. Conversely, if \(\mathbf{v}_{ij}\neq\mathbf{0}\), then the cell is occupied (this follows from the equations below, as all nonzero vectors appear in some edge with norm 1).
We now exploit these properties.
Living \(2\)-edges. For a non-degenerate \(2\)-edge \((i,j;k,l)\): since it is alive, at most one of the opposite cells is occupied. Thus at least one of \(\mathbf{v}_{il},\mathbf{v}_{kj}\) is the zero vector. Then (2) gives \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=1\); together with unit norms from (2) and Cauchy–Schwarz we obtain \[\mathbf{v}_{ij} = \mathbf{v}_{kl}. \qquad (7)\] For a row-degenerate \(2\)-edge: (2-row) directly gives \(\mathbf{v}_{ij}= \mathbf{v}_{il}\). For a column-degenerate \(2\)-edge: (2-col) gives \(\mathbf{v}_{ij}= \mathbf{v}_{kj}\).
Living \(3\)-edges. Case 1: Non-degenerate \(3\)-edge \((i,j;k,l;p,q)\). Because it is alive, at most one of the three opposite pairs is fully occupied. Hence at least two of the pairs are not fully occupied. Consider (3b). If \(\{(i,l),(k,j)\}\) is not fully occupied, then at least one of \(\mathbf{v}_{il},\mathbf{v}_{kj}\) is zero, so \(\mathbf{v}_{il}\cdot\mathbf{v}_{kj}=0\), hence \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=1\) and by Cauchy–Schwarz \(\mathbf{v}_{ij}=\mathbf{v}_{kl}\). Similarly, if \(\{(i,q),(p,j)\}\) is not fully occupied then \(\mathbf{v}_{ij}=\mathbf{v}_{pq}\) from (3c); if \(\{(k,q),(p,l)\}\) is not fully occupied then \(\mathbf{v}_{kl}=\mathbf{v}_{pq}\) from (3d). Since at least two of the three pairs are not fully occupied, we deduce \[\mathbf{v}_{ij} = \mathbf{v}_{kl} = \mathbf{v}_{pq}. \qquad (8)\]
Case 2: Half-row-degenerate \(3\)-edge \((i,j),\;(i,l),\;(p,q)\). It has two opposite pairs: \(P_1 = \{(i,q),(p,j)\}\) and \(P_2 = \{(i,q),(p,l)\}\). Alive means at most one of \(P_1,P_2\) is fully occupied. Hence at least one is not full. If \(P_1\) is not full, then at least one of \(\mathbf{v}_{iq},\mathbf{v}_{pj}\) is zero, so from (3h3): \(\mathbf{v}_{ij}\cdot\mathbf{v}_{pq}=1\) implies \(\mathbf{v}_{ij}=\mathbf{v}_{pq}\). If \(P_2\) is not full, then from (3h4): \(\mathbf{v}_{il}\cdot\mathbf{v}_{pq}=1\) implies \(\mathbf{v}_{il}=\mathbf{v}_{pq}\). Thus at least one equality holds. But from (3h2), \(\mathbf{v}_{ij}\cdot\mathbf{v}_{il}=1\) implies \(\mathbf{v}_{ij}=\mathbf{v}_{il}\) (since both have norm 1). Hence all three are equal: \[\mathbf{v}_{ij} = \mathbf{v}_{il} = \mathbf{v}_{pq}. \qquad (8h)\]
Case 3: Half-column-degenerate \(3\)-edge \((i,j),\;(k,j),\;(p,q)\). Similarly, from (3c2): \(\mathbf{v}_{ij}=\mathbf{v}_{kj}\), and from (3c3)/(3c4) and the alive condition we obtain \(\mathbf{v}_{ij}=\mathbf{v}_{pq}\) or \(\mathbf{v}_{kj}=\mathbf{v}_{pq}\), so \[\mathbf{v}_{ij} = \mathbf{v}_{kj} = \mathbf{v}_{pq}. \qquad (8c)\]
Case 4: Row-fully-degenerate \(3\)-edge \((i,j),\;(i,l),\;(i,m)\). From (3r2), \(\mathbf{v}_{ij}\cdot\mathbf{v}_{il}=1\) and \(\|\mathbf{v}_{ij}\|=\|\mathbf{v}_{il}\|=1\) implies \(\mathbf{v}_{ij}=\mathbf{v}_{il}\). Similarly \(\mathbf{v}_{ij}=\mathbf{v}_{im}\). Hence \[\mathbf{v}_{ij} = \mathbf{v}_{il} = \mathbf{v}_{im}. \qquad (8r)\]
Case 5: Column-fully-degenerate \(3\)-edge \((i,j),\;(k,j),\;(p,j)\). From (3f2), \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kj}=1\) implies \(\mathbf{v}_{ij}=\mathbf{v}_{kj}\), and similarly \(\mathbf{v}_{ij}=\mathbf{v}_{pj}\). Hence \[\mathbf{v}_{ij} = \mathbf{v}_{kj} = \mathbf{v}_{pj}. \qquad (8f)\]
Thus every \(2\)-edge forces equality of its two half-vectors, and every \(3\)-edge (of any type) forces equality of all three of its cell vectors.
Let \(H\) be the set of all occupied cells. For each \(1\)-edge pick its unique cell; for each \(2\)-edge pick one of its two halves; for each \(3\)-edge pick one of its three halves. This gives a set \(R\) of representatives with \(|R| = |E_1|+|E_2|+|E_3|\). If \(\operatorname{sos}(P_G) < |E_1|+|E_2|+|E_3|\), then \(r < |R|\) and the vectors \(\{\mathbf{v}_{ij} : (i,j)\in R\}\) lie in \(\mathbb{R}^r\), so they are linearly dependent. Choose a nontrivial linear relation \[\sum_{(i,j)\in R} \alpha_{ij} \mathbf{v}_{ij} = \mathbf{0}\] with minimal support \(S \subseteq R\) (i.e., \(\alpha_{ij}\neq 0\) for \((i,j)\in S\) and no proper nonempty subset yields a dependence). Minimality implies:
No two distinct cells in \(S\) belong to the same \(2\)-edge or \(3\)-edge (otherwise (7) or (8) would give two equal vectors, and we could combine their coefficients to obtain a relation with smaller support).
All vectors \(\{\mathbf{v}_{ij} : (i,j)\in S\}\) are nonzero and pairwise distinct.
We prove that for any two distinct cells \((i,j),(k,l)\in S\), \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=0.\] Consider several cases.
Case A: \(i,k,j,l\) are all distinct. Apply (4): \[\mathbf{v}_{ij}\cdot\mathbf{v}_{kl} + \mathbf{v}_{il}\cdot\mathbf{v}_{kj}=0.\] Suppose for contradiction that \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}\neq 0\). Then \(\mathbf{v}_{il}\cdot\mathbf{v}_{kj}\neq 0\), hence both \((i,l)\) and \((k,j)\) are occupied (nonzero vectors imply occupied by the convention above). At least one of \((i,j),(k,l)\) belongs to a \(2\)-edge or \(3\)-edge (otherwise they would be \(1\)-edges and we would obtain a contradiction from the generalized cycle-free condition (i) as shown below). Without loss assume \((i,j)\) is half of some edge \(e\in E_2\cup E_3\).
Subcase A1: \((i,j)\) belongs to a \(2\)-edge \((i,j;p,q)\). By (7), \(\mathbf{v}_{ij}=\mathbf{v}_{pq}\) and \((p,q)\) is occupied. Since \((i,j)\in S\), minimality forces \((p,q)\notin S\). Apply (4) to \((p,q)\) and \((k,l)\): \[\mathbf{v}_{pq}\cdot\mathbf{v}_{kl} + \mathbf{v}_{pl}\cdot\mathbf{v}_{kq}=0.\] Because \(\mathbf{v}_{pq}=\mathbf{v}_{ij}\) and \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}\neq0\), we get \(\mathbf{v}_{pl}\cdot\mathbf{v}_{kq}\neq0\), so \((p,l)\) and \((k,q)\) are occupied. Now we have occupied cells: \((i,j),(k,l),(i,l),(k,j),(p,q),(p,l),(k,q)\). If \(p=k\) or \(q=l\) then two cells among these share a row or column without being halves of a degenerate \(2\)-edge (otherwise they would be equal and cause a smaller support), which would contradict (5) or (6). Therefore \(p\neq k\) and \(q\neq l\).
Consider the five cells \[(k,l),\;(k,j),\;(k,q),\;(i,l),\;(p,l).\] All are occupied, \(k\notin\{i,p\}\), \(l\notin\{j,q\}\), and \((i,j;p,q)\) is a \(2\)-edge. We now distinguish two possibilities:
If none of these five cells is a half of a \(3\)-edge (i.e., each is occupied by a \(1\)-edge or a \(2\)-edge), then Condition (iii) of Definition 1 applies directly, giving a contradiction.
If some of these five cells is a half of a \(3\)-edge, say \(e_3 = (a,b;c,d;e,f)\), then consider that \(3\)-edge together with the original \(2\)-edge \((i,j;p,q)\) and the cell \((k,l)\). Because \((k,l)\) is distinct from the cells of \(e_3\) and satisfies the index disjointness conditions (since \(k\notin\{i,p\}\) and \(l\notin\{j,q\}\), and \(e_3\) shares at most one row or column with \((i,j)\) or \((p,q)\) by the structure of the five cells), the configuration of seven cells \[(k,j),\;(k,l),\;(k,q),\;(k,v),\;(i,l),\;(p,l),\;(u,l)\] (where \((u,v)\) is an appropriate cell from \(e_3\)) becomes fully occupied. This violates Condition (iv) of Definition 1, again a contradiction.
Thus in all situations we reach a contradiction. Hence \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=0\) in Subcase A1.
Subcase A2: \((i,j)\) belongs to a \(3\)-edge \((i,j;p,q;u,v)\). This includes non-degenerate, half-degenerate, and fully degenerate cases. By (8), (8h), (8c), (8r), or (8f), we have \(\mathbf{v}_{ij}=\mathbf{v}_{pq}=\mathbf{v}_{uv}\) (or appropriate equalities). The other two cells \((p,q),(u,v)\) are occupied but not in \(S\) (otherwise equal vectors would violate minimality). Apply (4) to \((p,q)\) and \((k,l)\) (and similarly for \((u,v)\)) to obtain that \((p,l),(k,q),(u,l),(k,v)\) are occupied. Using \(k\notin\{i,p,u\}\) and \(l\notin\{j,q,v\}\) (otherwise row/column orthogonality gives contradictions), we obtain the seven occupied cells \[(k,l),\;(k,j),\;(k,q),\;(k,v),\;(i,l),\;(p,l),\;(u,l).\] If the \(3\)-edge is not non-degenerate, then some of \(i,p,u\) may coincide, or some of \(j,q,v\) may coincide, causing duplicates in this list. However, Condition (iv) allows duplicates (the distinctness requirement applies only to non-degenerate \(3\)-edges). Thus the configuration remains forbidden. Hence \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=0\) in Case A.
Case B: \(i=k\) and \(j\neq l\) (same row). If \((i,j)\) and \((i,l)\) were the two halves of a row-degenerate \(2\)-edge, then (2-row) would give \(\mathbf{v}_{ij}=\mathbf{v}_{il}\), contradicting minimality (distinct cells in \(S\) with equal vectors). Thus (5) applies and \(\mathbf{v}_{ij}\cdot\mathbf{v}_{il}=0\).
Case C: \(j=l\) and \(i\neq k\) (same column). Analogously, they cannot be halves of a column-degenerate \(2\)-edge, so (6) gives \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kj}=0\).
Therefore in every case \(\mathbf{v}_{ij}\cdot\mathbf{v}_{kl}=0\) for distinct cells in \(S\).
Take the minimal dependence \(\sum_{(i,j)\in S} \alpha_{ij}\mathbf{v}_{ij}=0\). Fix \((i,j)\in S\) and dot both sides with \(\mathbf{v}_{ij}\): \[\alpha_{ij}\|\mathbf{v}_{ij}\|^2 + \sum_{(p,q)\in S\setminus\{(i,j)\}} \alpha_{pq}\,(\mathbf{v}_{pq}\cdot\mathbf{v}_{ij}) = 0.\] By orthogonality (Step 4), all dot products with \((p,q)\neq (i,j)\) vanish. Hence \(\alpha_{ij}\|\mathbf{v}_{ij}\|^2 = 0\). From (1) or from (7),(8) we have \(\|\mathbf{v}_{ij}\|=1\), so \(\alpha_{ij}=0\). This holds for every \((i,j)\in S\), contradicting the nontriviality of the dependence.
Thus our assumption \(\operatorname{sos}(P_G) < |E_1|+|E_2|+|E_3|\) is false. Consequently \(\operatorname{sos}(P_G) \ge |E_1|+|E_2|+|E_3|\), and together with the trivial upper bound we obtain equality. ◻
The locally solvable framework introduced in Definition 1 applies uniformly to graphs containing \(1\)-edges, \(2\)-edges and \(3\)-edges. This naturally yields four interrelated extremal numbers.
Definition 2 (Full \(3\)-augmented Zarankiewicz numbers). Let \(z_{3A}(m,n)\) denote the maximum possible value of \(|E_1|+|E_2|+|E_3|\) over all generalized cycle-free augmented bipartite graphs \(G=(S,T,E_1\cup E_2\cup E_3)\) (Definition 1) satisfying the simplicity condition (S). Let \(z_{3L}(m,n)\) denote the same maximum under the additional restriction that \(|E_1| = z(m,n)\) (i.e., \(E_1\) is a maximum \(C_4\)-free graph).
Proposition 2 (Basic inequalities). For all \(m,n \ge 2\), \[z_{3A}(m,n) \;\ge\; z_{3L}(m,n) \;\ge\; z_{L}(m,n) \;\ge\; z(m,n).\]
We now give a concrete application showing that \(z_{3L}(10,5) \ge z_L(10,5)+1\).
For \(q=4\), the incidence graph of \(K_5\) gives \(m=10\), \(n=5\), \(|E_1|=20\), and the known optimal \(E_2\) from [7] has \(|E_2|=6\), yielding \(z_L(10,5)=26\).
The available cells (not in \(E_1\) or \(E_2\)) include: \[(12,0),\;(13,0),\;(23,0),\;(24,0),\;(02,1),\;(24,1),\;(34,1),\;\dots\] In particular, column \(0\) has at least three available cells: \((12,0)\), \((13,0)\), \((23,0)\).
Define the column-fully-degenerate \(3\)-edge \[e_3 = \{(12,0),\;(13,0),\;(23,0)\}.\]
Simplicity (S): All three cells are available and distinct, so no conflict.
Condition (ii): Fully degenerate \(3\)-edges are never dead by definition.
Condition (iii): We must check that no \(2\)-edge \((i,j;p,q)\in E_2\) and cell \((k,l)\) with \(k\notin\{i,p\}\), \(l\notin\{j,q\}\) make the five cells \[(k,l),\;(k,j),\;(k,q),\;(i,l),\;(p,l)\] all occupied by \(1\)-edges or \(2\)-edges. The new cells are in column \(0\). There are two subcases:
If the \(2\)-edge has \(q=0\), then \(l\notin\{j,0\}\) forces \(l\neq0\), so the new cells in column \(0\) never appear as \((i,l)\) or \((p,l)\).
If the \(2\)-edge has \(q\neq0\) (and similarly \(j\neq0\)), then \(l=0\) is allowed because \(0\notin\{j,q\}\). In this case \((i,0)\) or \((p,0)\) could be one of the new cells. However, a direct exhaustive check of all six \(2\)-edges in \(E_2\) (listed in [7]) shows that for every such \(2\)-edge and every admissible \((k,l)\) with \(l=0\), at least one of the five cells is not occupied by a \(1\)-edge or \(2\)-edge. For example, the \(2\)-edge \((01,2;35,4)\) has \(j=2\), \(q=4\), so \(l=0\) is allowed; then \((p,l)=(35,0)\) is not occupied by any \(1\)-edge or \(2\)-edge. Similar checks hold for all other \(2\)-edges.
Thus Condition (iii) is not triggered.
Condition (iv): For the \(3\)-edge itself, with \(i=12,j=0,p=13,q=0,u=23,v=0\), the seven cells become \[(k,0),\;(k,l),\;(k,0),\;(k,0),\;(12,l),\;(13,l),\;(23,l).\] For any \(l\neq0\) (since \(l\notin\{j,q,v\}=\{0\}\)), the cells \((12,l),(13,l),(23,l)\) are not all occupied (e.g., for \(l=1\), \((23,1)\) is free). Hence no violation.
Thus \(G = (S,T,E_1 \cup E_2 \cup \{e_3\})\) is generalized cycle-free.
Theorem 3. For \(m=10\), \(n=5\), \[z_{3L}(10,5) \ge 27 \qquad\text{and}\qquad \operatorname{BSR}(10,5) \ge 27.\] In particular, \(z_{3L}(10,5) \ge z_L(10,5) + 1\).
Proof. The graph has \(|E_1|=20\), \(|E_2|=6\), \(|E_3|=1\), and is generalized cycle-free. By Theorem 1, \[\operatorname{sos}(P_G) = 20+6+1 = 27.\] Hence \(\operatorname{BSR}(10,5) \ge 27\) and \(z_{3L}(10,5) \ge 27\). Since \(z_L(10,5)=26\), the separation follows. ◻
We recall the setting from [8] and [7]. For the incidence graph of the complete graph \(K_{6}\), we have: \[m = \binom{6}{2} = 15,\qquad n = 6,\qquad z(15,6) = 30.\] The classical extremal \(C_4\)-free graph is the incidence graph itself. In XCQ26?, an admissible limited augmented graph with \(|E_2| = 13\) was exhibited, giving the lower bound \[z_L(15,6) \ge 30 + 13 = 43.\]
We now show that by adding a half-degenerate 3-edge to this construction, we can increase the total count to \(44\), thereby improving the bound for \(\operatorname{BSR}(15,6)\).
Let \(V = \{0,1,2,3,4,5\}\). The left vertices are the 2-element subsets of \(V\) (edges of \(K_6\)), and the right vertices are the elements of \(V\). The 1-edges are all incidences: \[E_1 = \{(e, v) : e \in \binom{V}{2},\;v \in e\}.\]
The admissible set \(E_2\) of 13 nondegenerate 2-edges from [7] is:
\[\begin{align} E_2 = \{ &(01,2;35,4),\;(01,3;45,2),\;(02,1;34,5),\;(02,3;14,5),\;(03,1;25,4),\\ &(04,3;15,2),\;(04,5;12,3),\;(05,3;24,1),\;(05,4;23,1),\;(13,0;24,5),\\ &(14,2;35,0),\;(15,4;23,0),\;(25,1;34,0)\}. \end{align}\]
We now add the half-row-degenerate 3-edge
\[e_3 = \{(01,4),\;(01,5),\;(23,1)\}.\]
Let \(E_3 = \{e_3\}\). We claim that \(G = (S,T,E_1 \cup E_2 \cup E_3)\) is generalized cycle-free.
We verify the three conditions of Definition 3.1.
Simplicity Condition (S)
The cells of \(e_3\) are \((01,4)\), \((01,5)\), and \((23,1)\).
- \((01,4)\): \(4 \notin \{0,1\}\) so not in \(E_1\). It is not a half of any 2-edge in \(E_2\) (the only 2-edges involving row 01 are \((01,2;35,4)\) and \((01,3;45,2)\), which use columns 2 and 3 respectively). Hence it is free. - \((01,5)\): \(5 \notin \{0,1\}\), not in \(E_1\); not in \(E_2\) (no 2-edge uses (01,5)). Free. - \((23,1)\): \(1 \notin \{2,3\}\), not in \(E_1\); the 2-edges involving row 23 are \((23,0)\) from \((15,4;23,0)\) and \((23,1)\) is not in \(E_2\). Free.
All three are distinct and disjoint from \(E_1\) and \(E_2\). Thus (S) holds.
2-edges All 2-edges in \(E_2\) are known to be alive from [7]. Adding \(e_3\) does not affect their opposite cells except possibly creating new occupied cells. We check each:
- For \((01,2;35,4)\): opposite cells \((01,4)\) and \((35,2)\). \((01,4)\) is now a half of \(e_3\) (occupied), \((35,2)\) is not occupied (row 35 = \(\{3,5\}\), col 2 not in \(\{3,5\}\), and not in \(E_2\)). So at most one occupied. Alive. - For \((01,3;45,2)\): opposite cells \((01,2)\) and \((45,3)\). \((01,2)\) is unoccupied (not in \(E_1\) or \(E_2\)), \((45,3)\) is unoccupied. Alive. - Others are symmetric or unaffected because their opposite cells do not include \((01,4),(01,5),(23,1)\). Thus all 2-edges remain alive.
The 3-edge \(e_3\) \(e_3\) is half-row-degenerate with \(i=01\), \(j=4\), \(l=5\), \(p=23\), \(q=1\). Its two opposite pairs are:
\[P_1 = \{(i,q),\;(p,j)\} = \{(01,1),\;(23,4)\},\] \[P_2 = \{(i,q),\;(p,l)\} = \{(01,1),\;(23,5)\}.\]
- \((01,1)\): \(1 \in \{0,1\}\) so in \(E_1\) (occupied). - \((23,4)\): \(4 \notin \{2,3\}\) so not in \(E_1\); not in \(E_2\) (no 2-edge uses (23,4)); not in \(E_3\). Unoccupied. - \((23,5)\): \(5 \notin \{2,3\}\) so not in \(E_1\); not in \(E_2\); unoccupied.
Thus \(P_1\) is not fully occupied (since \((23,4)\) free), and \(P_2\) is not fully occupied (since \((23,5)\) free). Hence zero opposite pairs are fully occupied, so \(e_3\) is alive (since at most one is required).
We must check for every 2-edge \((i,j;p,q) \in E_2\) and every \((k,l)\) with \(k \notin \{i,p\}\), \(l \notin \{j,q\}\) that the five cells \[(k,l),\;(k,j),\;(k,q),\;(i,l),\;(p,l)\] are not all occupied. Adding \(e_3\) introduces three new occupied cells: \((01,4),(01,5),(23,1)\). The only potential danger is if a 2-edge’s fixed cells include these. A systematic check (representative cases):
- For \((01,2;35,4)\): \(i=01,j=2,p=35,q=4\). The five cells involve \((01,l)\) and \((35,l)\). To have \((01,l)\) occupied by \(e_3\), we would need \(l = 4\) or \(5\). But \(l \notin \{j,q\} = \{2,4\}\), so \(l\) cannot be 4. Could \(l=5\)? Then \((35,5)\): \(5 \in \{3,5\}\) so in \(E_1\), and \((k,2),(k,4)\) would need to be occupied. No choice of \(k\) makes all five occupied (e.g., \(k=23\) gives \((23,5)\) free). Hence safe.
- For other 2-edges, the new cells \((01,4),(01,5)\) appear only in rows 01 and 23, and the forbidden configuration requires both \((i,l)\) and \((p,l)\) to be occupied. A direct case check (omitted for brevity, but exhaustive in the computational verification) shows no violation.
Thus Condition (iii) holds.
We must check for the 3-edge \(e_3 = (01,4;01,5;23,1)\) and every distinct cell \((k,l)\) with \[k \notin \{01,23,01\} = \{01,23\},\qquad l \notin \{4,5,1\}\] that the seven cells \[(k,4),\;(k,l),\;(k,5),\;(k,1),\;(01,l),\;(23,l),\;(01,l)\] are not all occupied. (Note \((01,l)\) appears twice ¨C duplicates allowed.)
Since \(l \notin \{1,4,5\}\), the possible \(l\) are \(0,2,3\). Also \(k\) is any row other than 01 or 23, i.e., \(k \in \{02,03,04,05,12,13,14,15,24,25,34,35,45\}\).
We examine each \(l\):
- \(l = 0\): The cells are \((k,4),(k,0),(k,5),(k,1),(01,0),(23,0),(01,0)\). \((01,0)\) is in \(E_1\) (occupied). \((23,0)\) is a half of 2-edge \((15,4;23,0)\), so occupied. To have all occupied, we would need \((k,4),(k,0),(k,5),(k,1)\) all occupied. But for any \(k \neq 01,23\), at least one of these is free (e.g., \(k=02\): \((02,4)\) free because \(4 \notin \{0,2\}\) and not in \(E_2\)). Hence impossible.
- \(l = 2\): Cells: \((k,4),(k,2),(k,5),(k,1),(01,2),(23,2),(01,2)\). \((01,2)\) is a half of 2-edge \((01,2;35,4)\), so occupied. \((23,2)\) is in \(E_1\) (occupied). Need \((k,4),(k,2),(k,5),(k,1)\) all occupied. For \(k=03\): \((03,4)\) is free (not in \(E_1\), not in \(E_2\)). Fail.
- \(l = 3\): Cells: \((k,4),(k,3),(k,5),(k,1),(01,3),(23,3),(01,3)\). \((01,3)\) is a half of 2-edge \((01,3;45,2)\), so occupied. \((23,3)\) is in \(E_1\) (occupied). Need \((k,4),(k,3),(k,5),(k,1)\) all occupied. For \(k=04\): \((04,3)\) is a half of 2-edge \((04,3;15,2)\), so occupied; \((04,4)\) is in \(E_1\) (since \(4 \in \{0,4\}\)); \((04,5)\) is in \(E_2\) (from \((04,5;12,3)\)), so occupied; but \((04,1)\) is free (\(1 \notin \{0,4\}\) and not in \(E_2\) or \(E_3\)). So fails.
Thus no \((k,l)\) makes all seven occupied. Condition (iv) holds.
Since all conditions are satisfied, \(G\) is generalized cycle-free.
Theorem 4. For \(m = 15\), \(n = 6\), \[z_{3A}(15,6) \ge 44 \qquad\text{and}\qquad \operatorname{BSR}(15,6) \ge 44.\] In particular, the lower bound for \(\operatorname{BSR}(15,6)\) is improved from 43 to 44.
Proof. The graph \(G = (S,T,E_1 \cup E_2 \cup E_3)\) defined above satisfies: - \(|E_1| = z(15,6) = 30\). - \(|E_2| = 13\). - \(|E_3| = 1\) (the half-degenerate 3-edge \(\{(01,4),(01,5),(23,1)\}\)). - By the verification above, \(G\) is generalized cycle-free (Definition 1) and satisfies the simplicity condition (S).
Applying Theorem 1, the associated triply simple biquadratic form \(P_G\) satisfies \[\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3| = 30 + 13 + 1 = 44.\] Since \(\operatorname{BSR}(15,6)\) is the maximum SOS rank over all \(15 \times 6\) biquadratic forms, we have \[\operatorname{BSR}(15,6) \ge 44.\] By definition, \(z_{3A}(15,6) \ge |E_1|+|E_2|+|E_3| = 44\). This improves the previous known bound \(z_L(15,6) \ge 43\). ◻
This is an explicit application of a 3-edge (half-degenerate) to improve a lower bound for \(\operatorname{BSR}(m,n)\). It demonstrates that the extended framework with half-degenerate 3-edges is not only theoretically sound but also practically useful. The same method may yield further improvements for larger parameters, such as \(21 \times 7\) and \(28 \times 8\), by searching for suitable half-degenerate 3-edges in the available cells of the known constructions.
We have extended the augmented bipartite graph framework to include \(3\)-edges¡ªtriples of cells representing squares of three-term bilinear forms. The main challenge was to define suitable generalized cycle-free conditions that are purely combinatorial yet sufficient to guarantee that the SOS rank of the associated triply simple biquadratic form equals the total number of edges. This was achieved in Definition 1, which carefully distinguishes between occupation by \(1\)/\(2\)-edges and occupation by \(3\)-edges in Condition (iii), and introduces Condition (iv) to handle configurations involving \(3\)-edges.
The main theoretical result (Theorem 1) establishes that for any generalized cycle-free augmented bipartite graph \(G\) satisfying the simplicity condition (S), \[\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|.\] This provides a combinatorial sufficient condition for irreducibility of triply simple biquadratic forms.
As concrete applications, we constructed two explicit examples:
A \(10 \times 5\) graph using a column-fully-degenerate \(3\)-edge, showing \[z_{3L}(10,5) \ge 27 \quad\text{and}\quad \operatorname{BSR}(10,5) \ge 27,\] which separates \(z_{3L}(10,5)\) from \(z_L(10,5)=26\).
A \(15 \times 6\) graph using a half-row-degenerate \(3\)-edge, showing \[z_{3A}(15,6) \ge 44 \quad\text{and}\quad \operatorname{BSR}(15,6) \ge 44,\] improving the previous lower bound of \(43\).
These are the first explicit applications of \(3\)-edges (both fully degenerate and half-degenerate) to obtain improved lower bounds for \(\operatorname{BSR}(m,n)\).
The framework opens several directions for future research:
Exact values for \(z_{3L}(m,n)\) and \(z_{3A}(m,n)\): Determine whether the lower bounds obtained in this paper are sharp. In particular, \[z_{3L}(10,5) = 27,\qquad z_{3A}(15,6) = 44,\qquad z_{3L}(15,6) = \;?\] The latter requires investigating whether a half-degenerate \(3\)-edge can be added to a \(15 \times 6\) graph while keeping \(|E_1| = z(15,6)=30\).
Asymptotic behavior: The classical Zarankiewicz number satisfies \(z(m,n) = O(mn^{1/2} + n)\). Does the introduction of \(2\)-edges and \(3\)-edges lead to a strictly larger asymptotic order for \(z_{3A}(m,n)\) or \(z_{3L}(m,n)\)? Or does the same \(O(mn^{1/2})\) upper bound persist?
Higher-order edges: The natural next step is to consider \(k\)-edges for \(k \ge 4\), representing squares of \(k\)-term bilinear forms. This would require defining generalized cycle-free conditions for \(k\)-uniform hypergraphs, potentially connecting to extremal hypergraph theory (e.g., \(C_4\)-free conditions in \(k\)-uniform hypergraphs).
Necessity vs. sufficiency: The generalized cycle-free conditions are sufficient for irreducibility but not necessary. Characterizing the exact combinatorial conditions that determine the SOS rank remains an open problem.
Computational search: Systematic computational searches for larger parameters (e.g., \(21 \times 7\), \(28 \times 8\)) using the incidence graphs of \(K_7\) and \(K_8\) may yield further improvements by adding suitable half-degenerate or fully degenerate \(3\)-edges.
The interplay between SOS representations of biquadratic forms and extremal bipartite graph theory, initiated in [3] and extended here to \(3\)-edges, reveals a rich structure that merits further exploration. We hope that the concepts of \(z_{3A}(m,n)\) and \(z_{3L}(m,n)\) will provide a productive framework for future investigations.
Acknowledgement This work was partially supported by Research Center for Intelligent Operations Research, The Hong Kong Polytechnic University (4-ZZT8), the National Natural Science Foundation of China (Nos. 12471282 and 12131004), and Jiangsu Provincial Scientific Research Center of Applied Mathematics (Grant No. BK20233002).
Data availability No datasets were generated or analysed during the current study.
Conflict of interest The authors declare no conflict of interest.
Jiangsu Provincial Scientific Research Center of Applied Mathematics, Nanjing 211189, China. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong. (maqilq@polyu.edu.hk)↩︎
School of Mathematical Sciences, Beihang University, Beijing 100191, China. (chunfengcui@buaa.edu.cn)↩︎
School of Mathematics, Southeast University, Nanjing 211189, China. Nanjing Center for Applied Mathematics, Nanjing 211135, China. Jiangsu Provincial Scientific Research Center of Applied Mathematics, Nanjing 211189, China.
(yi.xu1983@hotmail.com)↩︎