%0 Journal Article
%T On Sampling Colorings of Bipartite Graphs
%A R. Balasubramanian
%A C. R. Subramanian
%J Discrete Mathematics & Theoretical Computer Science
%D 2006
%I Discrete Mathematics & Theoretical Computer Science
%X 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/k 2 (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.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/448