Rapid mixing of the switch Markov chain for 2-class joint degree matrices

The switch Markov chain has been extensively studied as the most natural Markovchain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work westudy the problem of uniformly sampling graphs for which, in addition to the degree sequence, jointdegree constraints are given. These constraints specify how many edges there should be between twogiven degree classes (i.e., subsets of nodes that all have the same degree). Although the problem wasformalized over a decade ago, and despite its practical significance in generating synthetic networktopologies, small progress has been made on the random sampling of such graphs. In the case of onedegree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodeshave the same degree), but beyond this very little is known. We fully resolve the case of two degreeclasses, by showing that the switch Markov chain is always rapidly mixing. We do this by combininga recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al.[Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.