# On Sampling Colorings of Bipartite Graphs

On Sampling Colorings of Bipartite Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 IMSc - Institute of Mathematical Sciences India

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, \emphalmost 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 On-k vertices in a single transition step. This kind of exponential time mixing is called \emphtorpid 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.

Keywords : Graph colorings Markov chains Analysis of algorithms

Autor: ** R. Balasubramanian - C.R. Subramanian - **

Fuente: https://hal.archives-ouvertes.fr/