The probability that a random multigraph is simple

Simple item page
dc.creatorJanson, Svante
dc.date2006-09-28
dc.date.accessioned2026-07-07T07:25:23Z
dc.date.available2026-07-07T07:25:23Z
dc.descriptionConsider 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.
dc.description24 pages
dc.identifierhttps://arxiv.org/abs/math/0609802
dc.identifierhttp://arxiv.org/abs/math/0609802
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116698
dc.subjectCombinatorics
dc.subjectProbability
dc.subject05C80; 05C30, 60C05
dc.titleThe probability that a random multigraph is simple
dc.typetext

Files

Collections

arXiv