1/3–2/3 conjecture

The 1/3–2/3 conjecture states that every finite partially ordered set with incomparable elements contains a pair whose probability of appearing in either order in a uniformly random linear extension lies between one-third and two-thirds.

Connect

Partially ordered set: A set equipped with a transitive, reflexive, and antisymmetric relation. The conjecture concerns incomparable pairs in finite partially ordered sets.
Two-element antichain: A partially ordered set of two elements with neither element below the other. Its sole pair is split evenly between the two possible linear extensions.
William T. Trotter: An American mathematician whose work includes major contributions to the theory of partially ordered sets. Trotter formulated the conjecture with William Winkler in the 1980s.
Computational complexity of linear extension counting: The study of the resources required to count linear extensions of a finite partially ordered set. Exact probability checks require comparing counts that are difficult to compute in general.
Linear extension: A total order on a partially ordered set that preserves every relation in the partial order. The conjectured probabilities count how often each order occurs among linear extensions.
Standard example: A family of posets with minimal realizers of increasing size, built from mutually constrained incomparable pairs. These posets test how structural complexity affects balance among pairwise orders.
William Winkler: An American mathematician known for work in combinatorics and discrete mathematics. Winkler co-formulated the conjecture with Trotter.
Approximate counting: Algorithms that estimate a combinatorial count within a specified error and confidence bound. Approximate extension counts help explore the conjecture on larger posets than exact methods allow.
Incomparable elements: Two elements of a partially ordered set for which neither is less than or equal to the other. Only such pairs can have their relative order vary across linear extensions.
Semiorder: A partial order representable by real-valued scores with a fixed threshold for declaring one element greater than another. The conjecture is known for the restricted class of semiorders.