A Family of Partially Ordered Sets with Small Balance Constant
A Family of Partially Ordered Sets with Small Balance Constant
复制标题
具有小平衡常数的偏序集族
DOI：
--
复制
发表时间：
2017
影响因子：
0.7
通讯作者：
Evan Chen
中科院分区：
文献类型：
--
作者：
Evan Chen
给定一个有限偏序集$\mathcal{P}$以及两个不同的元素$x$和$y$，我们令$\operatorname{pr}_{\mathcal{P}}(x \prec y)$表示$\mathcal{P}$的线性扩张中$x$在$y$之前的比例。那么$\mathcal{P}$的平衡常数$\delta(\mathcal{P})$定义为
\[
\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\}.
\]
$\frac{1}{3}$ - $\frac{2}{3}$猜想断言，当$\mathcal{P}$不是一个链时，$\delta(\mathcal{P}) \geq \frac{1}{3}$，但是除了某些平凡的例子外，何时等式成立，甚至平衡常数是否能趋近于$\frac{1}{3}$都不清楚。在本文中，我们通过展示一个平衡常数趋近于$\frac{1}{32}(93 - \sqrt{6697}) \approx 0.3488999$的偏序集序列，在该猜想上取得了一些进展，回答了布莱特韦尔的一个问题。这些提供了比任何其他已知的非平凡族更小的平衡常数。
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.