The maximal degree in a Poisson-Delaunay graph

2018/04/04 by Gilles Bonnet, Bonnet, Gilles, Nicolas Chenavier +1
Mathematics · #FOS: Mathematics #Probability (math.PR) #math.PR

paper · pdf · doi:10.48550/arxiv.1804.01416

arxiv created 2018/04/04 · arxiv updated 2018/04/05

Abstract

We investigate the maximal degree in a Poisson-Delaunay graph in R^d, d≥ 2, over all nodes in the window W_ρ:= ρ^1/d[0,1]^d as ρ goes to infinity. The exact order of this maximum is provided in any dimension. In the particular setting d=2, we show that this quantity is concentrated on two consecutive integers with high probability. An extension of this result is discussed when d≥ 3

Related

• The maximum degree of planar graphs I. Series-parallel graphs
• Degrees in the β- and β'-Delaunay graphs
• The largest component in a subcritical random graph with a power law degree distribution
• The scaling window for a random graph with a given degree sequence
• Concentration of maximum degree in random planar graphs