Back to Search Start Over

Dimension of posets with planar cover graphs excluding two long incomparable chains

Authors :
Howard, David M.
Streib, Noah
Trotter, William T.
Walczak, Bartosz
Wang, Ruidong
Source :
J. Comb. Theory Ser. A 164 (2019) 1-23
Publication Year :
2016

Abstract

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.<br />Comment: New section on connections with graph minors, small corrections

Details

Database :
arXiv
Journal :
J. Comb. Theory Ser. A 164 (2019) 1-23
Publication Type :
Report
Accession number :
edsarx.1608.08843
Document Type :
Working Paper
Full Text :
https://doi.org/10.1016/j.jcta.2018.11.016