View PDF HTML (experimental)

Abstract:One of the possible cryptomorphic definitions of a partially ordered set (= a poset) $P$ on a non-empty finite ground set $N$ is in terms of the set ${\cal L}(P)$ of all its linear extensions, that is, in terms of the set of total orders on $N$ consistent with $P$. Any total order on $N$ can be interpreted as a node of a particular graph, called the permutohedral graph (over $N$), because it is indeed the graph of a certain polytope in $\mathbb{R}^{N}$, known as the permutohedron.
It is shown in the paper that a non-empty set of total orders on $N$ equals to ${\cal L}(P)$ for some poset $P$ on $N$ if and only if it is a geodetically convex set in the permutohedral graph. This result means that a purely graphical concept of geodetical convexity in this graph is a cryptomorphic definition of a finite poset. In particular, the lattice of geodetically convex sets in this graph is graded and its height function is described in graphical terms. A counter-example, however, shows that the height function does not correspond to the usual graphical diameter, relating this matter to a combinatorial concept of the dimension of a poset.
Two alternative cryptomorphic views on a poset $P$ on $N$ are also discussed. The geometric counterpart is its full-dimensional braid cone in $\mathbb{R}^{N}$, while a combinatorial alternative is a topology on $N$ distinguishing points, often referred as a (finite) distributive lattice.

Submission history

From: Milan Studeny [view email]
[v1] Fri, 14 Nov 2025 15:51:19 UTC (34 KB)
[v2] Mon, 24 Nov 2025 10:21:15 UTC (37 KB)
[v3] Sun, 2 Aug 2026 05:33:49 UTC (46 KB)