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

About 16 years old · traced to

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 S⊆E−efS\subseteq E-ef such that S∪efS\cup ef is contained in a cycle of G\mathcal G. For each S∈SS\in\mathscr S, let A(S)\mathscr A(S) be the collection of spanning forests AA such that A⊆E−efA\subseteq E-ef and S∪ef⊆C⊆A∪efS\cup ef\subseteq C\subseteq A\cup ef for a unique cycle CC. Here yX=∏x∈Xyx\mathbf y^X=\prod_{x\in X}y_x and ΔG{e,f}=GeGf−GGef\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}=∑S∈SyS(∑A∈A(S)c(S,C)yA−S)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.

References

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.