Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids

Fehrenbach Johannes and Rüschendorf Ludger

Statistics & Risk Modeling, 2004, vol. 22, issue 2, 109-130

Abstract: In this paper we establish that the natural single point update Markov chain (also known as Glauber dynamics) for counting the number of Euler orientations of 2-dimensional Cartesian grids is rapidly mixing. This extends a result of Luby, Randall, and Sinclair (2001) who consider the case where orientations in the boundary are fixed. Similarly, we also obtain a rapid mixing result for the 3-colouring of rectangular Cartesian grids without fixing the boundaries. The proof uses path coupling and comparison to related Markov chains which allow additional transitions and which can be analysed directly.

Date: 2004
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1524/stnd.22.2.109.49126 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:strimo:v:22:y:2004:i:2/2004:p:109-130:n:2

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/strm/html

DOI: 10.1524/stnd.22.2.109.49126

Access Statistics for this article

Statistics & Risk Modeling is currently edited by Robert Stelzer

More articles in Statistics & Risk Modeling from De Gruyter
Bibliographic data for series maintained by Peter Golla ().