Linear extension: Difference between revisions

Revision as of 21:48, 8 February 2022

Latest revision as of 22:11, 28 August 2025

(16 intermediate revisions by 9 users not shown)

Line 1:

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

{{CS1 config|mode=cs2}}

{{Distinguish|Linear extension of a linear map}}

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]].

== Definitions ==

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

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 (1) <math>\,\leq^*\,</math> is a [[total order]] and (2) for every <math>x, y \in X,</math> if <math>x \leq y,</math> then <math>x \leq^* y.</math> It is that second property that leads mathematicians to describe <math>\,\leq^*\,</math> as '''extending''' <math>\,\leq.</math>

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

# For every <math>x, y \in X,</math> if <math>x \leq y,</math> then <math>x \leq^* y.</math>

It is that second property that leads mathematicians to describe <math>\,\leq^*\,</math> as '''extending''' <math>\,\leq.</math>

Alternatively, a linear extension may be viewed as an [[order-preserving]] [[bijection]] from a partially ordered set <math>P</math> to a [[Total order#Chains|chain]] <math>C</math> on the same ground set.

{{Distinguish|=== Linear extension of a linearpreorder map}}===

A [[preorder]] is a reflexive and transitive relation. The difference between a preorder and a partial-order is that a preorder allows two different items to be considered "equivalent", that is, both <math>x\precsim y</math> and <math>y\precsim x</math> hold, while a partial-order allows this only when <math>x=y</math>. A relation '''<math>\precsim^*</math>''' is called a linear extension of a preorder <math>\precsim</math> if:

# '''<math>\precsim^*</math>''' is a [[total preorder]], and

# For every <math>x, y \in X,</math> if <math>x\precsim y</math> then <math>x\precsim^* y</math> , and

# For every <math>x, y \in X,</math> if <math>x\prec y</math> then <math>x\prec^* y</math> . Here, <math>x\prec y</math> means "<math>x \precsim y</math> and not <math>y \precsim x</math>".

The difference between these definitions is only in condition 3. When the extension is a partial order, condition 3 need not be stated explicitly, since it follows from condition 2. ''Proof'': suppose that <math>x \precsim y</math> and not <math>y \precsim x</math>. By condition 2, <math>x\precsim^* y</math>. By reflexivity, "not <math>y \precsim x</math>" implies that <math>y\neq x</math>. Since '''<math>\precsim^*</math> '''is a partial order, <math>x\precsim^* y</math> and <math>y\neq x</math> imply "not <math>y\precsim^* x</math>". Therefore, <math>x\prec^* y</math>.

However, for general preorders, condition 3 is needed to rule out trivial extensions. Without this condition, the preorder by which all elements are equivalent (<math>y \precsim x</math> and <math>x \precsim y</math> hold for all pairs ''x'',''y'') would be an extension of every preorder.

== Order-extension principle ==

{{further|Szpilrajn extension theorem}}

The statement that every partial order can be extended to a total order is known as the '''order-extension principle'''. A proof using the [[axiom of choice]] was first published by [[Edward Marczewski|Edward Marczewski (Szpilrajin)]] in 1930. Marczewski writes that the theorem had previously been proven by [[Stefan Banach]], [[Kazimierz Kuratowski]], and [[Alfred Tarski]], again using the axiom of choice, but that the proofs had not been published.<ref>{{citation

| last = Marczewski | first = Edward | authorlink = Edward Marczewski

| journal = Fundamenta Mathematicae

Line 23 ⟶ 38:

| year = 1930| doi = 10.4064/fm-16-1-386-389 | doi-access = free

}}.</ref>

There is an analogous statement for preorders: every preorder can be extended to a total preorder. This statement was proved by Hansson.<ref>{{citation |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 32 ⟶ 49:

| year = 2008}}.</ref> but the reverse implication doesn't hold.<ref>{{citation

| last1 = Felgner | first1 = U.

| last2 = Truss | first2 = J. K. |author-link2=John Truss

| date = March 1999

| doi = 10.2307/2586759

Line 124 ⟶ 141:

}}. See especially item (1) on {{nowrap|p. 294.}}</ref>

This area also includes one of order theory's most famous open problems, the [[1/3–2/3 conjecture]], which states that in any finite partially ordered set <math>P</math> that is not [[Total order|totally ordered]] there exists a pair <math>(x, y)</math> of elements of <math>P</math> for which the linear extensions of <math>P</math> in which <math>x < y</math> number between 1/3 and 2/3 of the total number of linear extensions of <math>P.</math><ref>{{citation|author=[[Sergey Kislitsyn|Kislitsyn, S. S.]] |year=1968|title=Finite partially ordered sets and their associated sets of permutations|journal=Matematicheskie Zametki|volume=4|pages=511–518}}.</ref><ref>{{citation

| last = Brightwell | first = Graham R.

| doi = 10.1016/S0012-365X(98)00311-2

Line 132 ⟶ 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 152 ⟶ 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 ==

{{reflist}}

{{Order theory}}

[[Category:Order theory]]