“1/3–2/3 conjecture”的意思、由来-开放百科全书

词条

1/3–2/3 conjecture

释义

Example
Definitions
History
Partial results
Applications
Generalizations and related results
Notes
References

In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y.

Example

The partial order formed by three elements a, b, and c with a single comparability relationship, {{nowrap|a ≤ b,}} has three linear extensions, {{nowrap|a ≤ b ≤ c,}} {{nowrap|a ≤ c ≤ b,}} and {{nowrap|c ≤ a ≤ b.}} In all three of these extensions, a is earlier than b. However, a is earlier than c in only two of them, and later than c in the third. Therefore, the pair of a and c have the desired property, showing that this partial order obeys the 1/3–2/3 conjecture.

This example shows that the constants 1/3 and 2/3 in the conjecture are tight; if q is any fraction strictly between 1/3 and 2/3, then there would not exist a pair x, y in which x is earlier than y in a number of partial orderings that is between q and {{nowrap|1 − q}} times the total number of partial orderings.^[1]

More generally, let P be any series composition of three-element partial orders and of one-element partial orders, such as the one in the figure. Then P forms an extreme case for the 1/3–2/3 conjecture in the sense that, for each pair x, y of elements, one of the two elements occurs earlier than the other in at most 1/3 of the linear extensions of P. Partial orders with this structure are necessarily series-parallel semiorders; they are the only known extreme cases for the conjecture and can be proven to be the only extreme cases with width two.^[2]

Definitions

A partially ordered set is a set X together with a binary relation ≤ that is reflexive, antisymmetric, and transitive. A total order is a partial order in which every pair of elements is comparable. A linear extension of a finite partial order is a sequential ordering of the elements of X, with the property that if x ≤ y in the partial order, then x must come before y in the linear extension. In other words, it is a total order compatible with the partial order. If a finite partially ordered set is totally ordered, then it has only one linear extension, but otherwise it will have more than one. The 1/3–2/3 conjecture states that one can choose two elements x and y such that, among this set of possible linear extensions, between 1/3 and 2/3 of them place x earlier than y, and symmetrically between 1/3 and 2/3 of them place y earlier {{nowrap|than x.^[3]}}

There is an alternative and equivalent statement of the 1/3–2/3 conjecture in the language of probability theory.

One may define a uniform probability distribution on the linear extensions in which each possible linear extension is equally likely to be chosen. The 1/3–2/3 conjecture states that, under this probability distribution, there exists a pair of elements x and y such that the probability that x is earlier than y in a random linear extension is between 1/3 and 2/3.^[3]

{{harvtxt|Kahn|Saks|1984}} define δ(P), for any partially ordered set P, to be the largest real number δ such that P has a pair x, y with x earlier than y in a number of linear extensions that is between δ and {{nowrap|1 − δ}} of the total number of linear extensions. In this notation, the 1/3–2/3 conjecture states that every finite partial order that is not total has {{nowrap|δ(P) ≥ 1/3}}.

History

The 1/3–2/3 conjecture was formulated by {{harvtxt|Kislitsyn|1968}}, and later made independently by Michael Fredman^[3] and by {{harvs|first=Nati|last=Linial|authorlink=Nati Linial|year=1984|txt}}.^[4] It was listed as a featured unsolved problem at the founding of the journal Order, and remains unsolved;^[4] {{harvtxt|Brightwell|Felsner|Trotter|1995}} call it "one of the most intriguing problems in the combinatorial theory of posets."

A survey of the conjecture is given by {{harvtxt|Brightwell|1999}}.

Partial results

The 1/3–2/3 conjecture is known to be true for certain special classes of partial orders, including partial orders of width two,^[5] partial orders of height two,^[6] partial orders with at most 11 elements,^[7] partial orders in which each element is incomparable to at most six others,^[8] series-parallel partial orders,^[9] and semiorders.^[10] In the limit as n goes to infinity, the proportion of n-element partial orders that obey the 1/3–2/3 conjecture approaches 100%.^[7]

{{harvtxt|Brightwell|Felsner|Trotter|1995}} proved that, for any finite partial order P that is not total, {{nowrap|δ(P) ≥ 1/2 − {{radic|5}}/10 ≈ 0.276.}} Their results improve previous weaker bounds of the same type.^[11] They use the probabilistic interpretation of δ(P) to extend its definition to certain infinite partial orders; in that context, they show that their bounds are optimal, in that there exist infinite partial orders with {{nowrap|1=δ(P) = 1/2 − {{radic|5}}/10.}}

Applications

{{harvtxt|Kahn|Saks|1984}} proposed the following application for the problem:

