v_selection_poset
For a natural number n, a partial order P on Fin n, and a rank i, V_i(P) is the infimum of depths of all comparison decision trees on n elements that correctly select the i-th smallest element for P.
Statement
noncomputable def v_selection_poset (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) : ℕ
- Defined in
- arXiv:2610.18740 Section 2, line 270
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 3
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
- comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
- comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
Read back from the Lean
v_selection_poset n P i is defined as the infimum (sInf, in ℕ) of the set of depths d of comparison trees T on n elements that correctly select the i-th element (1-indexed) under every linear extension of the partial order P on Fin n.
Specifically:
- Given n : ℕ, a partial order P on Fin n, and i : ℕ,
- It considers all comparison trees T : ComparisonTree n such that for every linear order L on Fin n extending P, evaluating T according to comparisons in L yields an element ans : Fin n such that exactly i - 1 elements in Fin n are strictly less than ans under L.
- It returns the infimum (minimum when nonempty, 0 when empty) of the depths of all such trees T.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The minimum worst-case number of comparisons V_i(P) to select the i-th smallest element for poset P. -/ noncomputable def v_selection_poset (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) : ℕ := open scoped Classical in sInf { d : ℕ | ∃ T : ComparisonTree n, comparison_tree_correct_for_selection n P i T ∧ comparison_tree_depth T = d }