On the jump of the cover time in random geometric graphs
Carlos Martinez-Arevalo, Dieter Mitsche · 2025
Read On the jump of the cover time in random geometric graphs by Carlos Martinez-Arevalo, Dieter Mitsche (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-02433.txt.
Description
Carlos Martinez-Arevalo and Dieter Mitsche wrote a mathematics paper in two thousand twenty-five about how long a random walk takes to visit every node of a random geometric graph. Such graphs scatter points in space and link near neighbors. The giant connected piece grows as the link radius rises, and the cover time is studied on that piece above the threshold where it appears.
The authors show the cover time jumps at the connectivity threshold. Below it, but above the giant-component threshold, the time grows like n times the square of log n. Above the connectivity point it drops to n times log n, a result known before only in two dimensions under stronger assumptions. The proofs also clarify behavior near the threshold.
Catalog record
| CREATOR | Carlos Martinez-Arevalo, Dieter Mitsche |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 122 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-02433