期刊论文详细信息
JOURNAL OF COMBINATORIAL THEORY SERIES A 卷:164
Dimension of posets with planar cover graphs excluding two long incomparable chains
Article
Streib, Noah1  Trotter, William T.2  Walczak, Bartosz3  Wang, Ruidong4 
[1] Ctr Comp Sci, 17100 Sci Dr, Bowie, MD 20715 USA
[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
[3] Jagiellonian Univ, Fac Math & Comp Sci, Dept Theoret Comp Sci, Krakow, Poland
[4] Blizzard Entertainment, Irvine, CA 92618 USA
关键词: Partially ordered sets;    Dimension;    Cover graph;    Planar graphs;   
DOI  :  10.1016/j.jcta.2018.11.016
来源: Elsevier
PDF
【 摘 要 】

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 >= 1, there is a constant d such that if P is a poset with a planar cover graph and P excludes k k, then dim(P) <= 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. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free   

【 预 览 】
附件列表
Files Size Format View
10_1016_j_jcta_2018_11_016.pdf 496KB PDF download
  文献评价指标  
  下载次数:22次 浏览次数:1次