Conjecture on rank-one solutions for edge sums in the max-cut SDP

From papers

Let G1G_1 and G2G_2 be two graphs with vertex sets

V1={1,2,,m+1,m+2},V2={m+1,m+2,,n1,n}.V_1=\{1,2,\ldots,m+1,m+2\},\qquad V_2=\{m+1,m+2,\ldots,n-1,n\}.

Let (X1,S1)(X_1,S_1) and (X2,S2)(X_2,S_2) be the primal-dual solution pairs to the max-cut SDPs on G1G_1 and G2G_2, respectively. Let GG be the edge sum of G1G_1 and G2G_2, with common edge (m+1,m+2)(m+1,m+2), and let (X,S)(X^*,S^*) be the primal and dual optimal solutions for GG. Edge-sum conjecture. The following statements are equivalent: (1) X1X_1 and X2X_2 are rank-one matrices and agree on the intersection; (2) for some common choice of signs on the off-diagonal w1w_1 entries, the dual solution has the form

S=[S1000]+[000S2]14[00000w1±w100±w1w100000].S=\begin{bmatrix} S_1^* & 0 \\ 0 & 0 \end{bmatrix}+\begin{bmatrix} 0 & 0 \\ 0 & S_2^* \end{bmatrix}-\frac14\begin{bmatrix} 0&0&0&0\\0&w_1&\pm w_1&0\\0&\pm w_1&w_1&0\\0&0&0&0\end{bmatrix}.

The first two matrices are n×nn\times n; S1S_1 is (m+2)×(m+2)(m+2)\times(m+2) and S2S_2 is (nm)×(nm)(n-m)\times(n-m), while in the final matrix the w1w_1 entries occur in positions (m+1,m+1)(m+1,m+1) and (m+2,m+2)(m+2,m+2) (with the off-diagonal entries carrying the common sign). This conjecture concerns how rank-one primal solutions and the corresponding dual structure behave under an edge sum, extending the paper's results for vertex sums and special edge sums. Its resolution for general edge sums or larger clique sums is left as future work.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Daniel Hong, Hyunwoo Lee and Alex Wei, “Optimal solutions and ranks in the max-cut SDP”, arXiv:2109.02238 (2021).

Solutions 0

No solutions have been posted yet.