pith. sign in

arxiv: 2605.20877 · v1 · pith:QFA4MXQHnew · submitted 2026-05-20 · 🧮 math.CO

Navigating Posets with Few Maps

Stefan Felsner , J\k{e}drzej Hodor , Giacomo Ortali , Alexander Wolff This is my paper

Pith reviewed 2026-05-21 04:16 UTC · model grok-4.3

classification 🧮 math.CO
keywords posetsdimensionwidthatlas thicknessplane mapsmapabilityNP-completenessfixed-parameter tractability
0
0 comments X

The pith

The atlas thickness of any poset sits between half its dimension and its width plus one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces atlas thickness as the smallest number of plane maps of a poset such that every element is tight in at least one map, where an element is tight when dominance of its image point exactly reproduces the order relations. It proves that this thickness parameter always satisfies dim(P) ≤ 2 at(P) ≤ width(P) + 1. The connection matters because it ties a geometric representation of order via coordinate dominance to two classical parameters of posets. The authors also construct families of posets where atlas thickness grows doubly exponentially with dimension, showing the parameters are not always close. On the computational side they establish that computing the maximum number of tight elements in one map is NP-complete yet fixed-parameter tractable, and that deciding whether atlas thickness is at most 2 is NP-complete.

Core claim

The paper establishes that for every finite poset P, dim(P) ≤ 2 at(P) ≤ width(P) + 1. It further shows there exists a sequence of posets (P_n) such that at(P_n) is doubly exponential in dim(P_n). These relations are obtained by constructing collections of plane maps in which dominance exactly matches the order for as many elements as possible, and by relating the minimal size of such a covering collection both to a realizer of the dimension and to the size of a largest antichain. Computationally, determining the largest number of tight elements possible in a single map is NP-complete and deciding whether at(P) ≤ 2 is NP-complete, while the former problem is fixed-parameter tractable.

What carries the argument

A plane map of the poset elements into R^2 in which an element is tight when the dominance relation on its image point exactly reproduces the poset order for that element; atlas thickness is the size of the smallest collection of such maps whose tight elements together cover the entire poset.

If this is right

  • The width of any poset directly upper-bounds the number of plane maps required to make every element tight.
  • The dimension of any poset lower-bounds its atlas thickness.
  • Some families of posets require a number of maps that is doubly exponential in their dimension.
  • Deciding whether two maps suffice to cover all elements as tight is NP-complete.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear bound in width suggests that posets with small width admit geometric representations with a small number of dominance queries for successor computation.
  • The doubly exponential separation indicates that dimension alone can understate the number of maps needed for exact order reproduction.
  • The fixed-parameter tractability result for mapability opens the possibility of practical algorithms when the maximum number of tight elements per map is small.

Load-bearing premise

Every two-dimensional poset admits a single plane map in which every element is tight, so that dominance exactly reproduces the order without extraneous relations.

What would settle it

A concrete poset P for which at(P) exceeds width(P) + 1, or for which 2 at(P) falls below dim(P).

