Volume 21, 2017
|Page(s)||235 - 250|
|Published online||12 December 2017|
Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism∗,∗∗
1 Department of Applied Informatics, Federal University of the State of Rio de Janeiro, Rio de Janeiro, Brazil
2 Systems Engineering and Computer Science Program, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
Received: 24 February 2017
Revised: 2 August 2017
Accepted: 21 August 2017
We consider events over the probability space generated by the degree sequences of multiple independent Erdős-Rényi random graphs, and consider an approximation probability space where such degree sequences are deemed to be sequences of i.i.d. random variables. We show that, for any sequence of events with probabilities asymptotically smaller than some power law in the approximation model, the same upper bound also holds in the original model. We accomplish this by extending an approximation framework proposed in a seminal paper by McKay and Wormald. Finally, as an example, we apply the developed framework to bound the probability of isomorphism-related events over multiple independent random graphs.
Mathematics Subject Classification: 05C80
Key words: Random graphs / degree sequences / power laws / asymptotic approximations / graph isomorphism
© EDP Sciences, SMAI, 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.