2025/11/14 by Milan Studený, Studený, Milan, Václav Kratochvíl +1
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Digital Image Processing Techniques #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2511.11785
One of possible cryptomorphic definitions of a partially ordered set (= a poset) P on a non-empty finite basic 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 of N consonant with P. Any total order of 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 ℝN, known as the permutohedron. It is shown in the paper that a non-empty set of total orders of N equals to \cal L(P) for some poset P on N iff 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 briefly commented. The geometric counterpart is its full-dimensional braid cone in ℝN, while a combinatorial alternative is a topology on N distinguishing points, often referred as a distributive lattice.