Two-point concentration in random geometric graphs

DOI10.1007/S00493-008-2283-3MaRDI QIDQ2390151zbMATH OpenOpenAlexFDO

Authors Tobias Müller

Publication date 20 July 2009

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-008-2283-3

zbMATH Keywords

geometric random graphgraph invariantstwo-point distributions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05)

Review text

Consider a sequence of independent identically distributed random variables \(X_n\) for \(n=1,2,\dots\) with a bounded density function in \(d\)-dimensional Euclidean space. A geometric graph \(G_n\) is defined on the first \(n\) random variables as vertices with edges between variables that are closer than a specified positive radius \(r=r(n)\). For \(n r^d = o(\ln n)\) it is shown that the probability distributions of the clique number, of the chromatic number, and of other specified graph parameters all become concentrated on two consecutive integers as \(n\) tends to infinity.

Recommendations

• Colouring random geometric graphs
• On the chromatic number of random geometric graphs
• Random Geometric Graphs
• Connectivity of soft random geometric graphs
• The spectrum of a random geometric graph is concentrated

Cites work

• A note on the sharp concentration of the chromatic number of random graphs
• An inequality involving multinomial probabilities
• Focusing of the scan statistic and geometric clique number
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• Maxima of Poisson-like variables and related triangular arrays
• On the chromatic number of random graphs
• Poisson approximation in connection with clustering of random points
• Random channel assignment in the plane
• Scan statistics
• Scan statistics and applications
• The concentration of the chromatic number of random graphs
• The distribution of the maximum degree of a random graph
• The two possible values of the chromatic number of a random graph

Cited in

(22)

• Limit theory of combinatorial optimization for random geometric graphs
• Large degrees in scale-free inhomogeneous random graphs
• Localization in random geometric graphs with too many edges
• The acquaintance time of (percolated) random geometric graphs
• Central limit theorems for \(U\)-statistics of Poisson point processes
• The spectrum of a random geometric graph is concentrated
• Concentration for Poisson functionals: component counts in random geometric graphs
• Laws of large numbers of subgraphs in directed random geometric networks
• Symmetric motifs in random geometric graphs
• Colouring random geometric graphs
• High-dimensional random geometric graphs and their clique number
• Focusing of the scan statistic and geometric clique number
• On the treewidth of random geometric graphs and percolated grids
• Maker-breaker games on random geometric graphs
• On the concentration of the domination number of the random graph
• On the normalized Laplacian spectra of random geometric graphs
• On the clique number of noisy random geometric graphs
• On the chromatic number of random geometric graphs
• Quantitative CLTs on the Poisson space via Skorohod estimates and p-Poincaré inequalities
• Planted clique recovery in random geometric graphs
• The chromatic and clique numbers of random scaled sector graphs
• A geometric Achlioptas process

This page was built for publication: Two-point concentration in random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390151)