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

At least 6 years old · documented by

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 f∗f^{*} 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=nH−jk_\mathcal{H}=n_\mathcal{H}-j for j≥3j\geq 3, then

sg=∑q=0jαq(∑S⊆V(H)∣S∣=q∏h∈Sxgh)for g∈V(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 f∗f^{*}. 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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.