Appendix F, p. 42, Figure 8 — the poset of ω disjoint k-element chains has width ω
ProvedPosetSecretary.LowerBound.width_chainsPosetantichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1posetposet-width
Let and , and let be the disjoint union of chains with elements each, two elements being comparable only when they lie in the same chain. Its width, the largest number of pairwise incomparable elements, is
This is the claim that the instance of Figure 8 has width , as Proposition 5.1 requires of its instance.
Formalization Note Width is the published AppliedComb.Posets.width (largest antichain), not a minimum number of chains. The hypothesis is necessary: for the poset is empty and has width .
Preamble
import Mathlib import Definitions.Def_AppliedComb_Posets_width import Definitions.Def_PosetSecretary_LowerBound_Setting
Formal statement
namespace PosetSecretary.LowerBound
theorem width_chainsPoset (ω k : ℕ) (hk : 1 ≤ k) :
AppliedComb.Posets.width (ChainsPoset ω k) = ω := by sorry
end PosetSecretary.LowerBound
Source
Salem & Gupta, Secretary Problems with Biased Evaluations Using Partial Ordinal Information, SSRN 3444283 (version of 2022-04-17), proof of Proposition 5.1, Appendix F, p. 42, first paragraph and Figure 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.