PMPoset
structure
A strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
Statement
structure PMPoset (n : ℕ)- 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
- Used by 27
- 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_ans_incIf the oracle answers that a and b are incomparable, neither a < b nor b < a holds.
- pm_asymma ≺ b excludes b ≺ a.
- pm_ans_famExplicit form of the oracle on a two-chain poset.
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
- PMSatA list of query/answer facts is satisfied by P.
- pm_exists_min_belowEvery element of a prefix lies above (or is) a minimal element of that prefix.
- 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.
- pmMinPreMinimal elements of the prefix {0, …, k−1}.
- PMTree.runThe output of the algorithm T on the poset P.
- pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
- pmFamThe poset that is a disjoint union of (at most) two chains: elements of the same colour c are ordered by the rank ρ, elements of different…
- 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…
- PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
- PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
- pm_ans_gtIf the oracle answers b < a then b < a holds and a < b does not.
- pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
- PMTree.costThe number of queries the algorithm T makes on the poset P.
- PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
- pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
- 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_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
- PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
/-- A strict partial order on the ground set `Fin n`, given by a Boolean relation `lt` (`lt a b = true` means `a ≺ b`). -/ structure PMPoset (n : ℕ) where lt : Fin n → Fin n → Bool irrefl : ∀ a, lt a a = false trans : ∀ a b c, lt a b = true → lt b c = true → lt a c = true