AFTD Auto-Formalizing Theoretical Domains

ocacagChainAux

def

The list of nested dyadic cuts obtained by starting at interval c and bisecting t times toward the vertex v: [c] for t = 0, and c :: ocacagChainAux t (ocacagSplit c v) v for t = t'+1.

Statement

def ocacagChainAux : ℕ → ℤ × ℤ → ℤ → List (ℤ × ℤ)
Source
step towards online_cycle_augmentation_adversary_cost_ge
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • ocacagSplitBisect the integer interval c = [c.1, c.2] at its midpoint m = floor((c.1+c.2)/2), returning the half that contains v: [c.1, m] if v ≤ m,…
Used by 1
  • ocacagChainThe dyadic chain to leaf v: start at the top cut [1, 2^(k-1)] and bisect k-1 times toward v, giving k nested cuts down to the singleton {v}.

Lean source view module on GitHub

/-- The chain of nested dyadic cuts from `c` towards the vertex `v`. -/
def ocacagChainAux : ℕ → ℤ × ℤ → ℤ → List (ℤ × ℤ) := fun t c v =>
  match t with
  | 0 => [c]
  | (t + 1) => c :: ocacagChainAux t (ocacagSplit c v) v
See it in the graphDiscuss this resultChallenge it