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