1/3–2/3 conjecture
Statement
Let be a finite partially ordered set, so that is a reflexive, antisymmetric, transitive binary relation on the finite set . A linear extension of is a total order on such that implies for all . Let denote the set of linear extensions of , and for put
the proportion of linear extensions of in which precedes .
Suppose is not a total order, i.e. there exist with , and . Then there exists a pair of elements with
Equivalently, setting
every finite partially ordered set that is not a total order satisfies .
Record
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.