Local Search for Almost-Spanning Square Grids in Erd\H{o}s--R\'enyi Random Graphs
Finding large lattice subgraphs in sparse Erd\H{o}s--R\'enyi 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 densit...