pmMinPre
def
Minimal elements of the prefix {0, …, k−1}.
Statement
open Finset in def pmMinPre {n : ℕ} (P : PMPoset n) (k : ℕ) : Finset (Fin n)
- 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
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- Used by 7
- pm_minPre_succAn element is minimal in the prefix of length k+1 iff it was minimal in the prefix of length k and is not above element k, or it is…
- pm_exists_min_belowEvery element of a prefix lies above (or is) a minimal element of that prefix.
- pm_alg_correctThe algorithm is correct on every width-2 poset.
- pm_mem_minPreEvery minimal element of the prefix of length k has index below k and no element of index below k lies below it.
- pm_minPre_nThe minimal elements of the full prefix of length n are the minimal elements of the poset.
- pm_step_eqOne scanning step of the candidate algorithm maintains the invariant that its candidate list is exactly the set of minimal elements of the…
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
open Finset in /-- Minimal elements of the prefix `{0, …, k−1}`. -/ def pmMinPre {n : ℕ} (P : PMPoset n) (k : ℕ) : Finset (Fin n) := Finset.univ.filter (fun a => a.val < k ∧ ∀ b : Fin n, b.val < k → P.lt b a = false)