read the original 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,\leq)$ is an injective mapping of $X$ into the Cartesian plane $\mathbb{R}^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 $\mu$ if the following holds: $x<y$ in $P$ if and only if $\mu(y)$ dominates $\mu(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$, $\mathrm{dmap}(P)$, to be the maximum number of elements that are tight in a single map, and we define the atlas thickness of $P$, $\mathrm{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 $\mathrm{dim}(P) \le 2\mathrm{at}(P) \le \mathrm{width}(P)+1$. On the other hand, there exists a sequence of posets $(P_n)_{n \ge 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 $\mathrm{at}(P) \le 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces mapability dmap(P) (maximum number of tight elements in any single plane map) and atlas thickness at(P) (minimum number of plane maps needed so every element is tight in at least one). It proves that dim(P) ≤ 2 at(P) ≤ width(P) + 1 for every finite poset P, constructs a sequence of posets where at(P_n) grows doubly exponentially in dim(P_n), and shows that computing dmap(P) and deciding whether at(P) ≤ 2 are NP-complete while computing dmap(P) is FPT with respect to the natural parameter.

Significance. The new parameters connect geometric plane representations to classical poset invariants. The inequalities are derived directly from the definitions of dimension (via realizers) and width (via Dilworth decompositions), providing clean, parameter-free bounds. The doubly-exponential separation and the contrasting complexity results (NP-complete vs. FPT) are noteworthy contributions. Explicit constructions and reductions are strengths that support the claims.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'with respect to the natural parameter' for the FPT result should briefly indicate what the parameter is (e.g., dimension or number of elements) to improve immediate readability.
  2. [Introduction] The statement that every 2-dimensional poset admits a plane map in which all elements are tight follows from the definition of dimension, but a short explicit reminder of this fact in the introduction would help readers unfamiliar with realizer-based embeddings.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, the recognition of its significance in connecting geometric parameters to classical poset invariants, and the recommendation for minor revision. No specific major comments or criticisms were raised in the report.

Circularity Check

0 steps flagged

Derivations follow directly from classical poset definitions with no reduction to inputs

full rationale

The paper grounds its bounds in the standard definition of dimension (minimum realizer of linear extensions) and the explicit construction of a plane map from any two linear orders via coordinate ranks, where dominance exactly reproduces the intersection. The statement that every 2-dimensional poset admits a map with all elements tight follows immediately from this representation, without circular redefinition of dmap or at. The inequality dim(P) ≤ 2 at(P) is obtained by extracting one pair of linear orders per map from the x- and y-sorts, whose intersection covers the tight relations for those elements; covering all elements with at(P) maps therefore yields a realizer of size at most 2 at(P). The bound 2 at(P) ≤ width(P) + 1 is derived from a Dilworth decomposition into chains and antichains. The doubly-exponential separation and the NP-completeness/FPT results rest on explicit constructions and reductions whose steps are independent of fitted parameters or self-citations. No load-bearing step equates a derived quantity to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the standard definitions of poset dimension and width plus the new geometric definitions of tight elements and maps. No free parameters are fitted to data. The key background fact is that every 2-dimensional poset admits a map in which all elements are tight.

axioms (1)
  • domain assumption Every 2-dimensional poset admits a plane map such that every element is tight.
    Stated explicitly in the abstract as holding by definition and used to relate at(P) to dimension.
invented entities (1)
  • plane map with tight elements no independent evidence
    purpose: Geometric representation where dominance exactly matches the poset order for selected elements
    Newly defined tool for measuring how many elements can be made tight in one drawing.

pith-pipeline@v0.9.0 · 5918 in / 1460 out tokens · 34691 ms · 2026-05-21T04:16:12.818305+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Dilworth , title =

    Robert P. Dilworth , title =. Annals of Mathematics , volume =

    work page

  2. [2]

    Leon Mirsky , title =. Amer. Math. Monthly , volume =. 1971 , doi =

    work page 1971

  3. [3]

    Steven Chaplick and Krzysztof Fleszar and Fabian Lipp and Alexander Ravsky and Oleg Verbitsky and Alexander Wolff , title =. J. Graph Algorithms Appl. , year = 2023, volume = 27, number = 6, pages =

    work page 2023

  4. [4]

    Alastair Farrugia , title =. Electr. J. Comb. , volume = 11, number = 1, pages =

    work page

  5. [5]

    Lewis and Mihalis Yannakakis , title =

    John M. Lewis and Mihalis Yannakakis , title =. J. Comput. Syst. Sci. , volume =. 1980 , doi =

    work page 1980

  6. [6]

    The order dimension of the complete graph , journal =

    Serkan Ho. The order dimension of the complete graph , journal =. 1999 , issn =

    work page 1999

  7. [7]

    doi:10.2307/1998052 , journal =

    Kleitman, Daniel and Markowsky, George , title =. doi:10.2307/1998052 , journal =

    work page doi:10.2307/1998052

  8. [8]

    , title =

    Biró, Csaba and Hamburger, Peter and Pór, Attila and Trotter, William T. , title =. doi:10.1007/s00373-015-1624-4 , number = 3, journal =

    work page doi:10.1007/s00373-015-1624-4

  9. [9]

    A note on

    Ne. A note on. Irregularities of partitions (. 1989 , DOI =

    work page 1989

  10. [10]

    Yannakakis, Mihalis , title =. SIAM J. Algebr. Discrete Meth. , volume =. 1982 , doi =

    work page 1982

  11. [11]

    West , title =

    Douglas B. West , title =

    work page

  12. [12]

    , journal =

    Dushnik, Ben and Miller, Edwin W. , journal =. Partially ordered sets , volume =. 1941 , doi =

    work page 1941

  13. [13]

    Minimizing an Uncrossed Collection of Drawings , booktitle =

    Petr Hlin. Minimizing an Uncrossed Collection of Drawings , booktitle =. doi:10.1007/978-3-031-49272-3_8 , url =

    work page doi:10.1007/978-3-031-49272-3_8

  14. [14]

    On the Uncrossed Number of Graphs , booktitle =

    Balko, Martin and Hlin. On the Uncrossed Number of Graphs , booktitle =. 2024 , volume =. doi:10.4230/LIPIcs.GD.2024.18 , annote =

    work page doi:10.4230/lipics.gd.2024.18 2024

  15. [15]

    Unbent Collections of Orthogonal Drawings , booktitle =

    Todor Anti. Unbent Collections of Orthogonal Drawings , booktitle =

    work page

  16. [16]

    , title =

    McCreight, Edward M. , title =. SIAM J. Comput. , volume = 14, number = 2, pages =

    work page

  17. [17]

    On the complexity of the storyplan problem , journal =

    Carla Binucci and Emilio. On the complexity of the storyplan problem , journal =

    work page

  18. [18]

    Outerplanar and Forest Storyplans , booktitle =

    Jiří Fiala and Oksana Firman and Giuseppe Liotta and Alexander Wolff and Johannes Zink , editor =. Outerplanar and Forest Storyplans , booktitle =

    work page

  19. [19]

    Giuseppe Di Battista and Walter Didimo and Luca Grilli and Fabrizio Grosso and Giacomo Ortali and Maurizio Patrignani and Alessandra Tappini , title =. J. Graph Algorithms Appl. , volume = 27, number = 8, pages =

    work page