PMTree.Correct2
def
T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
Statement
def PMTree.Correct2 {n : ℕ} (T : PMTree n) : Prop
- Defined in
- Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4: Theorem 11, Theorem 16 and the conjecture that the deterministic lower bound for k = 1 is tight; formalized by the operator (Claude), 2026-10-05
- Verified
- 05 Oct 2026
- Axioms
- none listed
- Built on 5
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
- PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
- PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
- PMTree.runThe output of the algorithm T on the poset P.
- Used by 4
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
- pm_alg_correctThe algorithm is correct on every width-2 poset.
- pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
Lean source view module on GitHub
/-- `T` correctly finds the minimal elements of every poset of width at most `2` on `Fin n`. -/ def PMTree.Correct2 {n : ℕ} (T : PMTree n) : Prop := ∀ P : PMPoset n, P.Width2 → T.run P = P.minSet