A family of partially ordered sets with small balance constant

Evan Chen¹

¹Massachussetts Institute of Technology

The electronic journal of combinatorics, Tome 25 (2018) no. 4

Résumé

Given a finite poset $\mathcal P$ and two distinct elements $x$ and $y$, we let $\operatorname{pr}_{\mathcal P}(x \prec y)$ denote the fraction of linear extensions of $\mathcal P$ in which $x$ precedes $y$. The balance constant $\delta(\mathcal P)$ of $\mathcal P$ is then defined by \[ \delta(\mathcal P) = \max_{x \neq y \in \mathcal P} \min \left\{ \operatorname{pr}_{\mathcal P}(x \prec y), \operatorname{pr}_{\mathcal P}(y \prec x) \right\}. \] The $1/3$-$2/3$ conjecture asserts that $\delta(\mathcal P) \ge \frac13$ whenever $\mathcal P$ is not a chain, but except from certain trivial examples it is not known when equality occurs, or even if balance constants can approach $1/3$.In this paper we make some progress on the conjecture by exhibiting a sequence of posets with balance constants approaching $\frac{1}{32}(93-\sqrt{6697}) \approx 0.3488999$, answering a question of Brightwell. These provide smaller balance constants than any other known nontrivial family.

Détail

DOI : 10.37236/7337

Classification : 06A07, 05A15
Mots-clés : poset, \(1/3\)-\(2/3\) conjecture, linear extension