suppose one wishes to comparison sort a totally ordered set X, for which some partial order information is already known in the form of a partial order on X. In the worst case, each additional comparison between a pair x and y of elements may yield as little information as possible, by resolving the comparison in a way that leaves as many linear extensions as possible compatible with the comparison result. The 1/3–2/3 conjecture states that, at each step, one may choose a comparison to perform that reduces the remaining number of linear extensions by a factor of 2/3; therefore, if there are E linear extensions of the partial order given by the initial information, the sorting problem can be completed in at most log_3/2E additional comparisons.

However, this analysis neglects the complexity of selecting the optimal pair x and y to compare. Additionally, it may be possible to sort a partial order using a number of comparisons that is better than this analysis would suggest, because it may not be possible for this worst-case behavior to occur at each step of a sorting algorithm. In this direction, it has been conjectured that log_φE comparisons may suffice, where φ denotes the golden ratio.^[7]

A closely related class of comparison sorting problems is considered by {{harvtxt|Fredman|1976}}, among them the problem of comparison sorting a set X when the sorted order of X is known to lie in some set S of permutations of X. Here S is not necessarily generated as the set of linear extensions of a partial order. Despite this added generality, Fredman shows that X can be sorted using log₂|S| + O(|X|) comparisons. This same bound applies as well to the case of partial orders and shows that log₂E + O(n) comparisons suffice.

Generalizations and related results

{{harvtxt|Kahn|Saks|1984}} conjectured that, in the limit as w tends to infinity, the value of δ(P) for partially ordered sets of width w should tend to 1/2. In particular, they expect that only partially ordered sets of width two can achieve the worst case value {{nowrap|1=δ(P) = 1/3,}} and {{harvtxt|Aigner|1985}} stated this explicitly as a conjecture. The smallest known value of δ(P) for posets of width three is 14/39,^[12] and computer searches have shown that no smaller value is possible for width-3 posets with nine or fewer elements.^[6]

Marcin Peczarski^[7]^[8] has formulated a "gold partition conjecture" stating that in each partial order that is not a total order one can find two consecutive comparisons such that, if t_i denotes the number of linear extensions remaining after i of the comparisons have been made, then (in each of the four possible outcomes of the comparisons) {{nowrap|t₀ ≥ t₁ + t₂.}} If this conjecture is true, it would imply the 1/3–2/3 conjecture: the first of the two comparisons must be between a pair that splits the remaining comparisons by at worst a 1/3–2/3 ratio. The gold partition conjecture would also imply that a partial order with E linear extensions can be sorted in at most log_φE comparisons; the name of the conjecture is derived from this connection with the golden ratio.

It is #P-complete, given a finite partial order P and a pair of elements x and y, to calculate the proportion of the linear extensions of P that place x earlier than y.^[13]

Notes

1. ^{{harvtxt|Kahn|Saks|1984}}; {{harvtxt|Brightwell|Felsner|Trotter|1995}}.
2. ^{{harvtxt|Aigner|1985}}.
3. ^However, despite the close connection of {{harvtxt|Fredman|1976}} to the problem of sorting partially ordered data and hence to the 1/3–2/3 conjecture, it is not mentioned in that paper.
4. ^¹²³{{harvtxt|Brightwell|Felsner|Trotter|1995}}.
5. ^{{harvtxt|Linial|1984}}, Theorem 2.
6. ^¹{{harvtxt|Trotter|Gehrlein|Fishburn|1992}}.
7. ^¹²³{{harvtxt|Peczarski|2006}}.
8. ^¹{{harvtxt|Peczarski|2008}}.
9. ^{{harvtxt|Zaguia|2012}}
10. ^{{harvtxt|Brightwell|1989}}.
11. ^{{harvtxt|Kahn|Saks|1984}}; {{harvtxt|Khachiyan|1989}}; {{harvtxt|Kahn|Linial|1991}}; {{harvtxt|Felsner|Trotter|1993}}.
12. ^{{harvtxt|Saks|1985}}.
13. ^{{harvtxt|Brightwell|Winkler|1991}}.

References

{{citation

| last = Aigner | first = Martin | authorlink = Martin Aigner
| doi = 10.1007/BF00333131
| issue = 3
| journal = Order
| pages = 257–264
| title = A note on merging
| volume = 2
| year = 1985| doi-broken-date = 2019-03-06 }}.

{{citation

| last = Brightwell | first = Graham R.
| doi = 10.1007/BF00353656
| issue = 4
| journal = Order
| pages = 369–380
| title = Semiorders and the 1/3–2/3 conjecture
| volume = 5
| year = 1989}}.

