On the probability of connectedness

Peter J. Cameron*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

Given a class of structures with a notion of connectedness (satisfying some reasonable assumptions), we consider the limit (as n → ∞) of the probability that a random (labelled or unlabelled) n-element structure in the class is connected. The paper consists of three parts: two specific examples, N-free graphs and posets, where the limiting probability of connectedness is one-half and the golden ratio respectively; an investigation of the relation between this question and the growth rate of the number of structures in the class; and a generalisation of the problem to other combinatorial constructions motivated in part by the group-theoretic constructions of direct and wreath product.

Original languageEnglish
Pages (from-to)175-187
Number of pages13
JournalDiscrete Mathematics
Volume167-168
DOIs
Publication statusPublished - 15 Apr 1997

Fingerprint

Dive into the research topics of 'On the probability of connectedness'. Together they form a unique fingerprint.

Cite this