ocacagChain
def
The 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}.
Statement
def ocacagChain (k : ℕ) (v : ℤ) : List (ℤ × ℤ)- Source
- step towards online_cycle_augmentation_adversary_cost_ge
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 2
- ocacagChainAuxThe 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 ::…
- 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,…
Lean source view module on GitHub
/-- The dyadic chain of cuts leading to the vertex `v`, starting from the top cut [1, 2^(k-1)]. -/ def ocacagChain (k : ℕ) (v : ℤ) : List (ℤ × ℤ) := ocacagChainAux (k - 1) (1, (2 : ℤ) ^ (k - 1)) v