On Sampling Colorings of Bipartite Graphs

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 O(n/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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.17-30
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00961100
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:30:01
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:34:34

Fichier

dm080102.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00961100, version 1

Collections

Citation

R. Balasubramanian, C.R. Subramanian. On Sampling Colorings of Bipartite Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.17-30. 〈hal-00961100〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

173