On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles
Abstract
Given an increasing graph property , a graph is ‐resilient with respect to if, for every spanning subgraph where each vertex keeps more than a ‐proportion of its neighbors, has property . We study the above notion of local resilience when is a random geometric graph obtained by embedding vertices independently and uniformly at random in , and connecting two vertices by an edge if the distance between them is at most . First, we focus on connectivity. We show that, for every , when is a constant factor above the sharp threshold for connectivity of , the random geometric graph is ‐resilient for the property of being ‐connected, with of the same order as the expected degree. However, contrary to binomial random graphs, for sufficiently small , connectivity is not born ‐resilient in 2‐dimensional random geometric graphs. Second, we study local resilience with respect to the property of containing long cycles. We show that, when is a constant factor above , is ‐resilient with respect to containing cycles of all lengths between constant and . Proving ‐resilience for Hamiltonicity remains elusive with our techniques. Nevertheless, we show that is ‐resilient with respect to Hamiltonicity for a fixed constant .
Related
- Maximum degree for random geometric graphs in the connectivity regime and beyond
- Random Quotients of Hyperbolic Spaces with Respect to WPD Actions and Linear Connectivity of the Boundary
- Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
- Planarity and number of crossings in general models of random geometric graphs
- Inhomogeneous random graphs: how heavy tails reshape connectivity
BibTeX
@article{diaz2026local,
title = {{On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles}},
author = {Alberto Espuny Díaz and Lyuben Lichev and Alexandra Wesolek},
journal = {Random Structures and Algorithms},
year = {2026},
month = oct,
doi = {10.1002/rsa.70100},
eprint = {2406.09921},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05796129v1},
note = {CC BY},
}
RIS
TY - JOUR
TI - On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles
AU - Alberto Espuny Díaz
AU - Lyuben Lichev
AU - Alexandra Wesolek
PY - 2026
DA - 2026/10/12
JO - Random Structures and Algorithms
DO - 10.1002/rsa.70100
UR - https://hal.science/hal-05796129v1
AB - Given an increasing graph property , a graph is ‐resilient with respect to if, for every spanning subgraph where each vertex keeps more than a ‐proportion of its neighbors, has property . We study the above notion of local resilience when is a random geometric graph obtained by embedding vertices independently and uniformly at random in , and connecting two vertices by an edge if the distance between them is at most . First, we focus on connectivity. We show that, for every , when is a constant factor above the sharp threshold for connectivity of , the random geometric graph is ‐resilient for the property of being ‐connected, with of the same order as the expected degree. However, contrary to binomial random graphs, for sufficiently small , connectivity is not born ‐resilient in 2‐dimensional random geometric graphs. Second, we study local resilience with respect to the property of containing long cycles. We show that, when is a constant factor above , is ‐resilient with respect to containing cycles of all lengths between constant and . Proving ‐resilience for Hamiltonicity remains elusive with our techniques. Nevertheless, we show that is ‐resilient with respect to Hamiltonicity for a fixed constant .
SN - 1042-9832
SN - 1098-2418
ER -