Graphical view on linear extensions of finite posets

Milan Studen\'y; V\'aclav Kratochv\'il

Graphical view on linear extensions of finite posets

T0 review · 0 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A non-empty set of total orders on a finite set equals the linear extensions of some partial order exactly when it is geodetically convex in the permutohedral graph.

desk verdict A clean, honestly-scoped re-proof of a known characterization (geodesic convexity = linear extensions) with a few useful refinements; worth refereeing despite modest novelty. read the letter →

arxiv 2511.11785 v3 pith:CFDHAZRQ submitted 2025-11-14 math.CO

Milan Studený , Václav Kratochvíl This is my paper · ORCID

classification math.CO MSC 06A0706A1562R01

keywords finiteposetlinearextensiongeodeticallyconvexsetpermutohedralgraphgradedlatticedimensioncryptomorphismGaloisconnection

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that the finite partially ordered sets (posets) on a given ground set can be recognized entirely from their linear extensions: a non-empty collection of total orders equals the set L(P) of all linear extensions of some poset P precisely when it forms a geodetically convex set in the permutohedral graph — the graph whose vertices are the total orders and whose edges join orders that differ by swapping adjacent elements. Because geodetic convexity is a purely graph-theoretic notion, the result offers a cryptomorphic definition of finite posets. The paper proves the lattice of such convex sets is graded, with the height of a non-empty set equal to the number of distinct edge labels (inversions) inside it, and shows that this height is, in general, not the graph diameter — the discrepancy reflects the order dimension of the poset. Two further equivalent descriptions are derived: full-dimensional braid cones in Euclidean space, and finite topologies that distinguish points. The significance for a general reader is that a single structural property of a finite collection of orderings fully codes the partial order that produced it.

What carries the argument

The permutohedral graph over N: vertices are enumerations of N (total orders), adjacency is an adjacent transposition. The paper labels each edge by the unordered pair of elements being swapped, and the pivotal Lemma 2 says that a walk between two enumerations is a geodesic if and only if no label is repeated; the labels along any geodesic are exactly the inversions between the endpoints. This label-repetition property makes the halfspaces S_{u≺v} = {orders in which u precedes v} geodetically convex, and the same property underpins the reflection argument in the sufficiency direction. The lattice-theoretic layer, built from Galois connections between subsets of enumerations and binary relati

What would settle it

Compute, for |N|=4, the full vertex set of the permutohedral graph and list every subset that is geodetically convex; compare this list to the collection of sets L(P) for all posets on N. If any non-empty geodetically convex set is not a linear-extension set, Theorem 3 is false. Alternatively, search for a geodesic between two permutations that repeats an edge label; such a walk would falsify Lemma 2(ii), the proof's keystone.

Watch

Extended reading notes

Core claim

Theorem 3 is the paper's central claim: for |N| ≥ 2, a subset S of the vertices of the permutohedral graph on N is the linear-extension set L(P) of some poset P if and only if S is geodetically convex. Geodetic convexity requires that whenever two total orders lie in S, every total order that appears on every shortest path between them also lies in S. The necessity follows from the observation that the coatoms of the poset-based lattice — the halfspaces S_{u≺v} in which a fixed element u precedes v — are geodetically convex, because a geodesic that swapped u and v twice could be shortened. The sufficiency reconstructs the poset from S by defining a covering relation Cov(S) from the edges tha

Load-bearing premise

The whole equivalence turns on the lemma that a shortest path between two total orders never swaps the same pair of elements twice; if any geodesic could repeat a pair, the proof that order-precedence halfspaces are convex and the reconstruction of the poset from the 'covering' edges would both break.

Editorial extensions

If this is right

