Limit theory of combinatorial optimization for random geometric graphs

Dieter Mitsche; Mathew D. Penrose

doi:10.1214/20-AAP1661

Limit theory of combinatorial optimization for random geometric graphs

Dieter Mitsche, Mathew D. Penrose

Institut Camille Jordan, Jean Monnet University, St Etienne, France

Research output: Contribution to journal › Article › peer-review

39 Downloads (Pure)

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	https://doi.org/10.1214/20-AAP1661
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

Access to Document

10.1214/20-AAP1661

AAP2005-006R1A0 (3).PDFAccepted author manuscript, 488 KB

Cite this

@article{0c8272d77e3a431c8c4c98ca0a99d62c,

title = "Limit theory of combinatorial optimization for random geometric graphs",

abstract = "In the random geometric graph G(n, rn), n vertices are placed randomly in Euclidean d-space and edges are added between any pair of vertices distant at most rn from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for G(n, rn) in the thermodynamic limit with nrnd = const., and also in the dense limit with nrnd → ∞, rn → 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.",

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

author = "Dieter Mitsche and Penrose, {Mathew D.}",

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: {\textcopyright} Institute of Mathematical Statistics, 2021",

year = "2021",

month = dec,

doi = "10.1214/20-AAP1661",

language = "English",

volume = "31",

pages = "2721--2771",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "6",

}

TY - JOUR

T1 - Limit theory of combinatorial optimization for random geometric graphs

AU - Mitsche, Dieter

AU - Penrose, Mathew D.

N1 - 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

PY - 2021/12

Y1 - 2021/12

N2 - In the random geometric graph G(n, rn), n vertices are placed randomly in Euclidean d-space and edges are added between any pair of vertices distant at most rn from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for G(n, rn) in the thermodynamic limit with nrnd = const., and also in the dense limit with nrnd → ∞, rn → 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.

AB - In the random geometric graph G(n, rn), n vertices are placed randomly in Euclidean d-space and edges are added between any pair of vertices distant at most rn from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for G(n, rn) in the thermodynamic limit with nrnd = const., and also in the dense limit with nrnd → ∞, rn → 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.

KW - Clique-covering number

KW - Dense limit

KW - Domination number

KW - Independence number

KW - Minimum-weight matching

KW - Random geometric graph

KW - Sphere packing

KW - Subadditivity

KW - Thermodynamic limit

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85121324415&partnerID=8YFLogxK

U2 - 10.1214/20-AAP1661

DO - 10.1214/20-AAP1661

M3 - Article

SN - 1050-5164

VL - 31

SP - 2721

EP - 2771

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 6

M1 - 0

ER -

Limit theory of combinatorial optimization for random geometric graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Mathew Penrose

Cite this

Limit theory of combinatorial optimization for random geometric graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Profiles

Mathew Penrose

Cite this