Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-27T10:30:12.916Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Finite Topologies and their Thresholds

Published online by Cambridge University Press:  25 June 2001

C. F. MACLEAN  and
NEIL O'CONNELL
C. F. MACLEAN
Affiliation:
Ecole Normale Supérieure, 45 rue d'Ulm, 75005 Paris, France (e-mail: [email protected])
NEIL O'CONNELL
Affiliation:
BRIMS, Hewlett-Packard Laboratories, Stoke Gifford, Bristol BS34 8QZ, England (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

For each integer n, there is a natural family of probability distributions on the set of topologies on a set of n elements, parametrized by an integer variable, m. We will describe how these are constructed and analysed, and find threshold functions (for m in terms of n) for various topological properties; we focus attention on connectivity and the size of the largest component.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 3 , May 2001 , pp. 239 - 249
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

An earlier version of this article appeared as BRIMS Technical Report HPL-BRIMS-9718.