The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]d
- 1 September 1997
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 29 (3), 567-581
- https://doi.org/10.2307/1428076
Abstract
On independent random points U1,· ··,Un distributed uniformly on [0, 1]d, a random graph Gn(x) is constructed in which two distinct such points are joined by an edge if the l∞-distance between them is at most some prescribed value 0 ≦ x ≦ 1. Almost-sure asymptotic rates of convergence/divergence are obtained for the maximum vertex degree of the random graph and related quantities, including the clique number, chromatic number and independence number, as the number n of points becomes large and the edge distance x is allowed to vary with n. Series and sequence criteria on edge distances {xn} are provided which guarantee the random graph to be empty of edges, a.s.Keywords
This publication has 13 references indexed in Scilit:
- The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1]dAdvances in Applied Probability, 1997
- Approximations and Bounds for the Distribution of the Scan StatisticJournal of the American Statistical Association, 1989
- The limit distribution of the largest nearest-neighbour link in the unit d-cubeJournal of Applied Probability, 1989
- Limit Theorems for a Triangular Scheme of $U$-Statistics with Applications to Inter-Point DistancesThe Annals of Probability, 1986
- Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensionsJournal of Applied Probability, 1986
- The Asymptotic Distribution of the Scan Statistic Under UniformityThe Annals of Probability, 1980
- Central Limit Theorems for Empirical MeasuresThe Annals of Probability, 1978
- Short distances, flat triangles and Poisson limitsJournal of Applied Probability, 1978
- Asymptotic normality of the number of small distances between random points in a cubeStochastic Processes and their Applications, 1975
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952