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

DOI10.1016/J.JCTA.2018.11.016zbMATH Open1407.05067arXiv1608.08843OpenAlexW2515403108WikidataQ128737588 ScholiaQ128737588MaRDI QIDQ1734698FDOQ1734698

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)

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.

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

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

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)

Cites Work

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

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)