On the probability of connectedness

✍ Scribed by Peter J. Cameron

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 648 KB
• Volume: 167-168
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00226-9

✦ Synopsis

Given a class of structures with a notion of connectedness (satisfying some reasonable assumptions), we consider the limit (as n -+ oc) 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.