Threshold Functions for Random Graphs on a Line Segment
Gregory L. McColm · Combinatorics Probability Computing · 2004
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.)