Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T04:34:43.123Z Has data issue: false hasContentIssue false
  • English
  • Français

The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]d

Part of: Combinatorial probability Geometric probability and stochastic geometry Graph theory

Published online by Cambridge University Press:  01 July 2016

Martin J. B. Appel  and
Ralph P. Russo
Martin J. B. Appel*
Affiliation:
United Technologies Research Center
Ralph P. Russo*
Affiliation:
University of Iowa
*
∗ Postal address: United Technologies Research Center, East Hartford, CT 06108, USA.
∗∗ Postal address: Department of Statistics and Actuarial Science, University of Iowa, Iowa City, IA 52242, USA.
Get access Rights & Permissions [Opens in a new window]

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

RANDOM GRAPHMAXIMUM VERTEX DEGREE

MSC classification

Primary: 05C80: Random graphs
Secondary: 60C05: Combinatorial probability 60D05: Geometric probability and stochastic geometry
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 29 , Issue 3 , September 1997 , pp. 567 - 581
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Appel, M. J. B. and Russo, R. P. (1997) The minimum vertex degree of a graph on uniform points in [0, 1]d. Adv. Appl. Prob. 29, 582–594.Google Scholar
[2] Appel, M. J. B. and Russo, R. P. (1997) The connectivity of a graph on uniform points in [0, 1] d. In preparation.Google Scholar
[3] BollobÁS, B. (1979) Graph Theory: an Introductory Course. Springer, Berlin.Google Scholar
[4] Bondy, J. A. and Murty, U. S. R. (1976) Graph Theory with Applications. North-Holland, Amsterdam.Google Scholar
[5] Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493–507.Google Scholar
[6] Chung, K. L. (1974) A Course in Probability Theory. Academic Press, New York.Google Scholar
[7] Cressie, N. (1980) The asymptotic distribution of the scan statistic under uniformity. Ann. Prob. 8, 828–840.CrossRefGoogle Scholar
[8] Dette, H. and Henze, N. (1989) The limit distribution of the largest nearest-neighbor link in the unit d-cube. J. Appl. Prob. 26, 67–80.Google Scholar
[9] Dudley, R. M. (1978) Central limit theorems for empirical measures. Ann. Prob. 6, 899–929.Google Scholar
[10] Glaz, J. (1989) Approximations and bounds for the distribution of the scan statistic. J. Amer. Statist. Assoc. 84, 560–566.Google Scholar
[11] Jammalamadaka, S. R. and Janson, S. (1986) Limit theorems for a triangular scheme of U-statistics with applications to inter-point distances. Ann. Prob. 14, 1347–1358.Google Scholar
[12] Kester, A. (1975) Asymptotic normality of the number of small distances between random points in a cube. Stoch. Proc. Appl. 3, 45–54.Google Scholar
[13] Palmer, E. M. (1985) Graphical Evolution. Wiley, New York.Google Scholar
[14] Serfling, R. J. (1980) Approximation Theorems of Mathematical Statistics. Wiley, New York.CrossRefGoogle Scholar
[15] Shiryayev, A. N. (1984) Probability. (Graduate Texts in Mathematics 95.) Springer, Berlin.Google Scholar
[16] Silverman, B. and Brown, T. (1978) Short distances, flat triangles and Poisson limits. J. Appl. Prob. 15, 815–825.CrossRefGoogle Scholar
[17] Steele, J. M. and Tierney, L. (1986) Boundary domination and the distribution of the largest nearest-neighbor link. J. Appl. Prob. 23, 524–528.CrossRefGoogle Scholar
[18] Zhou, S. and Jammalamadaka, S. R. (1993) Goodness of fit in multidimensions based on nearest neighbour distances. In Nonparametric Statistics. Vol. 2. Gordon and Breach, New York. pp. 271–284.Google Scholar