pith. sign in

arxiv: math/0609802 · v1 · submitted 2006-09-28 · 🧮 math.CO · math.PR

The probability that a random multigraph is simple

classification 🧮 math.CO math.PR
keywords multigraphprobabilityonlyrandomsimpleassumtionsasymptoticasymptotically
0
0 comments X
read the original abstract

Consider a random multigraph G* with given vertex degrees d_1,...,d_n, contructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the number of edges (d_1+...+d_n)/2 tending to infinity, the probability that the multigraph is simple stays away from 0 if and only if \sum d_i^2=O(\sum d_i). This was previously known only under extra assumtions on the maximum degree. We also give an asymptotic formula for this probability, extending previous results by several authors.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.