Content deleted Content added
Citation bot (talk | contribs) m Alter: isbn, title, issue. Add: citeseerx, issue, title-link, doi. Removed parameters. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. |
m task, replaced: Matematicheskiye Zametki → Matematicheskie Zametki |
||
Line 4:
Given any partial orders ≤ and ≤<sup>*</sup> on a set ''X'', ≤<sup>*</sup> is a linear extension of ≤ exactly when (1) ≤<sup>*</sup> is a [[total order]] and (2) for every ''x'' and ''y'' in ''X'', if {{nowrap|''x'' ≤ ''y''}}, then {{nowrap|''x'' ≤<sup>*</sup> ''y''}}. It is that second property that leads mathematicians to describe ≤<sup>*</sup> as '''extending''' ≤.
Alternatively, a linear extension may be viewed as an [[order-preserving]] [[bijection]] from a partially ordered set ''P'' to a [[
== Order-extension principle ==
Line 107:
| year = 1992}}. 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 ''P'' that is not [[total order|totally ordered]] there exists a pair (''x'',''y'') of elements of ''P'' for which the linear extensions of ''P'' in which {{nowrap|''x'' < ''y''}} number between 1/3 and 2/3 of the total number of linear extensions of ''P''.<ref>{{citation|author=Kislitsyn, S. S.|year=1968|title=Finite partially ordered sets and their associated sets of permutations|journal=
| last = Brightwell | first = Graham R.
| doi = 10.1016/S0012-365X(98)00311-2
| |||