Asymptotics for the probability of connectedness and the distribution of number of components

Jason P. Bell*, Edward A. Bender, Peter J. Cameron, L. Bruce Richmond

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

Let ρn be the fraction of structures of "size" n which are "connected"; e.g., (a) the fraction of labeled or unlabeled n-vertex graphs having one component, (b) the fraction of partitions of n or of an n-set having a single part or block, or (c) the fraction of n-vertex forests that contain only one tree. Various authors have considered lim ρn, provided it exists. It is convenient to distinguish three cases depending on the nature of the power series for the structures: purely formal, convergent on the circle of convergence, and other. We determine all possible values for the pair (lim inf ρn, lim sup ρn) in these cases. Only in the convergent case can one have 0 < lim ρn < 1. We study the existence of lim ρn in this case.

Original languageEnglish
Pages (from-to)1-22
Number of pages22
JournalElectronic Journal of Combinatorics
Volume7
Issue number1 R
Publication statusPublished - 1 Dec 2000

Fingerprint

Dive into the research topics of 'Asymptotics for the probability of connectedness and the distribution of number of components'. Together they form a unique fingerprint.

Cite this