pmFam
def
The 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 colours are incomparable.
Statement
def pmFam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) : PMPoset n where lt a b
- 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 12
- pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
- pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
- pm_ans_famExplicit form of the oracle on a two-chain poset.
- pm_fam_width2Two-chain posets with injective rank have width at most 2.
- PMState.InvThe adversary invariant.
- pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
- PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
- pm_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
- 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_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
- pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
Lean source view module on GitHub
/-- The 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 colours are incomparable. -/ def pmFam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) : PMPoset n where lt a b := decide (c a = c b ∧ ρ a < ρ b) irrefl a := by simp trans a b d h1 h2 := by simp only [decide_eq_true_eq] at h1 h2 ⊢ exact ⟨h1.1.trans h2.1, h1.2.trans h2.2⟩