Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T00:52:05.944Z Has data issue: false hasContentIssue false

Threshold Functions for Random Graphs on a Line Segment

Published online by Cambridge University Press:  28 April 2004

GREGORY L. McCOLM
Affiliation:
Department of Mathematics, University of South Florida, Tampa, FL 33620, USA (e-mail: mccolm@math.usf.edu URL: http://www.math.usf.edu/~mccolm)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We look at a model of random graphs suggested by Gilbert: given an integer $n$ and $\delta > 0$, scatter $n$ vertices independently and uniformly on a metric space, and then add edges connecting pairs of vertices of distance less than $\delta$ apart.

We consider the asymptotics when the metric space is the interval [0, 1], and $\delta = \delta(n)$ is a function of $n$, for $n \to \infty$. We prove that every upwards closed property of (ordered) graphs has at least a weak threshold in this model on this metric space. (But we do find a metric space on which some upwards closed properties do not even have weak thresholds in this model.) We also prove that every upwards closed property with a threshold much above connectivity's threshold has a strong threshold. (But we also find a sequence of upwards closed properties with lower thresholds that are strictly weak.)

Information

Type
Paper
Copyright
2004 Cambridge University Press