Local search finds large square grids in random graphs efficiently
Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
Discrete Mathematics
Summary
Finding big square grid patterns inside random networks is a challenging math problem. The authors created a special step-by-step algorithm that carefully builds these grids piece by piece. Their approach works well even when the network connections are fairly sparse, but still above a certain threshold. This result improves how we understand when large grid-like structures appear in random graphs.
What this means in practice
- •For network engineers: Design network topologies that embed large grid-like substructures efficiently to improve navigation and fault tolerance analysis.
- •For complex system modelers: Simulate spreading processes on large networks using embedded grid patterns to better approximate spatially structured phenomena.
A theory result. No direct application yet.
Authors
Dávid Ferenczi, Alexander Grigoriev
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 $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.