Finite posets become recognizable purely graphically: the set of linear extensions is convex in the permutohedral graph, and no extra data beyond the graph is needed to recover the poset.
The lattice of geodetically convex sets is graded: the height of a non-empty convex set equals the number of different edge labels (inversions) appearing in its induced subgraph, which is also the number of incomparable pairs of the corresponding poset.
The height and the graphical diameter of a convex set generally differ for ground sets with at least six elements; this failure is governed by the poset's dimension, so the height function encodes a finer invariant than diameter.
Relative to any fixed reference total order, every poset is representable by an interval in a Boolean lattice of size 3^{n choose 2}, yielding an elementary upper bound on the number of posets on an n-element set.
The description implies that the lattice of geodetically convex sets is anti-isomorphic to the lattice of all posets on N, so order-theoretic questions about posets can be translated into questions about convexity in the permutohedral graph.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's local trichotomy condition (each pair is either an inversion inside S, or ordered by the transitive closure of the covering relation, in one direction only) is conjectured to characterize convexity without checking all geodesics; if provable, it would give a fast way to test whether a given set of total orders comes from a poset, only requiring edge counts rather than all-pairs distanc
Because geodetic convexity is a property of the whole graph, the result suggests that algorithms that generate linear extensions by Markov-chain walks could be constrained to stay inside convex 'poset-compatible' regions, potentially improving sampling or counting procedures.
The equivalence between convex sets and linear-extension sets, combined with the braid-cone and topology translations, points toward a unified dictionary in which the same convexity criterion reappears as the normality of a fan of braid cones or the distributivity of a finite lattice; one could test this by translating a known non-poset convex set into the cone/topology language and checking which

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main thing to know: the paper re-proves, elementarily, that a non-empty set of total orders on a finite set is the set of linear extensions of a poset iff it is geodetically convex in the permutohedral graph. The authors credit Tits and Björner–Wachs for the original characterization, so the novelty is not in the theorem itself. What is new is the self-contained proof, the Galois-connection framing of the lattice of such sets, the height function as the number of inversion-labels inside the set, and the example showing height and diameter diverge for a 3-dimensional poset on 6 elements. Those are real refinements, modest but useful.

The paper does well what it sets out to do. The proof of the central theorem rests on Lemma 2(ii) — a walk is a geodesic iff it repeats no edge label — and that lemma is proved carefully. I checked the reflection argument and the inversion-counting induction; both hold. The necessity direction via convexity of the halfspaces S_{u≺v} is clean, and the sufficiency direction via Cov(S) is sound. The lattice-theoretic parts (Lemma 1) are mostly standard Galois-connection material, and the paper is honest about which pieces are routine. The self-citation to [18] is motivation, not load-bearing. The remark on the gaps in [9]'s alternative characterization is candid and does not affect the main proof.

Soft spots, in proportion: they are minor. Example 1's decomposition of the six-element set into four face-associated blocks is stated with "one can show" and the diameter computation is sketched rather than fully verified; a referee should ask for a few lines of detail, but it is plausibly correct and not central. Some extension steps in Lemma 1(i), particularly the case analysis for non-adjacent pairs, are compressed. Section 5.5 explicitly leaves an alternative characterization unproved; that is fine, since it is clearly marked as beyond scope. The paper also has a slightly odd appendix-style acknowledgment at the end, which should be cleaned up editorially but does not affect the mathematics.

If your field is order theory, combinatorial representation of posets, or permutohedron geometry, this is a solid, readable contribution. It deserves a serious referee: the proof is self-contained, the claims are verifiable, and the exposition is careful. I would send it to peer review rather than desk reject, mainly because the elementary proof of a known-but-scattered result has independent value and the height/diameter discussion is a genuine add-on. My only caution is to make sure the referee checks the Example 1 computation and the few compressed steps in Lemma 1(i).

Referee Report

0 major / 5 minor

Summary. The paper develops a graphical characterization of sets of linear extensions of finite posets. The central result, Theorem 3, states that for a finite set N with |N|≥2, a subset S of the set Υ(N) of all total orders on N belongs to the Galois-closed family X° (i.e., S is either empty or the set L(P) of linear extensions of a unique poset P on N) if and only if S is geodetically convex in the permutohedral graph on Υ(N). The proof is built on a Galois-connection framework (Section 4) and on Lemma 2, which characterizes geodesics as walks using no repeated edge-label. The paper also shows that the lattice of such convex sets is graded, identifies the height function as the number of edge-colors inside the set, relates the height/diameter discrepancy to poset dimension, and sketches two further cryptomorphic views (braid cones and finite topologies).

