Planar posets that are accessible from below have dimension at most 6

DOI10.1007/S11083-020-09525-4MaRDI QIDQ2663166zbMATH OpenOpenAlexFDO

Authors Csaba Biró, Bartłomiej Bosek, Heather Smith, Stephen J. Young, William T. Trotter, Rui Dong Wang

Publication date 16 April 2021

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

accessible from below posetdimensionplanar poset

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: Planar posets can have arbitrarily large dimension. However, a planar poset of height $h$ has dimension at most $192h+96$, while a planar poset with $t$ minimal elements has dimension at most $2t+1$. In particular, a planar poset with a unique minimal element has dimension at most $3$. In this paper, we extend this result by showing that a planar poset has dimension at most $6$ if it has a plane diagram in which every minimal element is accessible from below.

Review text

In this paper, the authors consider dimension of posets. It is known that a planar poset of height \(h\) has dimension at most \(192h + 96\), while a planar poset with \(t\) minimal elements has dimension at most \(2t +1\). In particular, a planar poset with a unique minimal element has dimension at most 3. Definition. Let \(\mathbb{D}\) be a plane diagram for a poset \(P\), and let \(x\) be a minimal element of \(P\). We say that \(x\) is accessible from below when there is a positive number \(\epsilon = \epsilon(x)\) so that any point \(p\) in the plane which is distinct from \(x\), on the vertical ray emanating downwards from \(x\) and within distance \(\epsilon\) from \(x\) is in the exterior region. In particular, a plane diagram \(\mathbb{D}\) is accessible from below if every minimal element of \(P\) is accessible from below. In this paper, the authors extend the above stated result and prove the following result. Theorem. If \(P\) is an accessible from below poset, then \(\dim(P ) \leq 6\).

Recommendations

• Planar Posets Have Dimension at Most Linear in Their Height
• Planar posets, dimension, breadth and the number of minimal elements
• Planar graphs and poset dimension
• The dimension of posets with planar cover graphs.
• Dimension and height for posets with planar cover graphs

Cites work

• Boolean dimension and local dimension
• Boolean dimension and tree-width
• Boolean dimension, components and blocks
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• Dimension and cut vertices: an application of Ramsey theory
• Dimension and height for posets with planar cover graphs.
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 4118416 (Why is no real title available?)
• Local dimension is unbounded for planar posets
• Minors and dimension
• On the dimension of partially ordered sets
• On the dimension of posets with cover graphs of treewidth 2
• Partially Ordered Sets
• Planar Posets Have Dimension at Most Linear in Their Height
• Planar posets, dimension, breadth and the number of minimal elements
• 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

(4)

• Adjacency posets of outerplanar graphs
• Planar posets, dimension, breadth and the number of minimal elements
• Planar Posets Have Dimension at Most Linear in Their Height
• Forcing the wheel

This page was built for publication: Planar posets that are accessible from below have dimension at most 6

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