Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
Abstract
Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed δ∈ (0,1), there exists Cδ>0 such that the algorithm embeds a k× k square grid with k2≤ (1−δ)n in G(n,p) with high probability whenever p≥ Cδ√(ln k/n). Thus, for k2=Θ(n), a density of order √(log n/n) is sufficient, a factor of order √(log n) above the corresponding n−1/2 emergence scale.
Related
- High powers of grids in random geometric graphs and thresholds for wide spanning structures
- Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
- Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
- Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
- Spanning-Tree Maximization Forces Isoperimetry in the Square Lattice
BibTeX
@misc{ferenczi2026local,
title = {{Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs}},
author = {Dávid Ferenczi and Alexander Grigoriev},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12647},
eprint = {2609.12647},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12647},
}
RIS
TY - UNPB
TI - Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
AU - Dávid Ferenczi
AU - Alexander Grigoriev
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12647
UR - https://arxiv.org/abs/2609.12647
AB - Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed δ∈ (0,1), there exists C_δ>0 such that the algorithm embeds a k× k square grid with k^2≤ (1−δ)n in G(n,p) with high probability whenever p≥ C_δ√(ln k/n). Thus, for k^2=Θ(n), a density of order √(log n/n) is sufficient, a factor of order √(log n) above the corresponding n^−1/2 emergence scale.
ER -