Significance. The result, if correct, provides a purely graph-theoretic cryptomorph of finite posets. Although the equivalence is essentially contained in Tits's work as reformulated by Björner and Wachs [3], the present proof is elementary and self-contained, avoiding Coxeter-group machinery. The geodesic characterization (Lemma 2(ii)) is the load-bearing structural fact and is proved carefully; the Galois-connection lattice framework gives a clean derivation of the necessity and sufficiency of Theorem 3. The auxiliary results on height, diameter, and dimension, and the explicit 6-element counterexample, are valuable. The paper is clearly written and the main proof is internally consistent. I found no circularity: [18] is motivational only, and the alternative characterization in Section 5.5 is explicitly marked as beyond the paper's scope.

minor comments (5)

[§4, Lemma 1(i)] In the sufficiency part, the extension of an enumeration of A to an enumeration of N is asserted without justification. One should add that transitivity of T rules out arrows from N\A into A, so A is an initial segment in every linear extension of G; hence the enumeration of A can simply be followed by any linear extension of the induced graph on N\A.
[§5.4, Example 1] The decomposition of S into the four face-associated subsets and the diameter computation are stated without proof. The argument that diam(S)≤8 would be more transparent if the authors noted that every pair of elements of S lies in at least one of S\B, S\C, S\D, so that one of the three relations c≺f, b≺e, a≺d is shared; since the inversions inside S are among the 9 incomparable pairs, this bounds the distance by 8.
[§5.5] The status of the rephrased [9, Theorem 9] should be clarified. As written, “it looks like the statement is indeed valid” is a conjecture, not a result of this paper. The authors should label it as a conjecture or an open problem, rather than leaving the reader uncertain about whether a theorem is being claimed.
[§5.4, Corollary 6] The proof uses the nonstandard height convention |Inv(∅)|=−1. The sentence assigning the value C(n,2)−|P\∆| to S=L(P) may appear off by one from h_Y(N×N)=C(n,2)+1 unless the shift is made explicit. Please state that this is the standardized height shifted so that the empty set has height −1, which is consistent with the convention in the corollary.
[Various] Minor typographical issues: “sandwiche principle” should be “sandwich principle”; “Appendum” should be “Addendum”. In Lemma 1(iv), the atomistic/coatomistic arguments are compressed; a sentence explaining that every closed set is the join/meet of the relevant atoms/coatoms would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 3 is derived from first principles and the proof is self-contained.

full rationale

The paper's central claim (Theorem 3) is that a non-empty set S of enumerations equals L(P) for some poset P iff S is geodetically convex in the permutohedral graph. The derivation is not circular. The key structural fact, Lemma 2(ii), is proved directly from the inversion-distance formula Lemma 2(i), which is established by an independent induction argument using adjacent transpositions. Lemma 2(ii) is then used to prove both directions of Theorem 3: necessity via convexity of the halfspace coatoms S_{u≺v}, and sufficiency via the identity S = Cov(S)^⊲ for geodetically convex S. The objects Inv(S) and Cov(S) are defined purely graph-theoretically, not in terms of posets, and the poset interpretation is obtained as a consequence, not assumed. The paper's references to prior work are not load-bearing for the main theorem: [18] is used only as motivation and for the geometric interpretation of edge labels as parallel permutohedron edges, and [9] is explicitly described as having gaps and as merely inspiring the proof technique, with its sufficiency proof 'beyond the scope of the present paper.' The discussion of [3] reformulates known results as consequences of the independently proved Theorem 3. The height-function remark is also handled internally: the paper proves that the edge-labeling can be reconstructed from the graph itself, so the label-count description is not smuggled in as an unexplained input. No fitted parameter is called a prediction, and no argument reduces to a self-citation chain. Therefore no circular step is present, and an honest non-finding with score 0 is appropriate.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters: this is a pure structural proof, not a data-fitting exercise. No invented entities: the permutohedral graph, geodetic convexity, braid cones, and finite topologies are all standard objects; the paper introduces only definitions for them. The axioms are standard background from lattice theory, polyhedral geometry, and order dimension; the paper proves the key graph-theoretic lemmas (Lemma 2) and the Galois-connection lattice properties (Lemma 1) from these ingredients. The dimension results are used only for context/counterexample, not for the central claim.

