AFTD Auto-Formalizing Theoretical Domains

PMPoset.Width2

def

The poset has width at most 2: among any three distinct elements some two are comparable.

Statement

def PMPoset.Width2 {n : ℕ} (P : PMPoset 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 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 8
  • pm_fam_width2Two-chain posets with injective rank have width at most 2.
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
  • 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_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
  • 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

/-- The poset has width at most `2`: among any three distinct elements some two are comparable. -/
def PMPoset.Width2 {n : ℕ} (P : PMPoset n) : Prop :=
  ∀ a b c : Fin n, a ≠ b → b ≠ c → a ≠ c →
    P.lt a b = true ∨ P.lt b a = true ∨ P.lt b c = true ∨ P.lt c b = true ∨
      P.lt a c = true ∨ P.lt c a = true
See it in the graphDiscuss this resultChallenge it