Geodesic
A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The switch chain is a well-known Markov chain for sampling directed graphs with a given degree sequence. While not ergodic in general, we show that it is ergodic for regular degree sequences. We then prove that the switch chain is rapidly mixing for regular directed graphs of degree $d$, where $d$ is any positive integer-valued function of the number of vertices. We bound the mixing time by bounding the eigenvalues of the chain. A new result is presented and applied to bound the smallest (most negative) eigenvalue. This result is a modification of a lemma by Diaconis and Stroock [Annals of Applied Probability 1991], and by using it we avoid working with a lazy chain. A multicommodity flow argument is used to bound the second-largest eigenvalue of the chain. This argument is based on the analysis of a related Markov chain for undirected regular graphs by Cooper, Dyer and Greenhill [Combinatorics, Probability and Computing 2007], but with significant extension required.
DOI : 10.37236/721
Classification : 05C20, 60J10
Mots-clés : regular degree sequences, switch chain, Markov chain for undirected regular graphs 
@article{10_37236_721,
     author = {Catherine Greenhill},
     title = {A polynomial bound on the mixing time of a {Markov} chain for sampling regular directed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/721},
     zbl = {1243.05095},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/721/}
}
TY  - JOUR
AU  - Catherine Greenhill
TI  - A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/721/
DO  - 10.37236/721
ID  - 10_37236_721
ER  - 
%0 Journal Article
%A Catherine Greenhill
%T A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/721/
%R 10.37236/721
%F 10_37236_721
Catherine Greenhill. A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/721

Cité par Sources :