Order, lattices, ordered algebraic structures Chains, antichains, dimension Conjecture

1/3–2/3 conjecture

Builds on Partial order Total order Linear extension

Statement

Let $(P, \le)$ be a finite partially ordered set that is not a total order. For $x, y \in P$ , let $p(x, y)$ be the fraction of the linear extensions of $P$ in which $x$ comes before $y$ . Then there are elements $x, y \in P$ with $\frac{1}{3} \le p(x, y) \le \frac{2}{3}.$

Remarks

The conjecture is open. The bounds cannot be improved: for $P = \set{a, b, c}$ with $a < b$ as the only relation, the linear extensions are $cab$ , $acb$ and $abc$ , so $p(a, c) = 2/3$ , $p(c, b) = 2/3$ and $p(a, b) = 1$ . Kahn and Saks proved that a pair with $3/11 \le p(x, y) \le 8/11$ always exists. Brightwell, Felsner and Trotter improved the constant $3/11$ to $(5 - \sqrt{5})/10 \approx 0.276$ . Linial proved the conjecture for posets of width $2$ . The conjecture was later stated again, independently, by Michael Fredman and by Nathan Linial.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Linear extension concept
Partial order concept
Total order concept
1/3–2/3 conjecture conjecture

Tag	`AXCH7Z9FKH`
URI	`m2://AXCH7Z9FKH`
Kind	conjecture
Writing	W0 stub
MSC	06A07
Status	This copy of the site has no build data. Run `m2 status AXCH7Z9FKH`.
About	Linear extension
Uses	Partial order, Total order, Linear extension

1/3–2/3 conjecture

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here