正則雙分圖與有限共鄰圖上之隨機著色

Abstract

給定G是一個有n個點，最大度數為△的圖。葛勞柏動態過程是一個在G的所有著色上執行的馬可夫鏈。葛勞柏動態過程目前已被證明出在各種不同圖上可以達到快速趨近。近幾年來的研究焦點著重在△≧d log2 n，d是某些足夠大的常數。本篇論文結果如下: 1.給定α≒1.645為(1-e^{{-1}/x})^2+ 2xe^{-1/x}=2之根。若G為正則雙分圖，且k≥(α+ε) △，則葛勞柏動態過程的結合時間為O(nlog n)。 2. 給定β≒1.763為x=e^{1/x}之根。若G上任二相鄰點的共同鄰居個數至多為ε^{1.5}Delta/360e且k≥(1+ε)β△，則葛勞柏動態過程的結合時間為O(nlog n)。

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. 1. Let α≒1.645 be the root of (1-e^{{-1}/x})^2+ 2x e^{-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). 2.Let β≒1.763 be the root of x=e^{1/x}. If the number of 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).