Navigating Posets with Few Maps
Abstract
We study two new parameters for finite posets motivated by the problem of efficiently determining the set of successors of a given element. A plane map of a poset P=(X,≤) is an injective mapping of X into the Cartesian plane ℝ2. Given two different points a and b in the plane, we say that b dominates a if a<b coordinatewise. We say that an element x of P is tight in a plane map μ if the following holds: x<y in P if and only if μ(y) dominates μ(x). Note that, by definition, every 2-dimensional poset admits a map such that every element of the poset is tight. For any poset P, we define the mapability of P, dmap(P), to be the maximum number of elements that are tight in a single map, and we define the atlas thickness of P, at(P), to be the size of the smallest collection of maps such that every element is tight in at least one map of the collection. We relate these parameters to the classical notions of dimension and width: for every poset P, we show that dim(P) ≤ 2at(P) ≤ width(P)+1. On the other hand, there exists a sequence of posets (Pn)n ≥ 1 such that the atlas thickness of Pn is doubly exponential in the dimension of Pn. On the computational side, we prove that it is NP-complete, for a given poset P, to compute the mapability of P and to decide whether at(P) ≤ 2. In contrast to the latter, we show that computing the mapability of a poset is fixed-parameter tractable with respect to the natural parameter.
Related
BibTeX
@misc{felsner2026navigating,
title = {{Navigating Posets with Few Maps}},
author = {Stefan Felsner and Jędrzej Hodor and Giacomo Ortali and Alexander Wolff},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.20877},
eprint = {2605.20877},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.20877},
}
RIS
TY - UNPB
TI - Navigating Posets with Few Maps
AU - Stefan Felsner
AU - Jędrzej Hodor
AU - Giacomo Ortali
AU - Alexander Wolff
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.20877
UR - https://arxiv.org/abs/2605.20877
AB - We study two new parameters for finite posets motivated by the problem of efficiently determining the set of successors of a given element. A plane map of a poset P=(X,≤) is an injective mapping of X into the Cartesian plane ℝ^2. Given two different points a and b in the plane, we say that b dominates a if a<b coordinatewise. We say that an element x of P is tight in a plane map μ if the following holds: x<y in P if and only if μ(y) dominates μ(x). Note that, by definition, every 2-dimensional poset admits a map such that every element of the poset is tight. For any poset P, we define the mapability of P, dmap(P), to be the maximum number of elements that are tight in a single map, and we define the atlas thickness of P, at(P), to be the size of the smallest collection of maps such that every element is tight in at least one map of the collection. We relate these parameters to the classical notions of dimension and width: for every poset P, we show that dim(P) ≤ 2at(P) ≤ width(P)+1. On the other hand, there exists a sequence of posets (P_n)_n ≥ 1 such that the atlas thickness of P_n is doubly exponential in the dimension of P_n. On the computational side, we prove that it is NP-complete, for a given poset P, to compute the mapability of P and to decide whether at(P) ≤ 2. In contrast to the latter, we show that computing the mapability of a poset is fixed-parameter tractable with respect to the natural parameter.
ER -