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

Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors

郭慶徵(Ching-Chen Kuo)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00953

摘要

給定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).

並列關鍵字

Markov chai ； random coloring ； graph ； Glauber dynamics

參考文獻

[1] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 223–231, 1997.

[2] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125–145, 2002.

[3] M. Dyer, A. Flaxman, A. Frieze, and E. Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structure and Algorithms, 29(4):450–465, 2006.

[4] M. Dyer and A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 579–587, 2001.

[5] M. Dyer, A. Frieze, T. P. Hayes, and E. Vigoda. Randomly coloring constant degree graphs. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 582–589, 2004.