Vi studerar en enkel Markov kedja, omkopplaren kedja, på uppsättningen av alla perfekta matchningar i en bipartite graf. Denna Markov kedja föreslogs av Diaconis, Graham och Holmes som en möjlig strategi för ett urvalsproblem som uppstår i Statistik. Vi frågar: för vilka ärftliga klasser av grafer är Markov kedjan ergodic och för vilka är det snabbt blandning? Vi ger ett exakt svar på ergodicitetsfrågan och nära gränser för blandningsfrågan. Vi visar för första gången att blandningstiden för omkopplaren är polynom i fallet med monotona grafer, en klass som innehåller exempel på intresse i den statistiska inställningen.
I REF är det bevisat att den största ärftliga klassen av bipartit grafer där omkonfigurering grafen av perfekta matchningar med flips är ansluten är klassen av ackord bipartit grafer.
On the Switch Markov Chain for Perfect Matchings
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}