论文标题
随机的两分poset和极端问题
Random bipartite posets and extremal problems
论文作者
论文摘要
以前，ErdőS，Kierstead和Trotter研究了随机高度的尺寸〜$ 2 $部分订购的集合。他们的研究主要是由两个目标动机：（1）〜分析Füredi-kahn上限在最高程度方面的相对紧密度； （2）〜开发用于估计$ n $点的随机标记poset的预期维度的机械。由于这些原因，他们的大部分努力都集中在案件上，$ 0 <p \ le 1/2 $。虽然给出了$ 1/2 \ le p <1 $的范围，但原始纸张中结果的相对准确性被降低，$ p $接近$ 1 $。 由两个极端问题涉及涉及迫使POSET包含大型标准例子的条件的极端问题，我们被迫重新审视这一主题，但现在主要强调了$ 1/2 \ le P <1 $的范围。我们的分析表明，随着$ p $接近〜$ 1 $，尺寸的预期值增加然后减少，在否定的情况下回答了原始论文中提出的问题。在此过程中，我们应用了Talagrand和Janson的不平等，与拉丁矩形和Euler产品功能建立联系，并在两个极端问题上取得进展。
Previously, Erdős, Kierstead and Trotter investigated the dimension of random height~$2$ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the Füredi-Kahn upper bounds on dimension in terms of maximum degree; and (2)~developing machinery for estimating the expected dimension of a random labeled poset on $n$ points. For these reasons, most of their effort was focused on the case $0<p\le 1/2$. While bounds were given for the range $1/2\le p <1$, the relative accuracy of the results in the original paper deteriorated as $p$ approaches~$1$. Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range $1/2\le p<1$. Our sharpened analysis shows that as $p$ approaches~$1$, the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems.