{{citation

| last = Brightwell | first = Graham R.
| doi = 10.1016/S0012-365X(98)00311-2
| issue = 1–3
| journal = Discrete Mathematics
| pages = 25–52
| title = Balanced pairs in partial orders
| volume = 201
| year = 1999}}.

{{citation

{{citation

| last1 = Brightwell | first1 = Graham R.
| last2 = Winkler | first2 = Peter | author2-link = Peter Winkler
| doi = 10.1007/BF00383444
| issue = 3
| journal = Order
| pages = 225–242
| title = Counting linear extensions
| volume = 8
| year = 1991}}.

{{citation

| last1 = Felsner | first1 = Stefan
| last2 = Trotter | first2 = William T.
| contribution = Balancing pairs in partially ordered sets
| mr = 1249709
| location = Budapest
| pages = 145–157
| publisher = János Bolyai Mathematical Society
| series = Bolyai Society Mathematical Studies
| title = Combinatorics, Paul Erdős is eighty
| volume = 1
| year = 1993}}.

{{citation

| last = Fredman | first = M. L. | authorlink = Michael Fredman
| doi = 10.1016/0304-3975(76)90078-5
| issue = 4
| journal = Theoretical Computer Science
| pages = 355–361
| title = How good is the information theory bound in sorting?
| volume = 1
| year = 1976}}

{{citation

| last1 = Kahn | first1 = Jeff
| last2 = Linial | first2 = Nati | author2-link = Nati Linial
| doi = 10.1007/BF01275670
| issue = 4
| journal = Combinatorica
| pages = 363–368
| title = Balancing extensions via Brunn-Minkowski
| volume = 11
| year = 1991}}.

{{citation

| last1 = Kahn | first1 = Jeff
| last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician)
| doi = 10.1007/BF00565647
| issue = 2
| journal = Order
| pages = 113–126
| title = Balancing poset extensions
| volume = 1
| year = 1984}}.

{{citation

| last = Khachiyan | first = Leonid | authorlink = Leonid Khachiyan
| contribution = Optimal algorithms in convex programming decomposition and sorting
| editor-last = Jaravlev | editor-first = J.
| language = Russian
| location = Moscow
| pages = 161–205
| publisher = Nauka
| title = Computers and Decision Problems
| year = 1989}}. As cited by {{harvtxt|Brightwell|Felsner|Trotter|1995}}.

{{citation

| last = Kislitsyn | first = S. S.
| doi = 10.1007/BF01111312
| issue = 5
| journal = Mathematical Notes
| pages = 798–801
| title = A finite partially ordered set and its corresponding set of permutations
| volume = 4
| year = 1968}}.

{{citation

| last = Linial | first = Nati | authorlink = Nati Linial
| doi = 10.1137/0213049
| issue = 4
| journal = SIAM Journal on Computing
| pages = 795–801
| title = The information-theoretic bound is good for merging
| volume = 13
| year = 1984}}.

{{citation

| last = Peczarski | first = Marcin
| doi = 10.1007/s11083-006-9033-1
| issue = 1
| journal = Order
| pages = 89–95
| title = The gold partition conjecture
| volume = 23
| year = 2006}}.

{{citation

| last = Peczarski | first = Marcin
| doi = 10.1007/s11083-008-9081-9
| issue = 2
| journal = Order
| pages = 91–103
| title = The gold partition conjecture for 6-thin posets
| volume = 25
| year = 2008}}.

{{citation

| last = Saks | first = Michael | authorlink = Michael Saks (mathematician)
| title = Balancing linear extensions of ordered sets | department = Unsolved problems
| doi = 10.1007/BF00333138| journal = Order
| pages = 327–330
| volume = 2
| year = 1985| doi-broken-date = 2019-03-06 }}

{{citation

| last1 = Trotter | first1 = William T.
| last2 = Gehrlein | first2 = William V.
| last3 = Fishburn | first3 = Peter C. | author3-link = Peter C. Fishburn
| doi = 10.1007/BF00419038
| issue = 1
| journal = Order
| pages = 43–53
| title = Balance theorems for height-2 posets
| volume = 9
| year = 1992}}.

{{citation

| last1 = Zaguia| first1 = Imed
| issue = 2
| journal = Electronic Journal of Combinatorics
| pages = P29
| title = The 1/3-2/3 Conjecture for N-free ordered sets
| url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p29
| volume = 19
| year = 2012}}.{{DEFAULTSORT:1 3-2 3 conjecture}}

2 : Order theory|Conjectures

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。