The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

References

  1. D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation, available at http://stat-www.berkeley.edu/users/aldous/RWG/book.html. Math. Review number not available.
  2. I. Benjamini, O. Häggström and E. Mossel. On random graph homomorphisms into Z. J. Combinatorial Th. (B) 78 no. 1 (2000), 86--114. Math. Review 2001c:60135
  3. B. Bollobás. Extremal Graph Theory. Academic Press, New York, 1978. Math. Review 80a:05120
  4. B. Bollobás. Modern Graph Theory. Springer, New York, 1998. Math. Review 99h:05001
  5. B. Bollobás. Random Graphs. Cambridge University Press, Cambridge, 2001. Math. Review 2002j:05132
  6. C. Borgs, J. Chayes, A. Frieze, J. Kim, P. Tetali, E. Vigoda, V. Vu. Torpid Mixing of some Monte Carlo Markov Chain algorithms in Statistical Physics. Proc. IEEE FOCS '99 218--229. Math. Review MR1917562
  7. R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. Proc. IEEE FOCS '97 223--231. Math. Review number not available.
  8. H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23 (1952), 493--507. Math. Review 15,241c
  9. R. Diestel. Graph Theory. Springer, New York, 2005. Math. Review 2006e:05001
  10. M. Dyer, A. Frieze and M. Jerrum. On counting independent sets in sparse graphs. SIAM J. Comp. 31 (2002), 1527--1541. Math. Review 2003h:68043
  11. M. Dyer, C. Greenhill, M. Molloy. Very rapid mixing of the Glauber dynamics for proper colorings on bounded degree graphs. Random Struc. & Alg. 20 (2002), 98--114. Math. Review 2002i:60131
  12. D. Galvin. On homomorphisms from the Hamming cube to Z. Isr. J. Math. 138 (2003), 189--213. Math. Review 2005b:05158
  13. D. Galvin and D. Randall. Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus. Proc. ACM--SIAM SODA '07 376--384. No Math. Review number available.
  14. D. Galvin and P. Tetali. Slow mixing of Glauber dynamics for the hard-core model on the Hamming cube. Random Structures & Alg. 28 (2006) 427-443. Math. Review 2007a:05127
  15. M. Jerrum. A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Struc. & Alg. 7 (1995), 157--165. Math. Review 97f:68070
  16. M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved. Proc. ACM STOC '88 235--243. No Math. Review number available.
  17. J. Kahn. Range of cube-indexed random walk. Isreal J. Math. 124 (2001) 189--201. Math. Review 2002k:60173
  18. A. Korshunov and A. Sapozhenko. The number of binary codes with distance 2. Problemy Kibernet. 40 (1983), 111--130. (Russian) Math. Review 85a:94026
  19. T. Łuczak and E. Vigoda. Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings. J. Discrete Alg. 3 no. 1 (2005), 92--100. Math. Review 2006d:68268
  20. M. Molloy. Very rapidly mixing Markov chains for 2Δ-colourings and for independent sets in a 4-regular graph. Random Struc. & Alg. 18 (2001), 101--115. Math. Review 2002b:68036
  21. R. Montenegro and P. Tetali. Mathematical aspects of mixing times in Markov chains. Foundations and Trends in Theoretical Computer Science 1 no. 3 (2006), 237--354. Math. Review number not available.
  22. D. Randall. Mixing. Proc. IEEE FOCS '03 4--15. Math. Review number not available.
  23. D. Randall. Personal communication. Math. Review number not available.
  24. J. Salas and A. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Stat. Phys. 86 (1997), 551--579. Math. Review 98b:82020
  25. A. Sapozhenko. On the number of connected subsets with given cardinality of the boundary in bipartite graphs. Metody Diskret. Analiz. 45 (1987), 42--70. (Russian) Math. Review 89i:05168
  26. A. A. Sapozhenko. The number of antichains in ranked partially ordered sets. Diskret. Mat. 1 (1989), 74--93. (Russian; translation in Discrete Math. Appl. 1 no. 1 (1991), 35--58) Math. Review 91h:06006
  27. A. Sokal. Chromatic Polynomials, Potts Models and All That. Physica A279 (2000), 324--332. Math. Review number not available.
  28. A. Sokal. A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models. Markov Process. Related Fields 7 (2001), 21--38. Math. Review MR1835744
  29. E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys. 41 (2000), 1555--1569. Math. Review 2001a:60085
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.