The independent-set polynomial cover inequality for bipartite graphs

At least 14 years old · documented by

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 independent∏v∈Ixvp(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 f⪯gf\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.

References

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.