Approximating the degree sequences of two random graphs
Jefferson Elbert Simões, Daniel R. Figueiredo, Valmir Carneiro Barbosa · arXiv (Cornell University) · 2016
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.