UZH-Logo

Maintenance Infos

Random combinatorial structures: the convergent case


Barbour, A D; Granovsky, B (2005). Random combinatorial structures: the convergent case. Journal of Combinatorial Theory, Series A, 109(2):203-220.

Abstract

This paper studies the distribution of the component spectrum of combinatorial structures such as uniform random forests, in which the classical generating function for the numbers of (irreducible) elements of the different sizes converges at the radius of convergence; here, this property is expressed in terms of the expectations of independent random variables Zj, j ≥ 1, whose joint distribution, conditional on the event that Σnj=1 jZj = n, gives the distribution of the component spectrum for a random structure of size n. For a large class of such structures, we show that the component spectrum is asymptotically composed of Zj components of small sizes j, j ≥ 1, with the remaining part, of size close to n, being made up of a single, giant component.

This paper studies the distribution of the component spectrum of combinatorial structures such as uniform random forests, in which the classical generating function for the numbers of (irreducible) elements of the different sizes converges at the radius of convergence; here, this property is expressed in terms of the expectations of independent random variables Zj, j ≥ 1, whose joint distribution, conditional on the event that Σnj=1 jZj = n, gives the distribution of the component spectrum for a random structure of size n. For a large class of such structures, we show that the component spectrum is asymptotically composed of Zj components of small sizes j, j ≥ 1, with the remaining part, of size close to n, being made up of a single, giant component.

Citations

12 citations in Web of Science®
11 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

38 downloads since deposited on 02 Feb 2010
18 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Uncontrolled Keywords:Combinatorial structures; Giant component; Conditioning relation; Coagulation-fragmentation
Language:English
Date:2005
Deposited On:02 Feb 2010 19:19
Last Modified:05 Apr 2016 13:24
Publisher:Academic Press
ISSN:0097-3165
Publisher DOI:https://doi.org/10.1016/j.jcta.2004.09.001
Related URLs:http://www.ams.org/mathscinet-getitem?mr=2121024
Permanent URL: https://doi.org/10.5167/uzh-21672

Download

[img]
Preview
Content: Accepted Version
Filetype: PDF
Size: 201kB
View at publisher

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations