Dimension of posets with planar cover graphs excluding two long incomparable chains
arXiv:1608.08843 · doi:10.1016/j.jcta.2018.11.016
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 , there is a constant such that if is a poset with a planar cover graph and excludes , then . 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.
arXiv commentNew section on connections with graph minors, small corrections
References in corpus (9)
- Tree-width and dimension
- Minors and dimension
- Dimension and cut vertices: an application of Ramsey theory
- Planar posets have dimension at most linear in their height
- Posets with cover graph of pathwidth two have bounded dimension
- First-Fit is Linear on Posets Excluding Two Long Incomparable Chains
- An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
- Sparsity and dimension
- An extremal problem on crossing vectors