Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1 — deterministic LOCAL (1 + epsilon)-approximate maximum matching

Proved
FasterDistributedMatching.ApproximateMatching.theorem_1_1

by mikedeng1 · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributed-algorithmsgraph-theorymatchingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

For every positive real ε\varepsilonε and every finite undirected simple graph GGG, with known vertex and degree bounds ∣V(G)∣≤n|V(G)|\le n∣V(G)∣≤n and deg⁡(G)≤Δ\deg(G)\le\Deltadeg(G)≤Δ, a uniform deterministic LOCAL protocol returns an actual matching MMM satisfying

OPT⁡(G)≤(1+ε)∣M∣.\operatorname{OPT}(G)\le(1+\varepsilon)|M|.OPT(G)≤(1+ε)∣M∣.

For each fixed polynomial identifier-range convention there are constants C>0C>0C>0 and d∈Nd\in\mathbb Nd∈N, chosen before accuracy, graph, bounds and identifiers, such that

T≤⌈C(1+1/ε)d(L3/2J2+Lmax⁡{1,log⁡∗n})⌉,T\le\left\lceil C(1+1/\varepsilon)^d\left(L^{3/2}J^2+\sqrt L\max\{1,\log^*n\}\right)\right\rceil,T≤⌈C(1+1/ε)d(L3/2J2+L​max{1,log∗n})⌉,

where L=max⁡{1,log⁡2(max⁡{2,Δ})}L=\max\{1,\log_2(\max\{2,\Delta\})\}L=max{1,log2​(max{2,Δ})} and J=max⁡{1,log⁡2L}J=\max\{1,\log_2L\}J=max{1,log2​L}. Nodes initially know their identifier, neighbor identifiers, the common bounds and ε\varepsilonε; no bipartition, matching oracle or optimum is supplied. Both endpoints report their incident matching edge consistently. The protocol must work for every permitted injective identifier assignment, and includes empty graphs, isolated vertices, small degrees and all ε>1\varepsilon>1ε>1.

This is the source's complete degree-dependent headline result, including the square-root factor in the additive coloring term and polynomial accuracy overhead. The external approximation booster remains a proof obligation, not a hypothesis.

Differences from the source:

  • encoding: finite undirected simple graphs → SimpleGraph (Fin N), with arbitrary supplied bounds n and degree; reason: every finite simple graph can be relabelled in this way; the carrier index is never processor input
  • encoding: deterministic synchronous LOCAL algorithms → tape-independent published LocalAlg programs with source-only local inputs and endpoint-consistent outputs; reason: rules and types precede graph inputs; multiset broadcast supports addressed dictionaries without bandwidth restrictions
  • encoding: asymptotic base-two logarithmic bounds → uniform positive constants, natural ceiling budgets and logarithms padded to at least one; reason: only bounded-parameter conventions change; empty and degree-zero or degree-one graphs remain included
  • encoding: unique O(log n)-bit identifiers → every injection below max(2,n)^(b+1), for each fixed natural b; reason: the protocol and constants may depend on the fixed ID convention, and never on a graph, its identifiers or epsilon
  • encoding: hidden poly(1/epsilon) overhead for all epsilon > 0 → a uniform C(1+1/epsilon)^d factor, with natural d and C>0 before epsilon; reason: this expresses polynomial accuracy overhead explicitly and includes large epsilon without narrowing its domain
Preamble
import Mathlib
import Definitions.Def_FasterDistributedMatching_ApproximateMatching_Local
Formal statement
namespace FasterDistributedMatching.ApproximateMatching

/- Theorem 1.1, printed pp.1--2 / PDF pp.3--4; §3.5. The program and polynomial
accuracy bound precede all graph instances and all positive real epsilon. -/
theorem theorem_1_1 :
    ∀ b : ℕ, ∃ (A : Deterministic Accuracy (Finset ℕ) (Option ℕ)) (C : ℝ) (d : ℕ),
      0 < C ∧
      (∀ k : Accuracy, 0 < k.epsilon →
        A.program.rounds k ≤ budget C ((1 + 1 / k.epsilon) ^ d * matchingTime k.n k.degree)) ∧
      ∀ (N : ℕ) (G : SimpleGraph (Fin N)) (k : Accuracy),
        0 < k.epsilon → boundedGraph G k.n k.degree →
        ∀ ids : Fin N → ℕ, Identifiers k.n (b + 1) ids →
          ∃ M : SimpleGraph (Fin N),
            ReportsMatching G ids (execute A G k ids (neighborIDs G ids)) M ∧
            (optimum G : ℝ) ≤ (1 + k.epsilon) * (matchingSize M : ℝ) := by sorry

end FasterDistributedMatching.ApproximateMatching
Source
Mohsen Ghaffari, Christoph Grunau, STOC 2027 submission #1024 (October 2026), Theorem 1.1, printed pp.1–2, PDF pp.3–4; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1024.pdf
Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me