{"id":"arxiv/2609.12647","url":"https://arxiv.org/abs/2609.12647","tags":["math.PR","cs.DM","math.CO"],"score":0,"title":"Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs","domain":"math.PR","source":"arxiv","authors":["Dávid Ferenczi","Alexander Grigoriev"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-11","reactions":{}}