Graphical view on linear extensions of finite posets

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 $\mathcal{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 $\mathcal{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.

39 pages, 6 figures, submitted to special issue of Algebraic Statistics in memory of Henry Wynn