Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers
Abstract
Let G be a finite bipartite graph and let G̃ be an M-fold cover. We compare independent sets of G̃ with those of the trivial cover, consisting of M disjoint copies of G, after prescribing how many vertices are selected above each vertex of G. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For M≥2 and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of pGM−2 with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.
Related
- Exact three-component covers in 2-coloured random bipartite graphs
- Eventual Exactness and Rigidity for Abelian Covers of Groups
- A Higher dimensional log Riemann--Hurwitz inequality and rigidity of covers
- Rigidity of the period map up to finite covers
- Scaled Companion Linearizations for Coefficientwise Backward Stability
BibTeX
@misc{watanabe2026coefficientwise,
title = {{Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers}},
author = {Yusuke Watanabe},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14892},
eprint = {2610.14892},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14892},
}
RIS
TY - UNPB
TI - Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers
AU - Yusuke Watanabe
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14892
UR - https://arxiv.org/abs/2610.14892
AB - Let G be a finite bipartite graph and let G̃ be an M-fold cover. We compare independent sets of G̃ with those of the trivial cover, consisting of M disjoint copies of G, after prescribing how many vertices are selected above each vertex of G. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For M≥2 and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of p_G^M−2 with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.
ER -