Math Conjectures

1/3–2/3 Conjecture for Posets

OPENMajorConjectureProposed 1968 · Standard version

Canonical statement

Let P=(X,≤P)P=(X,\leq_P) be a finite poset that is not a chain, and let L(P)\mathcal L(P) be its set of linear extensions. For incomparable x,y∈Xx,y\in X, put
pP(x,y)=∣{L∈L(P):x<Ly}∣∣L(P)∣. p_P(x,y)=\frac{\lvert\{L\in\mathcal L(P):x<_L y\}\rvert}{\lvert\mathcal L(P)\rvert}.
Then some incomparable pair x,yx,y satisfies
13≤pP(x,y)≤23. \frac13\leq p_P(x,y)\leq\frac23.
View source LaTeX
Let \(P=(X,\leq_P)\) be a finite poset that is not a chain, and let \(\mathcal L(P)\) be its set of linear extensions. For incomparable \(x,y\in X\), put
\[
  p_P(x,y)=\frac{\lvert\{L\in\mathcal L(P):x<_L y\}\rvert}{\lvert\mathcal L(P)\rvert}.
\]
Then some incomparable pair \(x,y\) satisfies
\[
  \frac13\leq p_P(x,y)\leq\frac23.
\]
COMB-013:[Kislitsyn1968][BrightwellFelsnerTrotter1995][Brightwell1999][SilvaAlvarado2026BalanceClaim]
CombinatoricsTheoretical computer science

Notes

A linear extension of a finite poset PP is a listing of its elements consistent with the partial order, and for an incomparable pair x,yx,y one writes pP(x,y)p_P(x,y) for the proportion of linear extensions in which xx precedes yy. The 1/3–2/3 conjecture asserts that every finite poset that is not a chain has an incomparable pair with 13≤pP(x,y)≤23\tfrac13\le p_P(x,y)\le\tfrac23. It goes back to Kislitsyn in 1968 [Kislitsyn1968], and the constant 1/31/3 would be sharp: in the three-element poset with a single relation, every incomparable pair is split exactly 1/31/3 to 2/32/3.

The strongest bound valid for all posets guarantees a pair whose probability lies between (5−5)/10(5-\sqrt5)/10 and (5+5)/10(5+\sqrt5)/10, roughly between 0.2760.276 and 0.7240.724 [BrightwellFelsnerTrotter1995]; Brightwell's survey collects this together with the many special classes of posets for which the exact 1/31/3 bound is known [Brightwell1999].

A recent preprint claims an exact resolution for posets with a small number of bottlenecks, but its current version explicitly leaves the case of four or more bottlenecks open [SilvaAlvarado2026BalanceClaim]. The conjecture therefore remains open in general; a full proof must handle arbitrary finite posets.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.