The independent-set polynomial cover inequality for bipartite graphs

Let G=(V,E)G=(V,E) be a finite bipartite graph, let G~\tilde{G} be its MM-cover, and let p(G)=I independentvIxvp(G)=\sum_{I\text{ independent}}\prod_{v\in I}x_v be its multivariate independent-set polynomial. Extend the natural projection from G~\tilde{G} to GG to a ring homomorphism Π\Pi by mapping each indeterminate xvx_v to xΠ(v)x_{\Pi(v)}. For polynomials with nonnegative coefficients, write fgf\preceq g when every monomial coefficient of ff is at most the corresponding coefficient of gg. Independent-set polynomial cover inequality. For any bipartite graph GG and its MM-cover G~\tilde{G}, one has

Π(p(G~))p(G)M.\Pi\bigl(p(\tilde{G})\bigr)\preceq p(G)^M.

The inequality compares the projected independent sets of a cover with the independent sets in MM disjoint copies of the base graph. It was checked computationally for many examples, but no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Yusuke Watanabe, “A conjecture on independent sets and graph covers”, arXiv:1109.2445 (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.