High powers of grids in random geometric graphs and thresholds for wide spanning structures

arXiv:2610.37408 · math.CO · Submitted 2026-10-27 · Read on arXiv

math.CO

Submitted: 2026-10-27

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by/4.0/

The gist: Using results of Leighton and Shor and of Shor and Yukich, we present a connection between d-dimensional bandwidth and (sharp) thresholds in d-dimensional random geometric graphs: namely…

Abstract

Using results of Leighton and Shor and of Shor and Yukich, we present a connection between d-dimensional bandwidth and (sharp) thresholds in d-dimensional random geometric graphs: namely, that the sharp threshold for a given graph property in random geometric graphs is determined by its d-dimensional bandwidth, and vice versa, whenever the d-dimensional bandwidth of this property grows sufficiently fast (at least polylogarithmically) with the order of the graphs. This connection provides a number of corollaries, such as new information about the sharp thresholds for containing different spanning subgraphs in 1-dimensional random geometric graphs, as well as asymptotically tight bounds for the d-dimensional bandwidth of structures such as graphs of bounded treewidth or genus, giving an asymptotic resolution to several problems raised by Chung in 1988.

Related papers