PreprintarXiv licencearXiv
Poset dimension and maximum comparability degree
Abstract
In 1986, Füredi and Kahn showed that the dimension dim(P) of any finite poset P satisfies dim(P) = O(d log2 d), where d is the maximum degree of the comparability graph of P. Scott and Wood more recently improved this bound to one of the form d log1+o(1) d. We show that dim(P) = O(d log d), thus confirming that the corresponding lower bound of Erdős, Kierstead, and Trotter is tight up to the implicit constant.
Related
- The Kelly--Trotter conjecture and dimension of poset products
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- Large induced subgraphs with k vertices of maximum degree
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
BibTeX
@misc{groenland2026poset,
title = {{Poset dimension and maximum comparability degree}},
author = {Carla Groenland and Richard Montgomery and Rajko Nenadov and Lisa Sauermann},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17344},
eprint = {2609.17344},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17344},
}
RIS
TY - UNPB
TI - Poset dimension and maximum comparability degree
AU - Carla Groenland
AU - Richard Montgomery
AU - Rajko Nenadov
AU - Lisa Sauermann
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17344
UR - https://arxiv.org/abs/2609.17344
AB - In 1986, Füredi and Kahn showed that the dimension dim(P) of any finite poset P satisfies dim(P) = O(d log^2 d), where d is the maximum degree of the comparability graph of P. Scott and Wood more recently improved this bound to one of the form d log^1+o(1) d. We show that dim(P) = O(d log d), thus confirming that the corresponding lower bound of Erdős, Kierstead, and Trotter is tight up to the implicit constant.
ER -