PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Search for Almost-Spanning Square Grids in Erd\H{o}s--R\'enyi Random Graphs

Dávid Ferenczi, Alexander Grigoriev

arXiv:2609.12647v1math.PRcs.DMmath.CO

TL;DR

General bounded-degree embedding and universality results give broad guarantees but require substantially larger densities when specialized to square grids. This paper uses the grid’s geometry in a local algorithm, proving a constructive almost-spanning result whose density is a factor of order √log n above the emergence scale for macroscopic grids.

  • Problem

    General bounded-degree embedding and universality results apply to square grids at densities substantially larger than the grid-emergence scale.

    Source: §1 · p. 2

  • Method

    The Quarantined Local Search separates initial-boundary construction from corner closure and controls adaptive negative exposure using bounded pair-test histories.

    Source: §1 · p. 2, §2.2 · pp. 6, 8, §2.3 · p. 9

  • Results

    For k^2 = Θ(n), the algorithmic guarantee requires a density a factor of order √log n above the existential square-grid emergence scale.

    Source: §1 · p. 3, §4 · p. 16

  • Takeaways & Limitations

    The local polynomial-time construction reaches every fixed almost-spanning regime k^2 ≤ (1−δ)n by exploiting the nested geometry of the square grid.

    Source: §4 · p. 16

    When n−k^2 = o(n), the argument no longer gives the same starvation bound, so the fully spanning case needs a more economical reservoir or different final closure steps.

    Source: §4 · p. 17

Abstract

