Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

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

  • Alberto Espuny Díaz
Open at sourcePDFDOICite

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

  1. Sharp detection thresholds for random geometric graphs with polynomial average degrees
    Hang Du, Cheng Mao, Nike Sun +2
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  2. Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
    Ghurumuruhan Ganesan
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  3. Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
    Dávid Ferenczi, Alexander Grigoriev
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Infinite divisibility of powers of positive stable random variables
    Min Wang
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  5. Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
    Kyle Luh
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{diaz2026high,
  title = {{High powers of grids in random geometric graphs and thresholds for wide spanning structures}},
  author = {Alberto Espuny Díaz},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37408},
  eprint = {2610.37408},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37408},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - High powers of grids in random geometric graphs and thresholds for wide spanning structures
AU  - Alberto Espuny Díaz
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37408
UR  - https://arxiv.org/abs/2610.37408
AB  - 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.
ER  -