On the 1/3–2/3 Conjecture
On the 1/3–2/3 Conjecture
复制标题
关于1/3–2/3猜想
作者：
E. Olson;B. Sagan
Let (P, ≤) be a finite poset (partially ordered set), where P has cardinality n. Consider linear extensions of P as permutations x1x2⋯xn in one-line notation. For distinct elements x, y ∈ P, we define ℙ(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0≤α≤12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$0\leq \alpha \leq \frac {1}{2}$\end{document}, we say (x, y) is an α-balanced pair if α ≤ ℙ(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2. We also consider various posets which satisfy the stronger condition of having a 1/2-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length 2. Various questions for future research are posed.
Let (P, ≤) be a finite poset (partially ordered set), where P has cardinality n. Consider linear extensions of P as permutations x1x2⋯xn in one-line notation. For distinct elements x, y ∈ P, we define ℙ(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0≤α≤12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$0\leq \alpha \leq \frac {1}{2}$\end{document}, we say (x, y) is an α-balanced pair if α ≤ ℙ(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2. We also consider various posets which satisfy the stronger condition of having a 1/2-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length 2. Various questions for future research are posed.