solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看21944次
Dimension of posets with planar cover graphs excluding two long incomparable chains. (arXiv:1608.08843v2 [math.CO] UPDATED)
来源于:arXiv
It has been known for more than 40 years that there are posets with planar
cover graphs and arbitrarily large dimension. Recently, Streib and Trotter
proved that such posets must have large height. In fact, all known
constructions of such posets have two large disjoint chains with all points in
one chain incomparable with all points in the other. Gutowski and Krawczyk
conjectured that this feature is necessary. More formally, they conjectured
that for every $k\geq 1$, there is a constant $d$ such that if $P$ is a poset
with a planar cover graph and $P$ excludes $\mathbf{k}+\mathbf{k}$, then
$\dim(P)\leq d$. We settle their conjecture in the affirmative. We also discuss
possibilities of generalizing the result by relaxing the condition that the
cover graph is planar. 查看全文>>