Geodesic
Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
Pieter Kleer1 ; Viresh Patel2 ; Fabian Stroh2
1Max Planck Institute for Informatics
2University of Amsterdam, Korteweg-de Vries Institute (KdVI)
The electronic journal of combinatorics, Tome 27 (2020) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider the irreducibility of switch-based Markov chains for the approximate uniform sampling of Hamiltonian cycles in a given undirected dense graph on $n$ vertices. As our main result, we show that every pair of Hamiltonian cycles in a graph with minimum degree at least $n/2+7$ can be transformed into each other by switch operations of size at most 10, implying that the switch Markov chain using switches of size at most 10 is irreducible. As a proof of concept, we also show that this Markov chain is rapidly mixing on dense monotone graphs.
DOI : 10.37236/9503
Classification : 05C45, 05C42, 60J10
Mots-clés : irreducibility of switch-based Markov chains, undirected dense graph

Pieter Kleer  1   ; Viresh Patel  2   ; Fabian Stroh  2

1 Max Planck Institute for Informatics
2 University of Amsterdam, Korteweg-de Vries Institute (KdVI) 
@article{10_37236_9503,
     author = {Pieter Kleer and Viresh  Patel and Fabian  Stroh},
     title = {Switch-based {Markov} chains for sampling {Hamiltonian} cycles in dense graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/9503},
     zbl = {1453.05056},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9503/}
}
TY  - JOUR
AU  - Pieter Kleer
AU  - Viresh  Patel
AU  - Fabian  Stroh
TI  - Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9503/
DO  - 10.37236/9503
ID  - 10_37236_9503
ER  - 
%0 Journal Article
%A Pieter Kleer
%A Viresh  Patel
%A Fabian  Stroh
%T Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9503/
%R 10.37236/9503
%F 10_37236_9503
Pieter Kleer; Viresh  Patel; Fabian  Stroh. Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9503

Cité par Sources :