Lemma 3.2 — Dynamic minimum-ratio cut interface
DisprovedDecrAlmostLinearSSSP.Decremental.dynamic_cut_interfaceFix a polynomial numerical-range exponent. There exist one deterministic finite RAM implementation, an absolute constant and positive functions of graph-size bound , chosen before the graph and operation stream. Each function is subpolynomial in , and
For every connected physical multigraph of size at most , with positive capacities and zero-sum supplied demand of the fixed polynomial numerical range, and every threshold , the implementation supports edge insertion and deletion, paired demand changes, ratio tuples, implicit-potential queries and toggling the latest cut. It starts with . When demand is nonzero, a tuple satisfies , , , and , where . A toggle with adds to and reports every threshold-crossing edge since insertion or its most recent report.
Over every legal finite prefix with operations, toggles and emitted reports,
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
import Mathlib import Definitions.Def_DecrAlmostLinearSSSP_Decremental_CutProtocol set_option autoImplicit false open scoped ENNReal NNReal
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.