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

DOI10.1016/J.JCTA.2018.11.016MaRDI QIDQ1734698zbMATH OpenOpenAlexWikidataFDO

Authors David M. Howard, Noah Streib, Bartosz Walczak, William T. Trotter, Rui Dong Wang

Publication date 27 March 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08843

zbMATH Keywords

dimensionplanar graphspartially ordered setscover graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorics of partially ordered sets (06A07)

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 $kgeq1$, there is a constant $d$ such that if $P$ is a poset with a planar cover graph and $P$ excludes $mathbfk+mathbfk$, then $dim(P)leqd$. 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.

Recommendations

• The dimension of posets with planar cover graphs.
• Dimension and height for posets with planar cover graphs.
• Dimension and height for posets with planar cover graphs
• Minors and dimension
• Minors and dimension

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3585462 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• A bound on the dimension of interval orders
• An extremal problem on crossing vectors.
• An improved bound for first-fit on posets without two long incomparable chains
• Dimension and cut vertices: an application of Ramsey theory
• Dimension and height for posets with planar cover graphs.
• Dimension, graph and hypergraph coloring
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• First-Fit is linear on posets excluding two long incomparable chains
• Forcing posets with large dimension to contain large standard examples
• Interval orders and dimension
• Intransitive indifference with unequal indifference intervals
• Minors and dimension
• Nowhere dense graph classes and dimension
• On the dimension of partially ordered sets
• On the dimension of posets with cover graphs of treewidth 2
• On-line dimension for posets excluding two long incomparable chains
• Partially Ordered Sets
• Planar Posets Have Dimension at Most Linear in Their Height
• Planar posets, dimension, breadth and the number of minimal elements
• Posets with cover graph of pathwidth two have bounded dimension
• Sparsity and dimension
• The dimension of planar posets
• The dimension of posets with planar cover graphs.
• Topological minors of cover graphs and dimension
• Tree-width and dimension

Cited in

(9)

• Improved bound for the dimension of posets of treewidth two
• Removing critical pairs
• Planar posets, dimension, breadth and the number of minimal elements
• On the transitivity coefficients for minimal posets with nonpositive quadratic Tits form
• Topological minors of cover graphs and dimension
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• The dimension of posets with planar cover graphs.
• Dimension and height for posets with planar cover graphs.
• Excluding a ladder

This page was built for publication: Dimension of posets with planar cover graphs excluding two long incomparable chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1734698)