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

CREATORCarlos Martinez-Arevalo, Dieter Mitsche
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-02433

Browse the full library · About the Tower of Babel