A random geometric graph, @math , is formed by choosing @math points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most @math . For a given constant @math , we show that @math is a distance threshold function for @math to have a connected subgraph on @math points. Based on this, we show that @math is a distance threshold for @math to be plane, and @math is a distance threshold to be planar. We also investigate distance thresholds for @math to have a non-crossing edge, a clique of a given size, and an independent set of a given size.
A general reference on random geometric graphs is @cite_14 . There is extensive literature on various aspects of random geometric graphs of which we mention the related work on coverage by @cite_3 @cite_24 and a review on percolation, connectivity, coverage and coloring by @cite_21 . As in random graphs, any monotone property in random geometric graphs has a threshold function @cite_10 @cite_7 @cite_9 @cite_13 .
@cite_13 @cite_14 @cite_7 @cite_9 @cite_21 @cite_3 @cite_24 @cite_10
2119221712 2037549896 1940448963 1974893148
Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of @math points distributed uniformly in [0,1]d. We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs. ean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of n points distributed uniformly in [0, 1] d . We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs. We give a characterization of vertex-monotone properties with sharp thresholds in a Poisson random geometric graph or hypergraph. As an application we show that a geometric model of random k-SAT exhibits a sharp threshold for satisfiability. In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n ,w e form a random graphby replacing eachvertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G .T h e resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also “randomizing” given graphs. The main specific result that we prove here (Theorem 1) is that if δ ≥ 3 is the smallest vertex degree in G, then almost all n-covers of G are δconnected. In subsequent papers we will address oth er graphproperties, suchas girth , expansion and chromatic number.