"1/3 - 2/3 Conjecture" For every poset that is not a chain, there is some pair of elements x and y so that x appears abo

Definitions and mathematical statement

A linear extension of a finite poset $P=(X,\le_P)$ is a total ordering of $X$ in which $x<_P y$ always places $x$ before $y$. Let $\mathcal L(P)$ be the finite nonempty set of all linear extensions and choose $L$ uniformly from it. For distinct elements $x,y\in X$, define \[ p_P(x,y)=\Pr[x\text{ precedes }y\text{ in }L] =\frac{|\{L\in\mathcal L(P):x\text{ precedes }y\}|} {|\mathcal L(P)|}. \] The one-third--two-thirds conjecture asserts that every finite poset which is not a total order has an incomparable pair $x,y$ with \[ \frac13\le p_P(x,y)\le\frac23. \] Both endpoints are included, and the same pair must satisfy both bounds. Reversing the pair replaces the probability by its complement, so the assertion does not depend on how the pair is named.

Uniformity is over all linear extensions, not over the successive choices of currently minimal elements in an arbitrary sampling procedure; such a procedure need not produce the uniform law. Comparable elements have probability zero or one and therefore cannot be the required pair. Excluding total orders is necessary because they have no incomparable pairs. The conjecture concerns existence for every non-chain poset, without a bound on its width, height, or number of elements.

Short English statement

Must every finite poset that is not a total order have an incomparable pair whose relative order has probability between one third and two thirds?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100045 (AMR-030-0045), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Matroids, Lattices, and Posets, source-order bullet 45. Original source indexed by AMR-030-0045. https://people.math.sc.edu/cooper/combprob.html.