Speaker: Jeff Kahn (Rutgers University)

Title: Balancing extensions in posets of large width

Abstract: 

We revisit two old conjectures on linear extensions in finite partially ordered sets (posets) \(P\). 

[A \emph{linear extension} of \(P\) is a linear ordering compatible with the poset relations. A \emph{chain} (\emph{antichain}) is a totally ordered (unordered) set, and the \emph{width}, \(w(P)\), is the maximum size of an antichain in \(P\).] 

Let \(p(x \prec y)\) be the probability that \(x\) precedes \(y\) in a uniformly random linear extension, and set
\[
\delta_{xy} = \min\{p(x \prec y), p(y \prec x)\} \quad \text{and} \quad \delta(P)=\max \delta_{xy},
\]
the max over distinct \(x,y\in P\). The conjectures are: 

\textbf{Conjecture 1} (the ``1/3-2/3 Conjecture''). \emph{If \(P\) is not a chain then}
\[
\delta(P)\geq 1/3.
\]
\textbf{Conjecture 2.} \emph{If \(w(P)\to\infty\), then}
\[
\delta(P)\to 1/2
\]
(that is, \(\delta(P)>1/2-o(1)\), where \(o(1)\to 0\) as \(w(P)\to\infty\)).

We are still far from proving either of these, but make some interesting progress.
Joint with Max Aires.