A counterexample to rapid mixing of the Ge-Štefankovič process
A counterexample to rapid mixing of the Ge-Štefankovič process
Ge and Stefankovic have recently introduced a novel two-variable graph polynomial. When specialised to a bipartite graphs G and evaluated at the point (1/2,1) this polynomial gives the number of independent sets in the graph. Inspired by this polynomial, they also introduced a Markov chain which, if rapidly mixing, would …