assumptions (5)

standard math Galois connections between power sets yield complete lattices and an anti-isomorphism of closed-set lattices (based on Birkhoff [2, §V.7])
Used to construct X° and Y° and their anti-isomorphism in Section 4; foundation for Lemma 1.
standard math Non-empty faces of the permutohedron Π(N) are in one-to-one correspondence with ordered partitions of N (cited from [1])
Used in Section 3.5 and Lemma 1(iii) to relate faces to posets; also for edge-label geometry.
standard math In the permutohedral graph, composing enumerations with a transposition of two elements is a graph automorphism (Section 3.7)
Used in Lemma 2(ii) and Theorem 3 Step II to 'reflect' geodesic sections across the u/v swap.
standard math A finite poset's strict part is a transitive acyclic relation; the cover (Hasse) relations generate its transitive closure (Section 3.2–3.3)
Used in Lemma 1, Theorem 4 and the sandwich principle.
domain assumption Classical results on poset dimension: dim(P) ≤ floor(n/2) and tightness (Hiraguchi [10], Dushnik–Miller [6])
Used in Section 5.4 to interpret the height/diameter gap and the dimension-3 example; not needed for the main theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graphical view on linear extensions of finite posets." pith.science (2026). https://pith.science/paper/CFDHAZRQ

@misc{pith2026251111785,
  author       = {Pith},
  title        = {Pith review of: Graphical view on linear extensions of finite posets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CFDHAZRQ}},
  note         = {Machine review of arXiv:2511.11785}
}

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.

Figures

Figures reproduced from arXiv: 2511.11785 by the authors.

