Linear extension: Difference between revisions

Revision as of 09:53, 18 August 2023

Latest revision as of 22:11, 28 August 2025

(4 intermediate revisions by 2 users not shown)

Line 1:

{{Short description|Mathematical ordering of a partial order}}

{{CS1 config|mode=cs2}}

In [[order theory]], a branch of [[mathematics]], a '''linear extension''' of a [[partial order]] is a [[total order]] (or linear order) that is compatible with the partial order. As a classic example, the [[lexicographic order]] of totally ordered sets is a linear extension of their [[product order]].

Line 39:

}}.</ref>

There is an analogous statement for preorders: every preorder can be extended to a total preorder. This statement was proved by Hansson.<ref>{{Cite journalcitation |last=Hansson |first=Bengt |date=1968 |title=Choice Structures and Preference Relations |url=https://www.jstor.org/stable/20114617 |journal=Synthese |volume=18 |issue=4 |pages=443–458 |doi=10.1007/BF00484979 |jstor=20114617 |issn=0039-7857}}</ref>{{Rp|___location=Lemma 3}}

In modern [[axiomatic set theory]] the order-extension principle is itself taken as an axiom, of comparable ontological status to the axiom of choice. The order-extension principle is implied by the [[Boolean prime ideal theorem]] or the equivalent [[compactness theorem]],<ref>{{citation

Line 169:

Counting the number of linear extensions of a finite poset is a common problem in [[algebraic combinatorics]]. This number is given by the leading coefficient of the [[order polynomial]] multiplied by <math>|P|!.</math>

[[Young tableaudiagram]]s can be considered as linear extensions of a finite [[Ideal (order theory)|order-ideal]] in the infinite poset <math>\N \times \N,</math>. and theySimilarly, [[Young tableau|standard Young tableaux]] can be considered as linear extensions of a poset corresponding to the Young diagram. For the (usual) Young diagrams, linear extensions are counted by the [[hook length formula]]. For the skew Young diagrams, linear extensions are counted by a determinantal formula.<ref>{{citation

| last1 = Chan | first1 = Swee Hong

| last2 = Pak | first2 = Igor | author2-link = Igor Pak

| arxiv = 2311.02743

| date = March 2025

| doi = 10.4171/EMSS/97

| journal = EMS Surveys in Mathematical Sciences

| title = Linear extensions of finite posets}}</ref>

==References==