Semiorders and the 1/3–2/3 conjecture |
| |
Authors: | Graham R Brightwell |
| |
Institution: | (1) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, CB2 1SB Cambridge, England |
| |
Abstract: | A well-known conjecture of Fredman is that, for every finite partially ordered set (X, <) which is not a chain, there is a pair of elements x, y such that P(x, the proportion of linear extensions of (X, <) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, <) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width. |
| |
Keywords: | 06A10 |
本文献已被 SpringerLink 等数据库收录! |
|