{"id":"06beff8d-c02f-4640-86b2-cf6bb72c8693","arxiv_id":"2511.11785","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A non-empty set of total orders is the set of linear extensions of some poset iff it is a geodesically convex set in the permutohedral graph; the paper gives an elementary proof and studies the graded lattice of such sets.","lead":"This paper gives an elementary proof that the linear extensions of a finite poset are exactly the geodesically convex subsets of the permutohedral graph, a characterization previously known from Coxeter group theory. It also shows the lattice of such convex sets is graded, with height equal to the number of incomparable pairs, and that this height need not equal the graph diameter — a fact tied to poset dimension.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified — the main theorem is supported by a sound proof; Lemma 2(ii) holds.","rationale":"The reader accepted with moderate confidence. My pass found the proof correct. Lemma 2(ii) is indeed the key step, and I traced its two directions; both are valid. I also re-derived the main theorem's sufficiency/necessity structure and found no hidden assumptions. The paper honestly attributes priority to Tits and Björner–Wachs, so novelty is appropriately scoped. No reason to alter the verdict.","tokens_in":27661,"tokens_out":13863,"duration_ms":129288,"concrete_test":"Brute-force verification: for n=4 and n=5, enumerate all permutations and all shortest walks between every pair (e.g., via BFS in the permutohedral graph) and assert that no geodesic contains an edge-label twice; equivalently, assert that the label set of every geodesic equals the inversion set of its endpoints. This directly tests Lemma 2(ii), the load-bearing lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After independent review, I find no load-bearing concern that would overturn the central claim. The theorem rests on Lemma 2(ii): a walk in the permutohedral graph is a geodesic iff it repeats no edge-label. I checked the proof in detail. Necessity uses the automorphism τ_{uv}; the section between consecutive occurrences of a repeated label lies entirely in one halfspace S_{v≺u} because no {u,v}-labeled edge occurs there, and τ_{uv} maps it to a strictly shorter connection. Sufficiency follows because each inversion must be swapped at least once and a single swap of a non-inversion would force a second swap to restore the endpoint order. The inversion-distance formula Lemma 2(i) is also correct by the usual adjacent-transposition induction. Theorem 3 then follows: necessity from convexity of halfspaces, sufficiency from the Cov(S) closure argument. The height/diameter example is auxiliary and plausibly correct; the Section 5.5 remark on [9] is not needed for the main theorem. The proof is self-contained and internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":27864,"tokens_out":28570,"duration_ms":223205,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§4, Lemma 1(i)"},{"comment":"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.","section":"§5.4, Example 1"},{"comment":"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.","section":"§5.5"},{"comment":"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.","section":"§5.4, Corollary 6"},{"comment":"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.","section":"Various"}],"recommendation":"minor_revision","confidential_remarks":"This is a solid paper. The main theorem is known in various forms from Tits and Björner–Wachs, but the elementary proof and the lattice-theoretic packaging make it a worthwhile contribution. The load-bearing Lemma 2(ii) is carefully proved, and I found no fatal gap in Theorem 3. The issues I identified are local clarity gaps (Lemma 1(i) extension step, Example 1 details, the nonstandard height convention, and the status of the Section 5.5 remark). A routine revision should suffice; I do not think further external review is needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSoft 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.\n\nIf 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).","headline":"A clean, honestly-scoped re-proof of a known characterization (geodesic convexity = linear extensions) with a few useful refinements; worth refereeing despite modest novelty.","tokens_in":807,"tokens_out":760,"would_cite":true,"duration_ms":17531,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["06A07","06A15","62R01"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["finite poset","linear extension","geodetically convex set","permutohedral graph","graded lattice","poset dimension","cryptomorphism","Galois connection"],"falsifier":"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.","tokens_in":27539,"feed_emoji":"🧩","tokens_out":9973,"duration_ms":79431,"temperature":0.7,"pith_summary":"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.","feed_headline":"Geodesic convexity identifies linear-extension sets of posets","feed_subtitle":"A set of total orders is from a poset exactly when it is geodetically convex in the permutohedral graph; the paper proves the equivalence.","key_machinery":"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","core_discovery":"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","pith_inferences":["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"],"forward_implications":["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."],"fun_headline_variants":["Posets from total orders via geodesic convexity","Geodesic convexity pins down linear-extension sets","Permutohedral convex sets equal poset extensions","Graphical criterion: geodetic convexity for posets","Total-order sets convex iff they are linear extensions"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Posets from total orders via geodesic convexity","Geodesic convexity pins down linear-extension sets","Permutohedral convex sets equal poset extensions","Graphical criterion: geodetic convexity for posets","Total-order sets convex iff they are linear extensions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1237,"prompt_tokens":867,"completion_tokens":370,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":307}},"tokens_in":611,"tokens_out":370,"duration_ms":3541,"temperature":1.0,"reasoning_tokens":307,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T06:47:07.648017+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}