Diaconis, Graham and Holmes [8] studied the statistical applications of counting and sampling perfect matchings in certain classes of graphs. They proposed a simple Markov chain, called the switch chain here, to generate a matching almost uniformly at random for graphs in these classes. We examine these graph classes in detail, and show that they have a strong graph-theoretic rationale. We consider the ergodicity of the switch chain, and show that all the classes in [8] inherit their ergodicity from a larger class. We also study the computational complexity of the mixing time of the switch chain, and show that this has already been resolved for all but one of the classes in [8], that which Diaconis, Graham and Holmes called monotone graphs. We outline an approach to showing polynomial time convergence of the switch chain for monotone graphs. This is shown to rely upon an interesting, though unproven, conjecture concerning Hamilton cycles in monotone graphs.
Diaconis, Graham et Holmes [8] ont étudié les applications statistiques du comptage et de l’échantillonnage des appariements parfaits dans certaines classes de graphes. Ils ont proposé une chaîne de Markov simple, appelée ici la chaîne “switch”, pour engendrer aléatoirement un appariement presque uniforme pour les graphes appartenant à ces classes. Nous étudions ces classes en détail en les justifiant du point de vue de la théorie des graphes. Nous montrons que l’ergodicité des chaînes des classes de [8] se déduit de celle d’une classe plus large. Nous nous intéressons également à la complexité calculatoire du temps de mélange de la chaîne switch et nous la déterminons pour toutes les classes de [8] sauf une, celle correspondant aux graphes monotones de Diaconis, Graham et Holmes. Nous ébauchons une approche pour montrer une convergence en temps polynomial de la chaîne switch pour les graphes monotones. Elle dépend d’une conjecture intéressante mais non-prouvée concernant les cycles hamiltoniens des graphes monotones.
@article{AFST_2015_6_24_4_885_0,
author = {Dyer, Martin and M\"uller, Haiko},
title = {Graph classes and the switch {Markov} chain for matchings},
journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
pages = {885--933},
year = {2015},
publisher = {Universit\'e Paul Sabatier, Institut de Math\'ematiques},
address = {Toulouse},
volume = {Ser. 6, 24},
number = {4},
doi = {10.5802/afst.1469},
zbl = {1337.60171},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/afst.1469/}
}
TY - JOUR AU - Dyer, Martin AU - Müller, Haiko TI - Graph classes and the switch Markov chain for matchings JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2015 SP - 885 EP - 933 VL - 24 IS - 4 PB - Université Paul Sabatier, Institut de Mathématiques PP - Toulouse UR - http://geodesic.mathdoc.fr/articles/10.5802/afst.1469/ DO - 10.5802/afst.1469 LA - en ID - AFST_2015_6_24_4_885_0 ER -
%0 Journal Article %A Dyer, Martin %A Müller, Haiko %T Graph classes and the switch Markov chain for matchings %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2015 %P 885-933 %V 24 %N 4 %I Université Paul Sabatier, Institut de Mathématiques %C Toulouse %U http://geodesic.mathdoc.fr/articles/10.5802/afst.1469/ %R 10.5802/afst.1469 %G en %F AFST_2015_6_24_4_885_0
Dyer, Martin; Müller, Haiko. Graph classes and the switch Markov chain for matchings. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Numéro Spécial : Conférence “Talking Across Fields” du 24 au 28 mars 2014 à l’Institut de Mathématiques de Toulouse, Tome 24 (2015) no. 4, pp. 885-933. doi: 10.5802/afst.1469
Cité par Sources :