{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:32:34Z","timestamp":1787322754404,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M004953\/1"],"award-info":[{"award-number":["EP\/M004953\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S016562\/1"],"award-info":[{"award-number":["EP\/S016562\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham, and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in an arbitrary graph. Finally, we give exact counting algorithms for three classes.<\/jats:p>","DOI":"10.1137\/18m1172910","type":"journal-article","created":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T14:51:01Z","timestamp":1562079061000},"page":"1146-1174","source":"Crossref","is-referenced-by-count":2,"title":["Counting Perfect Matchings and the Switch Chain"],"prefix":"10.1137","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2018-0374","authenticated-orcid":true,"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiko","family":"Muller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02352694"},{"key":"atypb2","unstructured":"O. Blumberg,\n                      Permutations with Interval Restrictions\n                      , Ph.D. thesis, Stanford University, Palo Alto, CA, 2012."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00389-5"},{"key":"atypb5","first-page":"50","author":"Broder A. Z.","year":"1986","journal-title":"New York"},{"key":"atypb6","first-page":"2","author":"Broder A. Z.","year":"1988","journal-title":"Proceedings of 20th Annual ACM Symposium on Theory of Computing"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90234-7"},{"key":"atypb11","first-page":"195","author":"Diaconis P.","year":"2001","journal-title":"OH"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2822322"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.5802\/afst.1469"},{"key":"atypb14","first-page":"190","author":"Dyer M.","year":"2018","journal-title":"Switzerland"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00394-9"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Ann. Discrete Math. 57, North-Holland, Amsterdam, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"145","key":"atypb18","first-page":"183","volume":"2005","author":"Habib M.","journal-title":"Discrete Appl. Math."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20006"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"atypb21","first-page":"101","author":"Jerrum M.","year":"1992","journal-title":"New York"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1063\/1.1703953"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth - Computations and Approximations\n                      , Lecture Notes in Comput. Sci. 842, Springer, Berlin, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"atypb26","unstructured":"E. K\u00f6hler,\n                      Graphs without Asteroidal Triples\n                      , Ph.D. thesis, Technische Universit\u00e4t Berlin, Berlin, 1999."},{"key":"atypb27","unstructured":"E. Lawler,\n                      Combinatorial Optimization - Networks and Matroids\n                      , Holt, Rinehart, and Winston, New York, 1976."},{"key":"atypb28","unstructured":"D. A. Levin, Y. Peres, and E. L. Wilmer,\n                      Markov Chains and Mixing Times\n                      , American Mathematical Society, Providence, RI, 2006."},{"key":"atypb29","unstructured":"J. Matthews,\n                      Markov Chains for Sampling Matchings\n                      , Ph.D. thesis, Edinburgh University, Edinburgh, 2008."},{"key":"atypb30","first-page":"296","author":"Okamoto Y.","year":"2010","journal-title":"Berlin"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90047-0"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"D. \u0160tefankovi\u010d, E. Vigoda, and J. Wilmes,\n                      On counting perfect matchings in general graphs\n                      , in Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN 2018), Lecture Notes in Comput. Sci. 10807, Springer, Cham, Switzerland, pp. 873-885, 2018.","DOI":"10.1007\/978-3-319-77404-6_63"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2298\/AADM100812027V"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1172910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:14Z","timestamp":1787318714000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1172910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1172910"],"URL":"https:\/\/doi.org\/10.1137\/18m1172910","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}