**Figure 2.** A picture illustrating the proof of Theorem 3. [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

**Figure 3.** Directed Hasse diagram of the poset from Example 1. [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 2 linked inside Pith

[18]

Studen´ y

M. Studen´ y. On combinatorial descriptions of faces of the cone of supermodular functions. Research report n. 2397, Institute of Information Theory and Automation, Prague, October 2024, available onhttp://arxiv.org/abs/2410.19454

arXiv 2024
[9]

Heath, A

L. Heath, A. Nema. The poset cover problem.Open Journal of Discrete Mathematics3 (2013) 101–111

2013
[3]

Bj¨ orner, M

A. Bj¨ orner, M. L. Wachs. Permutation statistics and linear extensions of posets.Journal of Combinatorial Theory A58 (1991) 85–114. 29

1991
[1]

L. J. Billera, A. Sarangarajan. The combinatorics of permutation polytopes. InFormal Power Series and Algebraic Combinatorics, DISMACS Series in Discrete Mathematics and Theoretical Computer Science 24, AMS, Providence 1996, pp. 1–23

1996
[2]

Birkhoff.Lattice Theory(Third edition)

G. Birkhoff.Lattice Theory(Third edition). AMS Colloquium Publications 25, AMS, Prov- idence 1995

1995
[4]

S. H. Chan, I. Pak. Linear extensions of finite posets. To appear inEMS Surveys in Math- ematical Sciences(2025), available onhttp://arxiv.org/abs/2311.02743

arXiv 2025
[5]

R. P. Dilworth. A decomposition theorem for partially ordered sets.Annals of Mathematics 51(1) (1950) 161–166

1950
[6]

Dushnik, E

B. Dushnik, E. W. Miller. Partially ordered sets.American Journal of Mathematics63(3) (1941) 600–610

1941

Show all 21 references

[7]

Fujishige.Submodular Functions and Optimization, North-Holland, 1991

S. Fujishige.Submodular Functions and Optimization, North-Holland, 1991

1991
[8]

Ganter, R

B. Ganter, R. Wille.Formal Concept Analysis - Mathematical Foundations, Springer, 1999

1999
[10]

Hiraguchi

T. Hiraguchi. On the dimension of partially ordered sets.The Science Reports Kanazawa University1(2) (1951) 77-94

1951
[11]

M. Massow. Linear extension graphs and linear extension diameter. Diploma thesis, TU Berlin, 2009

2009
[12]

Morton, L

J. Morton, L. Pachter, A. Shiu, B. Sturmfels, O. Wienand. Convex rank tests and semi- graphoids.SIAM Journal of Discrete Mathematics23(3) (2009) 1117–1134

2009
[13]

N. Naatz. The graph of linear extensions revisited.SIAM Journal of Discrete Mathematics 13 (2000) 354–369

2000
[14]

I. M. Pelayo.Geodesic Convexity in Graphs. Springer Briefs in Mathematics, Springer, 2013

2013
[15]

Postnikov, V

A. Postnikov, V. Reiner, L. Williams. Faces of generalized permutohedra.Documenta Math- ematica13 (2008) 207–273

2008
[16]

Pruesse, F

G. Pruesse, F. Ruskey. Generating linear extensions fast.SIAM Journal on Computing 23(2) (1994) 373–386

1994
[17]

R. P. Stanley.Enumerative Combinatorics, volume I.Cambridge Studies in Advanced Math- ematics 49, Cambridge University Press, 1997

1997
[19]

Tits.Buildings of Spherical Type and Finite BN-pairs

J. Tits.Buildings of Spherical Type and Finite BN-pairs. Lecture Notes in Mathematics 386, Springer, 1974

1974
[20]

Wiechert

V. Wiechert. Cover graphs and order dimension. Diploma thesis, TU Berlin, 2017

2017
[21]

G. M. Ziegler.Lectures on Polytopes. Graduate Texts in Mathematics 152, Springer, 1995. 30

1995

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [18]

Studen´ y

M. Studen´ y. On combinatorial descriptions of faces of the cone of supermodular functions. Research report n. 2397, Institute of Information Theory and Automation, Prague, October 2024, available onhttp://arxiv.org/abs/2410.19454

arXiv 2024

[2] [9]

Heath, A

L. Heath, A. Nema. The poset cover problem.Open Journal of Discrete Mathematics3 (2013) 101–111

2013

[3] [3]

Bj¨ orner, M

A. Bj¨ orner, M. L. Wachs. Permutation statistics and linear extensions of posets.Journal of Combinatorial Theory A58 (1991) 85–114. 29

1991

[4] [1]

L. J. Billera, A. Sarangarajan. The combinatorics of permutation polytopes. InFormal Power Series and Algebraic Combinatorics, DISMACS Series in Discrete Mathematics and Theoretical Computer Science 24, AMS, Providence 1996, pp. 1–23

1996

[5] [2]

Birkhoff.Lattice Theory(Third edition)

G. Birkhoff.Lattice Theory(Third edition). AMS Colloquium Publications 25, AMS, Prov- idence 1995

1995

[6] [4]

S. H. Chan, I. Pak. Linear extensions of finite posets. To appear inEMS Surveys in Math- ematical Sciences(2025), available onhttp://arxiv.org/abs/2311.02743

arXiv 2025

[7] [5]

R. P. Dilworth. A decomposition theorem for partially ordered sets.Annals of Mathematics 51(1) (1950) 161–166

1950

[8] [6]

Dushnik, E

B. Dushnik, E. W. Miller. Partially ordered sets.American Journal of Mathematics63(3) (1941) 600–610

1941