Linear extension: Difference between revisions

Revision as of 13:10, 28 February 2023

Latest revision as of 22:11, 28 August 2025

(8 intermediate revisions by 4 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 6:

=== Linear extension of a partial order ===

A [[partial order]] is a [[Reflexive relation|reflexive]], [[Transitive relation|transitive]] and [[Antisymmetric relation|antisymmetric]] relation. Given any partial orders <math>\,\leq\,</math> and <math>\,\leq^*\,</math> on a set <math>X,</math> <math>\,\leq^*\,</math> is a linear extension of <math>\,\leq\,</math> exactly when

# <math>\,\leq^*\,</math> is a [[total order]], and

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 149:

| title = Balanced pairs in partial orders

| volume = 201

| year = 1999| doi-access = free

}}.</ref> An equivalent way of stating the conjecture is that, if one chooses a linear extension of <math>P</math> uniformly at random, there is a pair <math>(x, y)</math> which has probability between 1/3 and 2/3 of being ordered as <math>x < y.</math> However, for certain infinite partially ordered sets, with a canonical probability defined on its linear extensions as a limit of the probabilities for finite partial orders that cover the infinite partial order, the 1/3–2/3 conjecture does not hold.<ref>{{citation

| last1 = Brightwell | first1 = G. R.

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==