The general sparse sum-of-squares certificate conjecture for Vizing's conjecture

From papers

Let G\mathcal{G} and H\mathcal{H} be the graph objects used in the paper's polynomial model, with vertex sets V(G)V(\mathcal{G}) and V(H)V(\mathcal{H}), parameters nGn_\mathcal{G} and nHn_\mathcal{H}, and kGk_\mathcal{G} and kHk_\mathcal{H}. Let xghx_{gh} be the associated polynomial variables, let ff^{*} be the target polynomial, and let jj-sos certificate mean a sum-of-squares certificate of the indicated degree. General sparse certificate conjecture. If kG=nGk_\mathcal{G}=n_\mathcal{G} and kH=nHjk_\mathcal{H}=n_\mathcal{H}-j for j3j\geq 3, then

sg=q=0jαq(SV(H)S=qhSxgh)for gV(G),s_g=\sum_{q=0}^{j}\alpha_q\left(\sum_{\substack{S\subseteq V(\mathcal{H})\\|S|=q}}\prod_{h\in S}x_{gh}\right)\quad\text{for }g\in V(\mathcal{G}),

where the αq\alpha_q solve a certain system of polynomial equations, gives a jj-sos certificate of ff^{*}. The claim is motivated by certificates established for the preceding cases, but the paper presents it as an expected generalization rather than a proved result.

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

Elisabeth Gaar, Daniel Krenn, Susan Margulies and Angelika Wiegele, “An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture”, arXiv:1901.10288 (2019).

Solutions 0

No solutions have been posted yet.