Sampling Regular Graphs and a Peer-to-Peer Network

Source abstract

This paper has two parts. In the first part we consider a simple Markov chain for d -regular graphs on n vertices, where d = d(n) may grow with n . We show that the mixing time of this Markov chain is bounded above by a polynomial in n and d . In the second part of the paper, a related Markov chain for d -regular graphs on a varying number of vertices is introduced, for even constant d . This is a model for a certain peer-to-peer network. We prove that the related chain has mixing time which is bounded above by a polynomial in N , the expected number of vertices, provided certain assumptions are met about the rate of arrival and departure of vertices.