Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.2 — Dynamic minimum-ratio cut interface

Disproved
DecrAlmostLinearSSSP.Decremental.dynamic_cut_interface

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

dynamic-algorithmsgraph-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-paths

Fix a polynomial numerical-range exponent. There exist one deterministic finite RAM implementation, an absolute constant C>0C>0C>0 and positive functions K,h,Γ,aK,h,\Gamma,aK,h,Γ,a of graph-size bound mmm, chosen before the graph and operation stream. Each function is subpolynomial in mmm, and

32≤K(m)≤2C(log⁡max⁡(2,m))5/6max⁡(1,log⁡log⁡max⁡(2,m)).32\le K(m)\le2^{C(\log\max(2,m))^{5/6}\max(1,\log\log\max(2,m))}.32≤K(m)≤2C(logmax(2,m))5/6max(1,loglogmax(2,m)).

For every connected physical multigraph of size at most mmm, with positive capacities and zero-sum supplied demand of the fixed polynomial numerical range, and every threshold ξ>0\xi>0ξ>0, the implementation supports edge insertion and deletion, paired demand changes, ratio tuples, implicit-potential queries and toggling the latest cut. It starts with y=0y=0y=0. When demand is nonzero, a tuple satisfies G<0G<0G<0, U>0U>0U>0, G=γ(C)G=\gamma(C)G=γ(C), cut⁡u(C)≤U\operatorname{cut}_u(C)\le Ucutu​(C)≤U and G/U≤r∗/KG/U\le r^*/KG/U≤r∗/K, where r∗=min⁡∥x∥u>0γ⋅x/∥x∥ur^*=\min_{\|x\|_u>0}\gamma\cdot x/\|x\|_ur∗=min∥x∥u​>0​γ⋅x/∥x∥u​. A toggle with 0≤τ≤1/U0\le\tau\le1/U0≤τ≤1/U adds τ1C\tau1_Cτ1C​ to yyy and reports every threshold-crossing edge since insertion or its most recent report.

Over every legal finite prefix with LLL operations, TTT toggles and RRR emitted reports,

R≤Γ(m)T/ξ,work⁡≤Cma(m)+h(m)(L+R).R\le\Gamma(m)T/\xi,\qquad\operatorname{work}\le Cma(m)+h(m)(L+R).R≤Γ(m)T/ξ,work≤Cma(m)+h(m)(L+R).

All operations terminate with these guarantees and actual instruction costs, including constant request marshalling. The statement supplies the physical cut implementation needed by the distance algorithm, rather than an assumed free oracle.

Differences from the source:

  • reading: the interface assumes polynomially bounded numerical inputs, with magnitude bound U₀ → an arbitrary fixed exponent bounds capacities above and below and demand magnitudes, with implementation constants uniform for that exponent; reason: p.16 explicitly checks these required polynomial ranges; no bound on the eventual full-goal W is imposed
  • encoding: an implicit cut of minimum-ratio quality and subpolynomial operation and report factors → a finite RAM implementation with semantic views, reusable slots and universal direction inequalities; sizes are saturated by max(2,m) and quality can be padded to K≥32; reason: queries and updates remain actual charged instructions; the direction form equals the minimum form on finite connected inputs and saturation changes only finitely many sizes
Preamble
import Mathlib
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_CutProtocol

set_option autoImplicit false
open scoped ENNReal NNReal
Formal statement
namespace DecrAlmostLinearSSSP.Decremental

/-- Lemma 3.2: all implementation properties, including actual operation costs, are
conclusions. Polynomial numerical ranges have an exponent fixed before graph instances. -/
theorem dynamic_cut_interface :
    ∀ exponent : ℕ, ∃ (impl : CutImplementation) (K h Γ a : ℕ → ℝ) (C : ℝ),
      0 < C ∧ Subpolynomial K ∧ Subpolynomial h ∧ Subpolynomial Γ ∧ Subpolynomial a ∧
      (∀ m, 32 ≤ K m ∧ K m ≤ Real.rpow 2
        (C * Real.rpow (Real.log (max 2 m : ℕ)) (5 / 6 : ℝ) *
          max 1 (Real.log (Real.log (max 2 m : ℕ))))) ∧
      ∀ m ξ, 0 < ξ → ImplementsCut impl m exponent (K m) (h m) (Γ m)
        (C * m * a m) ξ := by sorry

end DecrAlmostLinearSSSP.Decremental
Source
Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #912 (October 2026), p. 9, Lemma 3.2, equation (3.12), preamble and footnote 2; p. 16, numerical ranges; pinned PDF: https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/912.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