{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T14:10:49Z","timestamp":1791641449311,"version":"4.3.4"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps.The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has O(n log(n)) mixing time for triangle-free $\\Delta$-regular graphs if k colors are used, where $k\\geq (2-\\eta)\\Delta$, for some small positive constant $\\eta$. This is the first proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of k in the range $k\\leq 2\\Delta$.<\/jats:p>","DOI":"10.1137\/s0097539700372708","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1962-1975","source":"Crossref","is-referenced-by-count":20,"title":["An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings"],"prefix":"10.1137","volume":"30","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Catherine","family":"Greenhill","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"Susanne Albers, Michael Mitzenmacher, Average\u2010case analyses of first fit and random fit bin packing, ACM, New York, 1998, 290\u201329999h:68070"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-25.3.564"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"D. Aldous,\n                      Random walks on finite groups and rapidly mixing Markov chains\n                      , in S\u00e9minaire de Probabilit\u00e9s XVII 1981\/1982, Lecture Notes in Math. 986, A. Dold and B. Eckmann, eds., Springer\u2010Verlag, New York, 1983, pp. 243\u2013297.","DOI":"10.1007\/BFb0068322"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"R. Bubley and M. Dyer,\n                      Path coupling: A technique for proving rapid mixing in Markov chains\n                      , in 38th Annual Symposium on Foundations of Computer Science, IEEE, Los Alamitos, 1997, pp. 223\u2013231.","DOI":"10.1109\/SFCS.1997.646111"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798338175"},{"key":"R6","first-page":"0","volume":"4","author":"Chung F.","year":"1997","journal-title":"Electron. J. Combin."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"E. G. Coffman, D. S. Johnson, P. W. Shor, and R. R. Weber,\n                      Markov chains, computer proofs and average\u2010case analysis of best fit bin packing\n                      , in 25th Annual Symposium on the Theory of Computing, ACM, New York, 1993, pp. 412\u2013421.","DOI":"10.1145\/167088.167203"},{"key":"R8","unstructured":"Artur Czumaj, Przemka Kanarek, Miroslaw Kutylowski, Krzysztof Lory\u015b, Delayed path coupling and generating random permutations via distributed stochastic processes, ACM, New York, 1999, 271\u20132802000j:68145"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034968224"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1071"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Martin Dyer, Catherine Greenhill, Random walks on combinatorial objects, London Math. Soc. Lecture Note Ser., Vol. 267, Cambridge Univ. Press, Cambridge, 1999, 101\u20131362000h:60073","DOI":"10.1017\/CBO9780511721335.005"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1590"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0919"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"L. Lov\u2019 asz and P. Winkler, Efficient stopping rules for Markov chains, in 27th Annual Symposium on the Theory of Computing, ACM, New York, 1995, pp. 76\u201382.","DOI":"10.1145\/225058.225086"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz, Peter Winkler, Mixing times, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 41, Amer. Math. Soc., Providence, RI, 1998, 85\u201313399h:60138","DOI":"10.1090\/dimacs\/041\/06"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1063\/1.533199"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.58.86"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700372708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:16Z","timestamp":1787336416000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700372708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539700372708"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700372708","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}