Bipartite graph covers reveal new patterns in independent set counts
Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers
Discrete Mathematics
Summary
This paper looks at ways to count different groups of disconnected points in complex graph structures built from simpler pieces. The authors prove that for certain kinds of graphs, the simplest way of stacking copies maximizes these counts, confirming a long-standing guess. They also identify precise conditions when these counts match or differ, revealing deeper structural patterns. Their work connects these counting problems to coloring puzzles on graphs and uses computer proof tools to ensure correctness.
What this means in practice
- •For combinatorial optimization teams: Improve algorithms for counting independent sets in structured bipartite graphs by leveraging new rigidity and coefficient bounds.
- •For network reliability engineers: Use new insights into independent sets in bipartite graph covers to better model and analyze redundancy and fault tolerance.
A theory result. No direct application yet.
Authors
Yusuke Watanabe
Abstract
Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde 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\ge2$ 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.