{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:53Z","timestamp":1787323013894,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>A joint degree matrix (JDM) specifies the number of connections between nodes of given degrees in a graph, for all degree pairs, and uniquely determines the degree sequence of the graph. We consider the space of all balanced realizations of an arbitrary JDM, realizations in which the links between any two fixed-degree groups of nodes are placed as uniformly as possible. We prove that a swap Markov chain Monte Carlo algorithm in the space of all balanced realizations of an arbitrary graphical JDM mixes rapidly, i.e., the relaxation time of the chain is bounded from above by a polynomial in the number of nodes $n$. To prove fast mixing, we first prove a general factorization theorem similar to the Martin--Randall method for disjoint decompositions (partitions). This theorem can be used to bound from below the spectral gap with the help of fast mixing subchains within every partition and a bound on an auxiliary Markov chain between the partitions. Our proof of the general factorization theorem is direct and uses conductance based methods (Cheeger inequality).<\/jats:p>","DOI":"10.1137\/130929874","type":"journal-article","created":{"date-parts":[[2015,3,11]],"date-time":"2015-03-11T11:26:14Z","timestamp":1426073174000},"page":"481-499","source":"Crossref","is-referenced-by-count":12,"title":["A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix"],"prefix":"10.1137","volume":"29","author":[{"given":"P\u00e9ter L.","family":"Erd\u00f6s","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Istv\u00e1n","family":"Mikl\u00f3s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zolt\u00e1n","family":"Toroczkai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,11]]},"reference":[{"key":"atypb1","unstructured":"Y. Amanatidis, B. Green, and M. Mihail,\n                      Flexible models for complex networks\n                      , presented at Annual Conference on Discrete Mathematics, SIAM, Philadelphia, 2008; available online from http:\/\/www.cc.gatech.edu\/home\/mihail\/D.vita\/ARC2poster.ppt."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20155"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2008.62"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9323-9"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9569-3"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1214\/08-AAP558"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1198\/016214504000001303"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007978"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434243"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/060650544"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.10.012"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0010012"},{"key":"atypb14","first-page":"15","author":"Diaconis P.","year":"1995","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005980"},{"key":"atypb17","unstructured":"P.L. Erdo\u0308s, Z.S. Kiss, I. Miklo\u0301s, and L. Soukup,\n                      Constructing, Sampling and Counting Graphical Realizations of Restricted Degree Sequences,\n                      arXiv:1301.7523v2, 2013."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"T. Feder, A. Guetz, M. Mihail, and A. Saberi,\n                      A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks\n                      , in Proceedings of FOCS'06, 2006, pp. 69-76.","DOI":"10.1109\/FOCS.2006.5"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M.K. Ganapathy,\n                      Robust Mixing\n                      , Ph.D. dissertation, University of Chicago, 2006.","DOI":"10.1007\/11830924_33"},{"key":"atypb20","first-page":"557","volume":"16","author":"Greenhill C.","year":"2011","journal-title":"Electron. J. Combin."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/2\/023012"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/39\/392001"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G"},{"key":"atypb26","unstructured":"Z. Kira\u0301ly,\n                      Recognizing Graphic Degree Sequences and Generating All Realizations\n                      , Technical report TR-2011-11, EGRES, 2012, pp. 1-11."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1026915617"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007352"},{"key":"atypb29","doi-asserted-by":"crossref","first-page":"P16","DOI":"10.37236\/3028","volume":"20","author":"Miklo\u0301s I.","year":"2013","journal-title":"Electron. J. Combin."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90048-0"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2006.30"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"},{"key":"atypb33","first-page":"3","volume":"17","author":"Stanton I.","year":"2012","journal-title":"ACM J. Exp. Algorithms"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130929874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:14Z","timestamp":1787319434000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130929874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130929874"],"URL":"https:\/\/doi.org\/10.1137\/130929874","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}