High powers of grids in random geometric graphs and thresholds for wide spanning structures
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality