Strict State Hierarchies for Graph Homomorphism Polynomials

We prove that the distinguishing power of the full graph homomorphism polynomial increases strictly at every state number. For each q ≥ 1, we construct arbitrarily large finite families of graphs with the same q-state polynomial and the same Tutte polynomial, but pairwise distinct (q+1)-state polynomials even when all vertex activities are set to one. The graphs can simultaneously be chosen bipartite and 2-connected, with arbitrarily large girth, treewidth exactly q+1, and maximum average degree arbitrarily close to two. The construction uses even and odd permutation gadgets whose conditional partition functions agree whenever two terminal states coincide. A diagonal specialization proves that their difference is nonzero at the next state number. Gluing several copies yields an explicit nonnegative factorization of successive partition-function differences. These results establish Markström's fixed-state collision conjecture and give unbounded refinement within Tutte equivalence classes. We also construct witnesses of any prescribed vertex connectivity at least two.