Back to Search
Start Over
Dimension is polynomial in height for posets with planar cover graphs.
- Source :
-
Journal of Combinatorial Theory - Series B . Mar2024, Vol. 165, p164-196. 33p. - Publication Year :
- 2024
-
Abstract
- We show that height h posets that have planar cover graphs have dimension O (h 6). Previously, the best upper bound was 2 O (h 3). Planarity plays a key role in our arguments, since there are posets such that (1) dimension is exponential in height and (2) the cover graph excludes K 5 as a minor. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PARTIALLY ordered sets
*POLYNOMIALS
*PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 165
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 174580364
- Full Text :
- https://doi.org/10.1016/j.jctb.2023.10.009