Lemma 2.2 — hook-length formula for rooted tree posets
ProvedCountOrderings.NFree.lemma_2_2combinatoricslinear-extensionsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite poset whose Hasse diagram is a rooted tree: has a minimum element (the root), and every other element covers exactly one element. For let be the subtree rooted at . Then the number of linear extensions of is
This classical hook-length formula is the counting tool behind every reduction of the paper: fixing the order of the original elements turns the remaining constraints into a tree poset, whose linear extensions it counts in closed form (§3, §6).
Formalization Note. The identity is stated in ; every , so the quotient is an honest one. Covers, , rooted tree posets and are those of CountOrderings.NFree.Poset.
Differences from the source:
- encoding: "a poset whose Hasse diagram is a rooted tree (root = minimum, order increasing away from it)" → a finite poset with a least element in which every other element covers exactly one element; reason: for finite posets the two descriptions are equivalent (the Hasse diagram is then an out-tree from the root).
- encoding: #LE(T) = |T|!/∏|T_v| as a quotient → the same identity in ℚ with #LE(T) cast from ℕ; reason: every |T_v| ≥ 1, same value.
Preamble
import Mathlib import Definitions.Def_CountOrderings_NFree_Poset
Formal statement
namespace CountOrderings.NFree
theorem lemma_2_2 (T : Type) [PartialOrder T] [Fintype T] (hT : IsRootedTreePoset T) :
(numLinExt T : ℚ) =
((Fintype.card T).factorial : ℚ) / ∏ v : T, (upSetCard v : ℚ) := by sorry
end CountOrderings.NFree
Source
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission, p. 8 (PDF p. 9), Lemma 2.2 and footnote 2; proof in Appendix A.1, pp. 27–28 (PDF pp. 28–29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.