Linear extension: Difference between revisions

Revision as of 15:41, 9 February 2015

Latest revision as of 22:11, 28 August 2025

(39 intermediate revisions by 21 users not shown)

Line 1:

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

In [[order theory]], a branch of mathematics, a '''linear extension''' of a [[partial order]] is a linear order (or [[total order]]) that is compatible with the partial order.

{{CS1 config|mode=cs2}}

In [[order theory]], a branch of [[mathematics]], a '''linear extension''' of a [[partial order]] is a linear[[total order]] (or [[totallinear 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 linear 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''' ≤.

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

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.

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_orderTotal order#Chains|chain]] ''<math>C''</math> on the same ground set.

=== Linear extension of a preorder ===

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

{{Further2further|[[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 16 ⟶ 36:

| url = http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf

| volume = 16

| year = 1930}}| doi = 10.<4064/ref>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

| last = Jech | first = Thomas | author-link = Thomas Jech

| isbn = 978-0-486-46624-8

| origyearorig-year=originally published in 1973

| publisher = [[Dover Publications]]

| title = The Axiom of Choice

| 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 32 ⟶ 55:

| journal = The Journal of Symbolic Logic

| pages = 199–215

| publisher = Association for Symbolic Logic

| title = The Independence of the Prime Ideal Theorem from the Order-Extension Principle

| volume = 64

| jstor = 2586759}}| citeseerx = 10.</ref>1.1.54.8336

}}.</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 49 ⟶ 72:

| 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 [[directed 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 57 ⟶ 81:

| contribution = Section 22.4: Topological sort

| edition = 2nd

| isbn = 978-0-262-03293-73

| pages = 549–552

| publisher = MIT Press

| title = [[Introduction to Algorithms]]

| year = 2001| title-link = Introduction to Algorithms }}.</ref> Despite the ease of finding a single linear extension, the problem of counting all linear extensions of a finite partial order is [[Sharp-P-complete|#P-complete]]; however, it may be estimated by a [[fully polynomial-time randomized approximation scheme]].<ref>{{citation

| last1 = Brightwell | first1 = Graham R.

| last2 = Winkler | first2 = Peter | author2-link = Peter Winkler

Line 70 ⟶ 94:

| title = Counting linear extensions

| volume = 8

| year = 1991}}</ref><ref>| s2cid = 119697949

}}</ref><ref>

{{citation

| last1 = Bubley | first1 = Russ

Line 76 ⟶ 101:

| doi = 10.1016/S0012-365X(98)00333-1

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| pages =81-8881–88

| title = Faster random generation of linear extensions

| volume = 201

| issue = 1–3

| year = 1999}}.</ref> Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are [[semiorder]]s.<ref>{{citation

| year = 1999| s2cid = 2942330

| doi-access = free

| year = 1999}}.</ref> Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are [[semiorder]]s.<ref>{{citation

| last1 = Fishburn | first1 = Peter C. | author1-link = Peter C. Fishburn

| last2 = Trotter | first2 = W. T.

Line 89 ⟶ 117:

| title = Linear extensions of semiorders: a maximization problem

| volume = 103

| year = 1992}}.</ref>| doi-access = free

}}.</ref>

The [[order dimension]] of a partial order is the minimum cardinality of a set of linear extensions whose intersection is the given partial order; equivalently, it is the minimum number of linear extensions needed to ensure that each [[Critical pair (order theory)|critical pair]] of the partial order is reversed in at least one of the extensions.

[[Antimatroid]]s may be viewed as generalizing partial orders; in this view, the structures corresponding to the linear extensions of a partial order are the basic words of the antimatroid.<ref>{{citation

| last1 = Björner
| first1 = Anders

| last2 = Ziegler
| first2 = Günter M.
| author2-link = Günter M. Ziegler

| contribution = Introduction to Greedoids

| editor-last = White
| editor-first = Neil

| isbn = 978-0-521-38165-9

| pages = [https://archive.org/details/matroidapplicati0000unse/page/284 284–357]

| publisher = Cambridge University Press

| series = Encyclopedia of Mathematics and its Applications

| title = Matroid Applications

| volume = 40

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

| url = https://archive.org/details/matroidapplicati0000unse/page/284

}}. 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=[[Sergey Kislitsyn|Kislitsyn, S. S.]] |year=1968|title=Finite partially ordered sets and their associated sets of permutations|journal=MatematicheskiyeMatematicheskie Zametki|volume=4|pages=511–518}}.</ref><ref>{{citation

| last = Brightwell | first = Graham R.

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

| issue = 1-31–3

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| pages = 25–52

| title = Balanced pairs in partial orders

| volume = 201

| year = 1999| doi-access =

| year = 1999}}.</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 125 ⟶ 161:

| title = Balancing pairs and the cross product conjecture

| volume = 12

| year = 1995}}| citeseerx = 10.</ref>1.1.38.7841

| s2cid = 14793475

}}.</ref>

== 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 <math>|P|!.</math>

[[Young diagram]]s can be considered a finite [[Ideal (order theory)|order-ideal]] in the infinite poset <math>\N \times \N</math>. Similarly, [[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 ==

== References ==

{{reflist}}

{{Order theory}}

[[Category:Order theory]]