Computer Science/Discrete Mathematics Seminar I

Abstract: A linear extension of $P$ is a linear ordering compatible with the poset relations. Let $p(x<y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension, and let $\delta(x, y) = \min(p(x < y), p(y < x))$ and $\delta(P)$ be the maximum value of $\delta(x, y)$ over all $x, y$ in $P$. The following two conjectures about $\delta(P)$ are both well-known:

1. (The "1/3-2/3 Conjecture") $\delta(P) \geq \frac{1}{3}$ whenever $P$ is not a chain.
2. (The "Kahn-Saks Conjecture") $\delta(P) \to \frac{1}{2}$ as $w(P) \to \infty$ (where $w(P)$ is the maximum size of an antichain in $P$).

While still far from either of these, we prove a number of conditions for $\delta(P) \to \frac{1}{2}$ and $\delta(P) \geq \frac{1}{e} - o(1)$, using a mix of geometric and probabilistic techniques. Joint with Jeff Kahn.