Linear extension: Difference between revisions

Revision as of 23:21, 25 August 2019

Revision as of 21:24, 18 December 2019

Line 95:

[[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 ''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=Matematicheskie Zametki|volume=4|pages=511–518}}.</ref><ref>{{citation