Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.15274 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910838050258944 |
|---|---|
| author | Brandenberger, Anna Donderwinkel, Serte Kerriou, Céline Lugosi, Gábor Mitchell, Rivka |
| author_facet | Brandenberger, Anna Donderwinkel, Serte Kerriou, Céline Lugosi, Gábor Mitchell, Rivka |
| contents | A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time stamps indicate the propagation of information. We determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős-Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. Our results hold for a family of "soft" random geometric graphs as well as the standard random geometric graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Temporal connectivity of Random Geometric Graphs Brandenberger, Anna Donderwinkel, Serte Kerriou, Céline Lugosi, Gábor Mitchell, Rivka Probability A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time stamps indicate the propagation of information. We determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős-Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. Our results hold for a family of "soft" random geometric graphs as well as the standard random geometric graph. |
| title | Temporal connectivity of Random Geometric Graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2502.15274 |