On the components of random geometric graphs in the dense limit
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911574744104960 |
|---|---|
| author | Penrose, Mathew D. Yang, Xiaochuan |
| author_facet | Penrose, Mathew D. Yang, Xiaochuan |
| contents | Consider the geometric graph on $n$ independent uniform random points in a connected compact region $A$ of ${\bf R}^d, d \geq 2$, with $C^2$ boundary, or in the unit square, with distance parameter $r_n$. Let $K_n$ be the number of components of this graph, and $R_n$ the number of vertices not in the giant component. Let $S_n$ be the number of isolated vertices. We show that if $r_n$ is chosen so that $nr_n^d$ tends to infinity but slowly enough that ${\bf E}[S_n]$ also tends to infinity, then $K_n$, $R_n$ and $S_n$ are all asymptotic to $μ_n$ in probability as $n \to \infty$ where (with $|A|$, $θ_d$ and $|\partial A|$ denoting the volume of $A$, of the unit $d$-ball, and the perimeter of $A$ respectively) $μ_n := ne^{-πn (r_n)^d/|A|}$ if $d=2$ and $μ_n := ne^{-θ_d n (r_n)^d/|A|} + θ_{d-1}^{-1} |\partial A| (r_n)^{1-d} e^{- θ_d n (r_n)^d/(2|A|)}$ if $d\geq 3$. We also give variance asymptotics and central limit theorems for $K_n$ and $R_n$ in this limiting regime when $d \geq 3$, and for Poisson input with $d \geq 2$. We extend these results (substituting ${\bf E}[S_n]$ for $μ_n$) to a class of non-uniform distributions on $A$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02676 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the components of random geometric graphs in the dense limit Penrose, Mathew D. Yang, Xiaochuan Probability 60D05, 60F05, 60F25, 05C80 Consider the geometric graph on $n$ independent uniform random points in a connected compact region $A$ of ${\bf R}^d, d \geq 2$, with $C^2$ boundary, or in the unit square, with distance parameter $r_n$. Let $K_n$ be the number of components of this graph, and $R_n$ the number of vertices not in the giant component. Let $S_n$ be the number of isolated vertices. We show that if $r_n$ is chosen so that $nr_n^d$ tends to infinity but slowly enough that ${\bf E}[S_n]$ also tends to infinity, then $K_n$, $R_n$ and $S_n$ are all asymptotic to $μ_n$ in probability as $n \to \infty$ where (with $|A|$, $θ_d$ and $|\partial A|$ denoting the volume of $A$, of the unit $d$-ball, and the perimeter of $A$ respectively) $μ_n := ne^{-πn (r_n)^d/|A|}$ if $d=2$ and $μ_n := ne^{-θ_d n (r_n)^d/|A|} + θ_{d-1}^{-1} |\partial A| (r_n)^{1-d} e^{- θ_d n (r_n)^d/(2|A|)}$ if $d\geq 3$. We also give variance asymptotics and central limit theorems for $K_n$ and $R_n$ in this limiting regime when $d \geq 3$, and for Poisson input with $d \geq 2$. We extend these results (substituting ${\bf E}[S_n]$ for $μ_n$) to a class of non-uniform distributions on $A$. |
| title | On the components of random geometric graphs in the dense limit |
| topic | Probability 60D05, 60F05, 60F25, 05C80 |
| url | https://arxiv.org/abs/2501.02676 |