Planar Posets that are Accessible from Below Have Dimension at Most 6

被引：0

作者：

Csaba Biró

Bartłomiej Bosek

Heather C. Smith

William T. Trotter

Ruidong Wang

Stephen J. Young

机构：

[1] University of Louisville,Department of Mathematics

[2] Jagiellonian University,Theoretical Computer Science Department, Faculty of Mathematics and Computer Science

[3] Davidson College,Department of Mathematics and Computer Science

[4] Georgia Institute of Technology,School of Mathematics

[5] Blizzard Entertainment,undefined

[6] Pacific Northwest National Laboratory,undefined

来源：

Order | 2021年 / 38卷

关键词：

Dimension; Planar poset; Accessible from below poset;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：21 / 36

页数：15

共 10 条

[1] Planar Posets that are Accessible from Below Have Dimension at Most 6
Biro, Csaba
Bosek, Bartlomiej
Smith, Heather C.
Trotter, William T.
Wang, Ruidong
Young, Stephen J.
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2021, 38 (01): : 21 - 36
[2] PLANAR POSETS HAVE DIMENSION AT MOST LINEAR IN THEIR HEIGHT
Joret, Gwenael
Micek, Piotr
Wiechert, Veit
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (04) : 2754 - 2790
[3] Planar Posets, Dimension, Breadth and the Number of Minimal Elements
Trotter, William T.
Wang, Ruidong
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2016, 33 (02): : 333 - 346
[4] Planar Posets, Dimension, Breadth and the Number of Minimal Elements
William T. Trotter
Ruidong Wang
Order, 2016, 33 : 333 - 346
[5] The Dimension of Posets with Planar Cover Graphs
Felsner, Stefan
Trotter, William T.
Wiechert, Veit
GRAPHS AND COMBINATORICS, 2015, 31 (04) : 927 - 939
[6] The Dimension of Posets with Planar Cover Graphs
Stefan Felsner
William T. Trotter
Veit Wiechert
Graphs and Combinatorics, 2015, 31 : 927 - 939
[7] Dimension is polynomial in height for posets with planar cover graphs
Kozik, Jakub
Micek, Piotr
Trotter, William T.
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 165 : 164 - 196
[8] Posets with Cover Graph of Pathwidth two have Bounded Dimension
Csaba Biró
Mitchel T. Keller
Stephen J. Young
Order, 2016, 33 : 195 - 212
[9] Posets with Cover Graph of Pathwidth two have Bounded Dimension
Biro, Csaba
Keller, Mitchel T.
Young, Stephen J.
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2016, 33 (02): : 195 - 212
[10] Dimension of posets with planar cover graphs excluding two long incomparable chains
Howard, David M.
Streib, Noah
Trotter, William T.
Walczak, Bartosz
Wang, Ruidong
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2019, 164 : 1 - 23

← 1 →