Approximating the degree sequence of two random graphs

Jefferson Elbert Simões, Daniel R. Figueiredo, Valmir C. Barbosa

Published 2016-01-11Version 1

In a seminal paper, McKay and Wormald proposed a framework for approximating the distribution of the degree sequence of an Erd\H{o}s-R\'enyi random graph by a sequence of independent random variables. We extend their framework to the case of two independent random graphs, giving similar bounds on the resulting error for corresponding event probabilities. In particular, we show that, for events with probabilities asymptotically smaller than any power law on the approximation model, the same bounds also hold on the original model. Finally, as an example application, we apply the developed framework to bound the probability of having an isomorphism between two independent random graphs.