Wagner's sum-of-squares conjecture for spanning-forest Rayleigh differences

Let G\mathcal G be a graph, and let ee and ff be distinct edges. Write G=F(G;y)G=F(\mathcal G;\mathbf y) for the generating polynomial of its spanning forests, and let S\mathscr S be the collection of sets SEefS\subseteq E-ef such that SefS\cup ef is contained in a cycle of G\mathcal G. For each SSS\in\mathscr S, let A(S)\mathscr A(S) be the collection of spanning forests AA such that AEefA\subseteq E-ef and SefCAefS\cup ef\subseteq C\subseteq A\cup ef for a unique cycle CC. Here yX=xXyx\mathbf y^X=\prod_{x\in X}y_x and ΔG{e,f}=GeGfGGef\Delta G\{e,f\}=G_eG_f-GG_{ef}. Wagner's sum-of-squares conjecture. For some choice of signs c(S,C)=±1c(S,C)=\pm1,

ΔG{e,f}=SSyS(AA(S)c(S,C)yAS)2.\Delta G\{e,f\}=\sum_{S\in\mathscr S}\mathbf y^S\left(\sum_{A\in\mathscr A(S)}c(S,C)\mathbf y^{A-S}\right)^2.

This identity would give a sum-of-squares certificate for the nonnegativity of the spanning-forest Rayleigh difference and hence imply that graphs are I\mathbf I-Rayleigh. The statement is presented as a conjecture in the source; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Alejandro Erickson, “Sums of squares and negative correlation for spanning forests of series parallel graphs”, arXiv:1008.3660 (2011).

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.