from arXiv · show

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 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 $\delta\in (0,1)$, there exists $C_\delta>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-\delta)n$ in $G(n,p)$ with high probability whenever $p\ge C_\delta\sqrt{\ln k/n}$. Thus, for $k^2=\Theta(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.

1 Introduction

This paper gives a constructive local algorithm for embedding almost-spanning square grids in Erdős–Rényi random graphs. It exploits the grid’s geometry to reach a sparser density for square grids than general bounded-degree embedding results, while extending an earlier constructive occupancy guarantee.

1 Introduction

  • The construction extends an earlier guarantee for a fixed linear fraction of host vertices to every fixed regime k^2 ≤ (1−δ)n, at the same asymptotic density order for macroscopic grids.The earlier construction is due to Fernandez de la Vega and Manoussakis [1994].Source: §1 · p. 2
  • The Quarantined Local Search separates construction of the initial boundary from later corner closure and controls exposure history during grid filling.Its quarantine step isolates one-edge exposure, while a bounded partner-history invariant controls pair-test dependencies.Source: §1 · p. 2
  • Unlike broad bounded-degree embedding and universality results, this result is restricted to square grids but reaches a substantially sparser density for that target family.The cited general results are Ferber et al. [2017] and Ferber and Nenadov [2018].Source: §1 · p. 2
  • With probability 1−o(1), the randomized local-search algorithm finds a k × k square grid under the conditions of Theorem 1.The result covers every fixed almost-spanning regime k^2 ≤ (1−δ)n.Source: §1 · pp. 2–3
  • For k^2 = Θ(n), the algorithmic result pays a factor of order √log n over the existential square-grid emergence scale.This distinguishes the constructive guarantee from Riordan [2000].Source: §1 · pp. 2–3

2 Algorithmic Overview

The algorithm constructs an initial L-shaped grid boundary, quarantines vertices exposed during the path search until the first interior layer is complete, and then fills the grid with nested L-shaped layers using local searches. The overview also describes the corner-closure phase’s candidate-query count and its edge-level implementation cost when k² ≤ n.

2.1 Query model

  • Linear Extension uses one-edge tests only in Phase 1; Corner Closure tests whether a candidate connects to both active-pair vertices, records only Boolean failure, and retains failed candidates for other pairs.Each candidate is tested at most once against a given closure pair, with candidates inspected in a fixed order or one measurable from the revealed filtration.Source: §2.1 · p. 4

2.2 Structural Lemmas

  • The deterministic nested-L schedule completes the grid from its 2k−1-vertex boundary, embeds k² vertices total, and uses each grid vertex in at most four distinct closure pairs.Each added vertex is introduced by closing a corner using two previously embedded grid neighbours.Source: §2.2 · pp. 5–6
  • Prior failed pair-tests can alter later conditional success probabilities, but each vertex occurs in at most four distinct closure pairs; the conditional analysis applies to pair-test histories relative to the active frontier.The initial path's one-edge exposure history is kept out of the first closure layer by quarantining unused initial-pool vertices.Source: §2.2 · pp. 6, 9

2.3 Algorithmic Description

  • When p > p0, Phase 0 lazily thins the graph to operational density p0, removing Lemma 4's high-density deterioration from its (1−p)^8 factor; a grid found after thinning remains in the original graph.The fixed p0 is chosen so that (1−p0)^8 ≥ 1/2.Source: §2.2 · p. 9, §2.3 · p. 9
  • Phase 1 extends a 2k−1-vertex path from Vstart; Phase 2 builds the first 2k−3-vertex interior layer from pristine Vmain, then Phase 3 releases quarantined vertices.Unused vertices from Vstart are quarantined after path construction and temporarily excluded from the Phase 2 search.Source: §2.3 · pp. 9–10
  • The Quarantined Local Search uses O(k²n) local candidate queries, or O(n²) when k² ≤ n.Source: §2.3 · p. 12
  • Corner closures require O(kn) + O(k^2n) = O(k^2n) candidate queries.An exhaustive implementation inspects at most n candidates in each operation.Source: §2.3 · p. 12
  • Each candidate requires at most two ordinary edge inspections, so edge-level pair queries preserve the bound up to a constant factor at O(n^2) when k^2 ≤ n.Source: §2.3 · p. 12

3 Proof of Theorem 1

The proof establishes success for each of the three phases, then combines their failure probabilities to show that the algorithm embeds the target grid with high probability.

3.1 Probability of Success for Phase 1

  • Phase 1 succeeds with high probability because its failure-probability upper bound vanishes as n grows.The argument restricts the initial search to a linear-sized vertex pool and bounds failure across the required extension steps.Source: §3.1 · pp. 12–13

3.2 Probability of Success in Phase 2

  • Given Phase 1 success, Phase 2 fails with probability o(1) when Cδ > 2.Its candidate reservoir starts pristine, and the proof bounds the 2k − 3 required Corner Closures.Source: §3.2 · p. 13

3.3 Probability of Success in Phase 3

  • Phase 3 succeeds with high probability after the quarantine is lifted and the remaining Corner Closures are performed.The proof applies a union bound over the remaining operations, using the single-step failure bound from Lemma 4.Source: §3.3 · p. 15

3.4 Proof of Theorem 1

  • The global failure probability tends to zero, so the algorithm embeds the k × k square grid with high probability.The proof accounts for failure in each phase, conditional on the preceding phases succeeding.Source: §3.4 · pp. 15–16

4 Discussion and Open Problems

The paper’s local construction reaches every fixed almost-spanning square-grid regime by exploiting grid geometry and separating boundary construction from corner closures. Its density remains above the existential emergence scale, and the method’s extension to other lattices and nearly spanning grids has unresolved obstacles.

Discussion and Open Problems

  • The square-grid geometry supports a local polynomial-time construction by separating the initial boundary from deterministic corner closures and bounding active-frontier pair-test histories.Quarantine isolates one-edge exposure from the later pair-query process.Source: §4 · p. 16
  • The construction extends the prior fixed-linear-fraction guarantee to every fixed regime k^2 ≤ (1 − δ)n, while retaining the same asymptotic density order for macroscopic grids.General embedding results cover broader graph classes but require substantially higher densities when specialized to square grids.Source: §4 · p. 16
  • For k^2 = Θ(n), the sufficient density is a factor of order √log n above the corresponding n^-1/2 emergence scale.The result is constructive but does not recover the existential threshold.Source: §4 · p. 16
  • Whether the √log n overhead reflects a limit of local search or only the construction’s failure bounds remains unclear.The comparison is for the macroscopic regime k^2 = Θ(n).Source: §4 · p. 16
  • The Phase 3 reservoir argument retains a linear number of unused vertices, so it gives no same starvation bound when n − k^2 = o(n), including fully spanning grids.Extending the method there would require a more economical reservoir or a different treatment of final closures.Source: §4 · p. 17
  • Hexagonal walls require many one-neighbour extensions rather than the square grid’s two-neighbour Corner Closures, so the method does not directly apply.A rectangular-grid detour inherits the denser square-grid requirement; a direct wall algorithm would need different treatment of those extensions.Source: §4 · p. 17
  • Triangular grids may admit analogous three-neighbour closure bounds, but mixed two- and three-neighbour closures create candidate conflicts after failed pair queries.The paper leaves open whether closure ordering or reservoir control can address this issue.Source: §4 · p. 17
  • The applicability of Quarantined Local Search depends strongly on target geometry, motivating investigation of other families with a similar construction.The square-grid construction uses an initial boundary followed by closures with uniformly bounded active-frontier pair-test history.Source: §4 · p. 17
Loading 2609.12647v1…