On Sampling Colorings of Bipartite Graphs
R. Balasubramanian, C. R. Subramanian
Abstract
We study the problem of efficiently sampling k-colorings of bipartite graphs. We show that a
class of markov chains cannot be used as efficient
samplers. Precisely, we show that, for any k,
6 ≤ k ≤ n{1/3-ε}, ε
> 0 fixed, almost every bipartite graph on n+n vertices is such that the mixing time of any
markov chain asymptotically uniform on its k-colorings is exponential in n/k2 (if it is allowed to
only change the colors of O(n/k) vertices in a
single transition step). This kind of exponential time mixing is
called torpid mixing. As a corollary, we show that there are
(for every n) bipartite graphs on 2n vertices with Δ(G) =
Ω(ln n) such that for every k, 6 ≤ k ≤ Δ/(6 ln Δ), each member of a large class
of chains mixes torpidly. While, for fixed k,
such negative results are implied by the work of CDF, our
results are more general in that they allow k
to grow with n. We also show that these
negative results hold true for H-colorings of
bipartite graphs provided H contains a
spanning complete bipartite subgraph. We also present explicit
examples of colorings (k-colorings or H-colorings) which admit 1-cautious chains that are
ergodic and are shown to have exponential mixing time. While, for
fixed k or fixed H,
such negative results are implied by the work of CDF, our
results are more general in that they allow k
or H to vary with n.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page