Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
Date Issued
2009
Date
2009
Author(s)
Kuo, Ching-Chen
Abstract
Let G be an n-node graph with maximum degree △. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that △≧d log_2 n holds for some sufficiently large constant d. We add the following new results along this direction, where ε can be any constant with 0 < ε < 1.. Let α≒1.645 be the root of (1-e^{{-1}/x})^2+ 2x^{-1/x}=2. If G is regular and bipartite and k≥(α+ε) △， then the mixing time of the Glauber dynamics for G is O(nlog n)..Let β≒1.763 be the root of x=e^{1/x}. If the numberf common neighbors for any two adjacent nodes of G is at most ε^{1.5}Delta/360e且k≥(1+ε)β△， then the mixing time of the Glauber dynamics is O(nlog n).
Subjects
Markov chai
random coloring
graph
Glauber dynamics
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922074-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):e6920773a583594caffb967589cd5251