| The switch chain is a well-known Markov chain for sampling directed graphs with a given degree sequence. Ryser (1963) used switches to study classes of 0-1 matrices. Rao, Jana and Bandyopadhyay (1996) introduced the corresponding Markov chain and showed that it is not always ergodic for general degree sequences. However, for regular directed graphs the switch chain is ergodic with uniform stationary distribution. Cooper, Dyer and Greenhill (2007) showed that the analogous Markov chain for regular undirected graphs is rapidly mixing, using a multicommodity flow argument. I will discuss my extension of this argument to the directed setting, in which several complications emerge which are not present in the undirected case. The result is a polynomial bound on the mixing time of the switch chain for regular directed graphs of any degree. Finally, the extension to general (irregular) degree sequences will be considered. |
|