Subexponential mixing for partition chains on grid-like graphs

Alan Frieze, Wesley Pegden

We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to hav…