pmInit
def
The adversary's initial state: every element is its own component and alive.
Statement
open Finset in def pmInit (n : ℕ) : PMState n where col
- Source
- step towards pm_exact_complexity / pm_lower_bound (exact complexity 2n - 3 at width 2, refuting the tightness conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- PMStateThe state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to…
- Used by 3
- pm_init_potThe potential of the initial adversary state is 2n - 3.
- pm_init_invThe initial adversary state (all elements alive, every element its own component) satisfies the adversary invariant.
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
Lean source view module on GitHub
open Finset in /-- The adversary's initial state: every element is its own component and alive. -/ def pmInit (n : ℕ) : PMState n where col := fun _ => false rk := fun x => (x.val : ℤ) comp := id alive := Finset.univ facts := []