Conjecture on rank-one solutions for edge sums in the max-cut SDP
Conjecture on rank-one solutions for edge sums in the max-cut SDP
Let and be two graphs with vertex sets
Let and be the primal-dual solution pairs to the max-cut SDPs on and , respectively. Let be the edge sum of and , with common edge , and let be the primal and dual optimal solutions for . Edge-sum conjecture. The following statements are equivalent: (1) and are rank-one matrices and agree on the intersection; (2) for some common choice of signs on the off-diagonal entries, the dual solution has the form
The first two matrices are ; is and is , while in the final matrix the entries occur in positions and (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
Sign in to submit a solution.
No solutions have been posted yet.