## Abstract

In the random geometric graph G(n, r_{n}), n vertices are placed randomly in Euclidean d-space and edges are added between any pair of vertices distant at most r_{n} from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for G(n, r_{n}) in the thermodynamic limit with nr_{n}^{d} = const., and also in the dense limit with nr_{n}^{d} → ∞, r_{n} → 0. Examples include domination number, independence number, clique-covering number, eternal domination number and triangle packing number. The general theory is based on certain subadditivity and superadditivity properties, and also yields LLNs for other functionals such as the minimum weight for the traveling salesman, spanning tree, matching, bipartite matching and bipartite traveling salesman problems, for a general class of weight functions with at most polynomial growth of order d − ε, under thermodynamic scaling of the distance parameter.

Original language | English |
---|---|

Article number | 0 |

Pages (from-to) | 2721-2771 |

Number of pages | 51 |

Journal | Annals of Applied Probability |

Volume | 31 |

Issue number | 6 |

Early online date | 22 Dec 2020 |

DOIs | |

Publication status | Published - Dec 2021 |

### Bibliographical note

Funding Information:We thank Joe Yukich for suggesting that we address the issue of rates of convergence. We also thank the referee for some helpful comments. D. Mitsche has been partially supported by grant GrHyDy ANR-20-CE40-0002, by IDEXLYON of Universit? de Lyon (Programme Investissements d?Avenir ANR16-IDEX-0005) and by Labex MILYON/ANR-10-LABX-0070.

Publisher Copyright:

© Institute of Mathematical Statistics, 2021

## Keywords

- Clique-covering number
- Dense limit
- Domination number
- Independence number
- Minimum-weight matching
- Random geometric graph
- Sphere packing
- Subadditivity
- Thermodynamic limit
- Traveling salesman problem

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty