Threshold Functions for Random Graphs on a Line Segment
- 1 January 1999
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 13 (3) , 373-387
- https://doi.org/10.1017/s0963548304006121
Abstract
We look at a model of random graphs suggested by Gilbert: given an integer . 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.)Keywords
This publication has 0 references indexed in Scilit: