Linear extension: Difference between revisions

Revision as of 13:32, 6 July 2021

Revision as of 20:12, 22 July 2021

Line 3:

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

Given any partial orders ≤ and ≤^* on a set ''X'', ≤^* is a linear extension of ≤ exactly when (1) ≤^* is a [[total order]] and (2) for every ''x'' and ''y'' in ''X'', if {{nowrap|''x'' ≤ ''y''}}, then {{nowrap|''x'' ≤^* ''y''}}. It is that second property that leads mathematicians to describe ≤^* as '''extending''' ≤.

Given any partial orders ≤<math>\,\leq\,</math> and ≤<supmath>\,\leq^*\,</supmath> on a set ''<math>X'',</math> ≤<supmath>\,\leq^*\,</supmath> is a linear extension of ≤<math>\,\leq\,</math> exactly when (1) ≤<supmath>\,\leq^*\,</supmath> is a [[total order]] and (2) for every ''<math>x'', and ''y'' \in ''X'',</math> if {{nowrap|''<math>x'' ≤\leq ''y''}},</math> then {{nowrap|''<math>x'' ≤<sup>\leq^* y.</supmath> ''y''}}. It is that second property that leads mathematicians to describe ≤<supmath>\,\leq^*\,</supmath> as '''extending''' ≤<math>\,\leq.</math>

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

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.

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

Line 40 ⟶ 42:

}}.</ref>

Applying the order-extension principle to a partial order in which every two elements are incomparable shows that (under this principle) every set can be linearly ordered. This assertion that every set can be linearly ordered is known as the '''ordering principle''', OP, and is a weakening of the [[well-ordering theorem]]. However, there are [[modelModel theory|models of set theory]] in which the ordering principle holds while the order-extension principle does not.<ref>{{citation

| last = Mathias | first = A. R. D.

| contribution = The order extension principle

Line 52 ⟶ 54:

| year = 1971}}.</ref>

== Related results ==

The order extension principle is [[constructiveConstructive proof|constructively provable]] for ''{{em|finite''}} sets using [[topological sorting]] algorithms, where the partial order is represented by a [[directedDirected acyclic graph]] with the set's elements as its [[vertexVertex (graph theory)|vertices]]. Several algorithms can find an extension in [[linear time]].<ref>{{citation

| last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen

| last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson

Line 120 ⟶ 123:

}}. 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 [[totalTotal 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 {{nowrap|''<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=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 129 ⟶ 132:

| 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 {{nowrap|''<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.

| last2 = Felsner | first2 = S.

Line 145 ⟶ 148:

== Algebraic combinatorics ==

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 |P|!.

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 tableau]] can be considered as linear extensions of a finite [[Ideal (order theory)|order-ideal]] in the infinite poset <math>\mathbb{N}\times\mathbb{N}</math>, and they are counted by the [[hook length formula]].

[[Young tableau]] can be considered as linear extensions of a finite [[Ideal (order theory)|order-ideal]] in the infinite poset <math>\mathbb{N} \times \mathbb{N},</math>, and they are counted by the [[hook length formula]].

== References ==

{{reflist}}