Hubbry Logo
Linear extensionLinear extensionMain
Open search
Linear extension
Community hub
Linear extension
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Linear extension
Linear extension
Linear extension
View on Wikipedia
from Wikipedia

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

[edit]

Linear extension of a partial order

[edit]

A partial order is a reflexive, transitive and antisymmetric relation. Given any partial orders and on a set is a linear extension of exactly when

  1. is a total order, and
  2. For every if then

It is that second property that leads mathematicians to describe as extending

Alternatively, a linear extension may be viewed as an order-preserving bijection from a partially ordered set to a chain on the same ground set.

Linear extension of a preorder

[edit]

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 and hold, while a partial-order allows this only when . A relation is called a linear extension of a preorder if:

  1. is a total preorder, and
  2. For every if then , and
  3. For every if then . Here, means " and not ".

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 and not . By condition 2, . By reflexivity, "not " implies that . Since is a partial order, and imply "not ". Therefore, .

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

Order-extension principle

[edit]
Further information: 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 (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.[1]

There is an analogous statement for preorders: every preorder can be extended to a total preorder. This statement was proved by Hansson.[2]: 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,[3] but the reverse implication doesn't hold.[4]

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 models of set theory in which the ordering principle holds while the order-extension principle does not.[5]

[edit]

The order extension principle is constructively provable for finite sets using topological sorting algorithms, where the partial order is represented by a directed acyclic graph with the set's elements as its vertices. Several algorithms can find an extension in linear time.[6] Despite the ease of finding a single linear extension, the problem of counting all linear extensions of a finite partial order is #P-complete; however, it may be estimated by a fully polynomial-time randomized approximation scheme.[7][8] 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 semiorders.[9]

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 of the partial order is reversed in at least one of the extensions.

Antimatroids 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.[10]

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 that is not totally ordered there exists a pair of elements of for which the linear extensions of in which number between 1/3 and 2/3 of the total number of linear extensions of [11][12] An equivalent way of stating the conjecture is that, if one chooses a linear extension of uniformly at random, there is a pair which has probability between 1/3 and 2/3 of being ordered as 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.[13]

Algebraic combinatorics

[edit]

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

Young diagrams can be considered a finite order-ideal in the infinite poset . Similarly, 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.[14]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Linear extension

View on Grokipedia
from Grokipedia
In , a linear extension of a partial order on a set is a (also known as a linear order) on the same set that extends the partial order, meaning it preserves the comparability of elements: if a≤ba \leq b in the partial order, then aa precedes or equals bb in the linear order. Equivalently, it can be viewed as a of the set's elements such that the order respects all existing inequalities from the partial order. For example, in the poset consisting of two incomparable pairs like {1<2}\{1 < 2\} and {3<4}\{3 < 4\}, valid linear extensions include sequences such as 1-2-3-4 or 3-1-4-2, but not 2-1-3-4, as they must maintain the internal orders of each pair. A fundamental result in the field is Szpilrajn's theorem (also known as the extension theorem for partial orders), which states that every partial order on a nonempty set can be extended to a linear order; this holds for finite sets via inductive selection of minimal elements and for arbitrary sets using the axiom of choice. The existence proof often relies on Zorn's lemma or the Hausdorff maximum principle applied to chains in the poset of partial extensions. In graph-theoretic terms, where a partial order corresponds to a directed acyclic graph (DAG) with edges indicating precedence, a linear extension is precisely a topological sorting of the graph. Linear extensions play a central role in and , as the problem of counting the number of linear extensions of a given poset is #P-complete, making exact enumeration challenging for large sets. Algorithms exist for approximating the count or generating random extensions efficiently, such as those running in polynomial time relative to the poset's size using methods on the extension graph. They also arise in applications like scheduling tasks with precedence constraints, theory of posets (where the is the minimum number of linear extensions needed to realize the partial order), and probabilistic analyses in .

Definitions

Partial orders

A partial order on a set PP is a ≤\leq that is reflexive (for all a∈Pa \in P, a≤aa \leq a), antisymmetric (if a≤ba \leq b and b≤ab \leq a, then a=ba = b), and transitive (if a≤ba \leq b and b≤cb \leq c, then a≤ca \leq c). A classic example is the subset relation ⊆\subseteq on the power set of a , such as P({1,2})\mathcal{P}(\{1,2\}), where ∅⊆{1}⊆{1,2}\emptyset \subseteq \{1\} \subseteq \{1,2\} forms a , but {1}\{1\} and {2}\{2\} are incomparable. A linear extension of a partial order (P,≤)(P, \leq) is a total order (P,⪯)(P, \preceq) on the same ground set PP such that a≤ba \leq b implies a⪯ba \preceq b for all a,b∈Pa, b \in P. Here, a is a partial order in which every pair of distinct elements is comparable (for all a,b∈Pa, b \in P with a≠ba \neq b, either a⪯ba \preceq b or b⪯ab \preceq a). Consider the poset of positive divisors of 6, denoted D6={1,2,3,6}D_6 = \{1, 2, 3, 6\} under divisibility ∣|, where $1 | 2, &#36;1 | 3, $2 | 6, &#36;3 | 6, and 2 is incomparable to 3. Two linear extensions of this poset are 1⪯2⪯3⪯61 \preceq 2 \preceq 3 \preceq 6 and 1⪯3⪯2⪯61 \preceq 3 \preceq 2 \preceq 6. Hasse diagrams provide a standard visualization for partial orders, representing elements as vertices and covering relations (immediate precedences) as upward edges, omitting transitive edges and self-loops; for D6D_6, the diagram places 1 at the bottom, with edges to 2 and 3, and edges from 2 and 3 to 6 at the top. Linear extensions can then be illustrated by topological sorts of the Hasse diagram that respect all edges. By construction, a linear extension preserves all existing order relations from the partial order while resolving incomparabilities: if aa and bb are incomparable under ≤\leq (neither a≤ba \leq b nor b≤ab \leq a), then exactly one of a⪯ba \preceq b or b⪯ab \preceq a holds in the , without introducing contradictions since no prior relation is violated. This ensures the extension is a faithful total ordering compatible with the original structure. Linear extensions are also defined for preorders, which generalize partial orders by requiring only reflexivity and transitivity without antisymmetry.

Preorders

A on a set PP is a ≤\leq that is reflexive and transitive, but not necessarily antisymmetric. Unlike partial orders, preorders may permit distinct elements aa and bb such that a≤ba \leq b and b≤ab \leq a, inducing an ∼\sim where a∼ba \sim b a≤ba \leq b and b≤ab \leq a. These equivalence classes partition PP into subsets of indistinguishable elements under the preorder. A linear extension of a (P,≤)(P, \leq) is a (L,⪯)(L, \preceq) on PP such that if a≤ba \leq b in PP, then a⪯ba \preceq b in LL. A is a preorder that is also complete, meaning for all x,y∈Lx, y \in L, either x⪯yx \preceq y or y⪯xy \preceq x. This extension preserves the original ordering while resolving incomparabilities by introducing ties only within equivalence classes or establishing a total order among them. Consider a preorder on the set {a,b,c}\{a, b, c\} where a≤ba \leq b and a≤ca \leq c, but bb and cc are incomparable. One possible linear extension is the total preorder where a⪯ba \preceq b, a⪯ca \preceq c, and b∼cb \sim c (i.e., b⪯cb \preceq c and c⪯bc \preceq b), merging bb and cc into an . Another extension could impose b⪯cb \preceq c without c⪯bc \preceq b, yielding a strict order between them while maintaining a⪯ba \preceq b and a⪯ca \preceq c. Linear extensions of preorders are closely related to those of partial orders via the quotient poset P/∼P/{\sim}, obtained by identifying equivalent elements and inducing a partial order on the equivalence classes. A linear extension of the preorder (P,≤)(P, \leq) corresponds to a linear extension of this quotient poset, where elements within each equivalence class are tied in the total preorder, but classes are totally ordered. Partial orders represent special cases of preorders with trivial equivalence classes (singletons), leading to linear extensions that are strict total orders without ties.

Existence and Properties

Order-extension principle

The order-extension principle, also known as Szpilrajn's theorem, asserts that for any set XX equipped with a partial order ≤\leq, there exists a total order ⪯\preceq on XX such that x≤yx \leq y implies x⪯yx \preceq y for all x,y∈Xx, y \in X. This guarantees that every partial order can be "linearized" while preserving its original comparability relations. The theorem was proved by Edward Szpilrajn in 1930. A standard proof relies on . Consider the collection E\mathcal{E} of all partial orders on XX that contain the original partial order, partially ordered by inclusion. Every chain in E\mathcal{E} has an upper bound given by the union of its members, which remains a partial order; thus, E\mathcal{E} is inductive. By , E\mathcal{E} has a maximal element RR. To show RR is total, suppose a,Ra, R-incomparable to bb; then adjoining aR′ba R' b (and its ) to RR yields a strictly larger partial order in E\mathcal{E}, contradicting maximality. Hence, RR is a total order extending the original. For countable posets, a choice-free proof exists via : enumerate the elements and iteratively extend the order along countable ordinals, deciding comparability for each new pair while maintaining partial order properties. The principle extends to preorders. Every preorder on XX admits a total preorder extension, obtained by forming the quotient poset under the associated equivalence relation (where x∼yx \sim y if x≤yx \leq y and y≤xy \leq x), applying Szpilrajn's theorem to extend this poset to a , and lifting the extension back to XX via the quotient map. This result, while stated earlier by , was rigorously proved by Bengt Hansson in 1973.

Characterization of linear extensions

A linear extension of a partial order PP can be characterized topologically as a ≺\prec on the same set such that for all a,b∈Pa, b \in P, if a<Pba < _P b (where <P< _P denotes the strict partial order, i.e., the of the strict order relations in PP), then a≺ba \prec b. This ensures that the total order extends the partial order by respecting all existing comparabilities without introducing contradictions. From an viewpoint, a linear extension can be seen as an order-preserving injection σ:P→N\sigma: P \to \mathbb{N} (or equivalently, into the chain of the poset's elements labeled 1<2<⋯<n1 < 2 < \cdots < n) that is bijective onto its image, forming an order-embedding of PP into a total order; this preserves key structural invariants such as the height of PP (the size of the longest ) and the width of PP (the size of the largest ), since chains and antichains map to substructures of matching sizes in the target . A defining property is that elements incomparable under the non-strict partial order ≤P\leq_P (i.e., neither a≤Pba \leq_P b nor b≤Pab \leq_P a) must become comparable under ≺\prec, ordered in either direction as long as it does not conflict with other relations in PP. To verify whether a candidate total order ≺\prec is a linear extension of PP, examine all pairs (a,b)(a, b) where a<Pba < _P b and confirm that a≺ba \prec b holds in each case; this direct check suffices since ≺\prec is already total. For example, consider a poset with elements a<ba < b and cc incomparable to both aa and bb. Valid linear extensions include a≺c≺ba \prec c \prec b and a≺b≺ca \prec b \prec c, both respecting a≺ba \prec b, but exclude c≺a≺bc \prec a \prec b or b≺a≺cb \prec a \prec c as they violate the original relation.

Dilworth's theorem connections

Dilworth's theorem asserts that in any finite (poset), the size of a maximum equals the minimum number of needed to partition the poset. This equivalence between the width ww of the poset (the size of its largest ) and the minimum chain partition size provides a foundational link to linear extensions, as any linear extension must preserve the total order within each chain of such a partition. In a linear extension, elements from different chains in a partition can be interleaved arbitrarily, provided the overall ordering respects the poset's relations. For a chain partition into kk chains of sizes n1,…,nkn_1, \dots, n_k where ∑ni=n\sum n_i = n (the poset size), the total number of possible interleavings is the multinomial coefficient n!n1!⋯nk!\frac{n!}{n_1! \cdots n_k!}, which upper-bounds the number of linear extensions since additional incomparabilities may further constrain the orderings. By , the smallest achievable kk is ww, implying that linear extensions of a poset of width ww necessarily involve shuffling at least ww chains; this minimal kk often yields the strongest such bound when the chain sizes are as balanced as possible, influencing enumeration strategies and asymptotic estimates. This connection manifests prominently in the Boolean lattice BnB_n of subsets of an nn-element set ordered by inclusion, where the width is (n⌊n/2⌋)\binom{n}{\lfloor n/2 \rfloor} by Sperner's theorem. BnB_n admits a symmetric chain decomposition into exactly (n⌊n/2⌋)\binom{n}{\lfloor n/2 \rfloor} rank-symmetric chains, achieving Dilworth's minimum and partitioning the lattice such that each chain spans symmetrically across the middle rank. Linear extensions of BnB_n thus correspond to shuffles of these symmetric chains that additionally respect cross-inclusion relations between chains, providing a structured framework for bounding and analyzing the total number of extensions via the associated multinomial coefficient. Dually, aids in lower bounds on linear extensions through partitions (via the dual theorem of Mirsky), but its primary role in this context is enabling upper bounds through optimal decompositions, which constrain the possible orderings and facilitate combinatorial insights into extension counts.

Mirsky's theorem and

Mirsky's theorem, a dual to , states that for any finite PP, the minimum number of into which PP can be partitioned equals the size of the longest in PP. This theorem connects directly to linear extensions, as any linear extension of PP must preserve all comparabilities in PP, including those defining ; thus, every embeds as a totally ordered increasing in the linear extension. The of PP, defined as the of its longest , therefore imposes a fundamental constraint on linear extensions by requiring that such a maximal appear in strictly increasing order along the . In any linear extension, the poset's height corresponds to the length of the relative to the original partial order, ensuring that no longer can emerge while respecting the extension's compatibility. For instance, if PP is a single of size hh, then PP has exactly one linear extension, which rigidly preserves the chain's order without any interleaving possibilities. This chain preservation bounds the possible "spread" or interleaving of elements across linear extensions, limiting how much incomparable elements can disrupt the relative positioning of chain members, in duality to the width-based constraints from antichain partitions.

Combinatorial Aspects

Counting linear extensions

The number of linear extensions of a PP, denoted e(P)e(P), counts the total orders on the ground set of PP that respect the relations in PP. For simple posets, recursive formulas facilitate computation. In particular, for an consisting of two incomparable elements, e(P)=2e(P) = 2, which equals twice the number of linear extensions of the empty subposet (where e(∅)=1e(\emptyset) = 1). More generally, e(P)e(P) satisfies the deletion recursion e(P)=∑m∈min⁡(P)e(P∖m)e(P) = \sum_{m \in \min(P)} e(P \setminus m), where min⁡(P)\min(P) is the set of minimal elements of PP; this allows bottom-up computation by successively deleting minimal elements. For series-parallel posets, explicit recursions apply: if P+QP + Q is the , then e(P+Q)=(∣P∣+∣Q∣∣P∣)e(P)e(Q)e(P + Q) = \binom{|P| + |Q|}{|P|} e(P) e(Q); if P⊕QP \oplus Q is the ordinal sum (with all elements of PP below those of QQ), then e(P⊕Q)=e(P)e(Q)e(P \oplus Q) = e(P) e(Q). A prominent closed-form formula arises for the poset corresponding to a Young diagram λ\lambda of size nn, viewed as boxes ordered by containment in rows and columns. Here, e(λ)e(\lambda) equals the number of standard Young tableaux of shape λ\lambda, given by the hook-length formula: e(λ)=n!∏(i,j)∈λhλ(i,j),e(\lambda) = \frac{n!}{\prod_{(i,j) \in \lambda} h_{\lambda}(i,j)}, where hλ(i,j)h_{\lambda}(i,j) is the hook length at cell (i,j)(i,j), defined as the number of cells to the right and below (i,j)(i,j) plus one. This formula, originally proved probabilistically, connects linear extensions to and random walks. Algorithms for exact computation include dynamic programming over the lattice of order ideals (down-sets) of PP, where states track the number of ways to reach each ideal while building extensions; this runs in time O(cn)O(c^n) for c≈3c \approx 3 in the worst case but is polynomial-time for posets of bounded width by . Another geometric approach computes e(P)e(P) via the order polytope O(P)⊆[0,1]∣P∣O(P) \subseteq [0,1]^{|P|}, whose vertices correspond to indicator functions of linear extensions; the normalized volume satisfies \vol(O(P))=e(P)/n!\vol(O(P)) = e(P) / n!, and the LO(P)(t)L_{O(P)}(t) of O(P)O(P) enumerates integer points in t⋅O(P)t \cdot O(P) as multiset extensions, enabling volume extraction through interpolation for small posets. Despite these methods, computing e(P)e(P) exactly for general posets is #P-complete, even for height-2 or dimension-2 posets, implying no polynomial-time algorithm unless P = NP. Approximations via sampling, such as on the extension graph, yield (1±ϵ)(1 \pm \epsilon)-multiplicative estimates with high probability in time polynomial in nn and 1/ϵ1/\epsilon, balancing the intractability for large instances. Asymptotic behavior of e(P)e(P) often depends on structural parameters like width and height. For the Boolean lattice BkB_k of width (kk/2)\binom{k}{k/2}, log⁡e(Bk)≈2kH(k/2,k/2)\log e(B_k) \approx 2^k H(k/2, k/2), where HH is binary entropy, providing exponential growth tied to the central width. In general graded posets, log⁡e(P)\log e(P) approximates the over hh of log⁡w(h) dh\log w(h) \, dh, where w(h)w(h) is the width (maximum size) at level hh, reflecting multiplicative contributions from layer-wise interleavings.

Applications in algebraic combinatorics

Linear extensions play a central role in the enumeration of standard Young tableaux (SYT). For a partition λ\lambda of nn, the poset PλP_\lambda associated to the Young diagram of shape λ\lambda has elements corresponding to the boxes, ordered by the southeast relation: a box at position (i,j)(i,j) precedes (i′,j′)(i',j') if i≤i′i \leq i' and j≤j′j \leq j'. There is a natural bijection between the SYT of shape λ\lambda and the linear extensions of PλP_\lambda, as each SYT provides a labeling of the boxes with 11 to nn that respects both row and column increases, equivalent to a total order extending the poset relations. This connection allows the hook-length formula to directly count linear extensions of Young diagram posets. The number of linear extensions e(Pλ)e(P_\lambda) is given by e(Pλ)=n!∏(i,j)∈λh(i,j),e(P_\lambda) = \frac{n!}{\prod_{(i,j) \in \lambda} h(i,j)}, where h(i,j)h(i,j) is the hook length of the box at (i,j)(i,j), defined as the number of boxes to the right and below it, plus one for the box itself. This formula, originally derived for SYT, thus provides an explicit product expression for e(Pλ)e(P_\lambda). A notable result linking linear extensions to other combinatorial objects is Stanley's theorem on the boolean lattice. The generating function for the linear extensions of the boolean lattice BnB_n (the power set of $$ ordered by inclusion), enumerated by , equals the qq-factorial q!_q!, whose coefficients are the Mahonian numbers. Independently, the Mahonian numbers also arise as the distribution of over SYT of the shape (n−1,n−2,…,1)(n-1, n-2, \dots, 1), establishing an enumerative bridge between these structures via qq-analogues. In permutation enumeration, linear extensions model topological sorts of posets, yielding counts of permutations that avoid patterns induced by the poset relations. For a poset PP on $$, the linear extensions are precisely the permutations π\pi such that if i≺ji \prec j in PP, then π−1(i)<π−1(j)\pi^{-1}(i) < \pi^{-1}(j), equivalent to avoiding certain classical or consecutive patterns corresponding to forbidden inversions. This framework connects linear extension counts to pattern-avoiding permutation classes, with applications in refining enumerations beyond simple avoidance sets. For example, consider the poset PP for the 3×33 \times 3 rectangular grid, isomorphic to the Young diagram of shape (3,3,3)(3,3,3) with 9 elements. The number of linear extensions e(P)=42e(P) = 42, matching the number of SYT of this shape via the hook-length formula, illustrating the direct correspondence in this algebraic combinatorial setting.

References

  1. https://mathworld.wolfram.com/LinearExtension.html
  2. http://www.columbia.edu/~md3405/DT_Order_15.pdf
  3. https://ncatlab.org/nlab/show/linear%2Bextension%2Bof%2Ba%2Bpartial%2Border
  4. https://math.dartmouth.edu/~pw/M100W11/seth.pdf
  5. https://www.geeksforgeeks.org/topological-sorting/
  6. https://trotter.math.gatech.edu/papers/31.pdf
  7. https://www.ijcai.org/Proceedings/2018/0710.pdf
  8. https://www.cs.fsu.edu/~lacher/courses/MAD3105/lectures/s1_4partord.pdf
  9. https://mathworld.wolfram.com/PartialOrder.html
  10. https://ncatlab.org/nlab/show/total+order
  11. https://www.cs.mcgill.ca/~mdresc/combinatorics.pdf
  12. https://users.math.msu.edu/users/magyarp/math880/Gen-Fun-Construct.pdf
  13. https://mathworld.wolfram.com/HasseDiagram.html
  14. http://www.columbia.edu/~md3405/Behave_Col_UM_3_15.pdf
  15. http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf
  16. https://arxiv.org/abs/1708.04711
  17. https://www.isa-afp.org/entries/Szpilrajn.html
  18. https://arxiv.org/abs/1111.1390
  19. https://web.pdx.edu/~caughman/Ewan501.pdf
  20. https://users.utu.fi/harju/orderedsets/Mainorder.pdf
  21. https://arxiv.org/abs/2001.03670
  22. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p53
  23. https://math.mit.edu/~rstan/transparencies/chains-antichains.pdf
  24. https://www.math.ucla.edu/~pak/papers/LEsurvey11.pdf
  25. https://link.springer.com/article/10.1007/s00453-018-0496-4
  26. https://math.mit.edu/~rstan/papers/evac.pdf
  27. https://arxiv.org/pdf/1408.4497
  28. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf
  29. https://arxiv.org/abs/1905.02309
  30. https://www.math.ucla.edu/~pak/lectures/Slides/Pak-BCC-talk-July-2019.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.