Metrics on Permutation Families Defined by a Restriction Graph

Danylo Tymoshenko; Leonhard Nagel

REVIEW 5 major objections 4 minor 1 cited by

Metrics on Permutation Families Defined by a Restriction Graph

T0 review · 5 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read For a permutation family cut out by an acyclic restriction graph, the Kendall-Tau diameter attains its upper bound, the number of incomparable pairs, exactly when the graph's reachability poset has dimension at most 2.

desk verdict The Kendall-Tau/poset-dimension characterization is the right result, but the proof as written reverses the realizer-to-permutation mapping everywhere, and the applications section needs cleanup before the paper is citable. read the letter →

arxiv 2507.10569 v1 pith:SQ7GHEZ2 submitted 2025-07-08 cs.DM math.CO

Danylo Tymoshenko , Leonhard Nagel This is my paper · ORCID

classification cs.DMmath.CO MSC 05A0506A0705E10

keywords restrictiongraphKendall-TaumetricposetdimensionpermutationmetricsdescentsetsHessenbergvarietiesrealizerreachability

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

The paper studies permutation families defined by an oriented "restriction graph": an edge $u \to v$ forces any valid permutation $\sigma$ to place a larger value at position $u$ than at position $v$. For these families it asks how far apart two valid permutations can be. Under the $\ell_\infty$ metric it proves the exact diameter is $\max_i (n - |R(i)| - |R^{-1}(i)| - 1)$ and gives an algorithm that constructs a pair attaining it. Under the Kendall-Tau metric it characterizes when the diameter reaches the combinatorial upper bound $|\operatorname{Incomp}(P)|$: this happens exactly when the reachability poset $P$ of the graph has dimension at most 2. The paper then derives explicit formulas for descent sets and $h$-inversion sets, connecting metric geometry of permutation families to poset dimension theory.

What carries the argument

The load-bearing object is the reachability poset $P = ([n], \leq_G)$ defined by $a \leq_G b$ iff $a = b$ or there is a directed path from $a$ to $b$ in $G$. Acyclicity of restriction graphs makes this a genuine partial order, and the valid permutations $P(G)$ are identified with the (reversed) linear extensions of $P$. The Kendall-Tau upper bound counts exactly the incomparable pairs of $P$, and the argument turns on when two linear extensions can disagree on every incomparable pair while agreeing on every comparable pair. The dimension of a poset is the smallest number of total orders whose intersection is the poset, and the witnessing permutations in the extremal case are precisely a size-2 realizer. This identification carries the entire characterization.

What would settle it

Enumerate all valid permutations for a small restriction graph whose reachability poset is the standard dimension-3 example on six elements (edges $1\to4$, $2\to5$, $3\to6$, $1\to5$, $2\to6$, $3\to4$) and compute the Kendall-Tau diameter; finding two permutations that disagree on all six incomparable pairs would refute the characterization, since the theorem predicts the diameter is strictly less than 6.

Watch

Extended reading notes

Core claim

The central discovery is an if-and-only-if characterization of the Kendall-Tau diameter of a restriction-graph family. If $G$ is an acyclic restriction graph and $P = ([n], \leq_G)$ is the poset obtained by taking reachability as order, then there exist permutations $\sigma, \rho \in P(G)$ with $d_K(\sigma,\rho) = |\operatorname{Incomp}(P)|$ if and only if $\dim P \leq 2$. When the bound is attained and $P$ is not a total order, the two witnessing permutations are linear extensions whose intersection is exactly the poset order, i.e. they form a realizer of size 2. For posets of dimension at least 3 the diameter is strictly smaller than $|\operatorname{Incomp}(P)|$. For the $\ell_\infty$ metric the paper proves an exact diameter formula, $\max_i\{n - |R(i)| - |R^{-1}(i)| - 1\}$, and shows the bound is always attained by an explicit construction.

Load-bearing premise

The argument assumes that every permutation consistent with the reachability order of the restriction graph is actually realizable by the graph, so that $P(G)$ is completely captured by the poset of reachability inequalities.

Editorial extensions

If this is right

If $\dim P \leq 2$, the Kendall-Tau diameter of $P(G)$ is exactly the number of incomparable pairs, and the extremal pair can be read directly from a realizer.
If $\dim P \geq 3$, the diameter is strictly deficient: no two valid permutations can reverse every incomparable pair.
For descent-set families and $h$-inversion sets, the paper gives explicit diameter formulas, turning a metric computation into a small order-theoretic calculation.
For the $\ell_\infty$ metric, the diameter formula holds for every 2-admissible restriction graph, and the paper's algorithm constructs an optimal pair.
In the dimension-2 case the extremal pairs realize the poset, so metric witnesses and minimal realizers coincide.

Reading between the lines

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

Computing the Kendall-Tau diameter of a restriction-graph family is at least as hard as computing poset dimension, which is generally hard, so the characterization points to computational hardness of the diameter in the unrestricted setting.
For posets of dimension 3 or more, the ratio between the true diameter and $|\operatorname{Incomp}(P)|$ becomes a new metric invariant of the poset; tracking this ratio across families could quantify how far a poset is from being Kendall-realizable.
The same question could be asked for other permutation metrics: Spearman footrule or Hamming distance diameters might correspond to different order-theoretic invariants, such as width or cover relations.
A testable extension: for dimension-2 posets, the set of extremal pairs should be exactly the set of size-2 realizers, so counting realizers could predict how many permutation pairs achieve the maximum distance.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

First thing to know: the main Kendall-Tau result — diameter equals |Incomp(P)| iff the associated poset has dimension at most 2 — is true and is the result worth remembering. The stress-test note is accurate, though: Theorem 3.9 builds permutations from a realizer by listing each total order from smallest to largest, and that ordering actually violates the restriction graph. If u→v is an edge, then u ≤_P v, so u appears earlier in both words, and the entries at positions u and v are not guaranteed to satisfy σ_u > σ_v. The fix is the reverse-rank construction, σ_u = n − rank(u) + 1. The same orientation slip appears at the end of Theorem 3.10: the two linear extensions obtained from σ and ρ realize P^op, not P. Since dimension is invariant under reversal, the characterization survives, but the written proof needs correction.

What is genuinely good: the ℓ∞ diameter formula for arbitrary acyclic restriction graphs, with an explicit algorithm achieving the bound, is new and cleanly unifies earlier descent-set and peak-set special cases. The reachability-poset framing is natural and useful. The upper-bound proof for the Kendall-Tau metric is solid, and the iff structure of Theorem 3.10 is the right way to think about when the combinatorial bound is attainable.

The soft spots are real but mostly peripheral. The applications section is unpolished: Theorem 3.16 is stated without proof, Corollary 3.17's formula appears to fail on small examples (D = {2} in S3 gives the wrong answer), and Example 3.13 mis-counts the incomparable pairs — it omits (2,4), (3,5), and (1,6). These are not load-bearing, but they are errors in the text. Lemma 2.7 and Theorem 2.8 are also more informal than the rest of the paper, though the construction there is plausibly correct.

Who should read this: anyone working on permutation codes, metrics on constrained permutations, or connections between poset dimension and metric geometry. It deserves a serious referee. Send it to review, but tell the authors to fix Theorem 3.9 before the proof is trusted, and to repair the examples and formulas in the applications section.

Referee Report

5 major / 4 minor

Summary. The paper introduces restriction graphs G on [n], where each directed edge u→v requires σ_u > σ_v for every admissible permutation σ∈P(G). It studies the diameter of P(G) under the ℓ∞ metric and the Kendall-Tau metric. For ℓ∞, it proves an upper bound in terms of reachability sets and gives an algorithm achieving it. For Kendall-Tau, it characterizes when the diameter equals the number of incomparable pairs of the reachability poset P: it claims this occurs exactly when dim(P) ≤ 2, with the extremal permutations forming a realizer. The paper further applies these results to descent sets and h-inversion sets.

Significance. If the main characterization is established, this is a clean and publishable result: it links the metric diameter of a constrained permutation family to poset dimension, and the ℓ∞ diameter formula is explicit and algorithmic. The upper bound Theorem 3.3 is correct, and the dimension-2 construction is a natural realizer argument. The paper is self-contained and does not rely on fitted parameters. However, the proof of the central characterization currently contains a direction error in the realizer-to-permutation construction, and several applications contain false or unproved statements. These issues are repairable, but they must be fixed before the paper can be accepted.

major comments (5)

[Theorems 3.9 and 3.10] The realizer-to-permutation mapping in Theorem 3.9 is reversed. Writing a linear extension L = (x1, x2, ..., xn) as the permutation word x1x2...xn assigns value xi to position i; the edge constraint requires the value at position x_i to be larger than the value at position x_j whenever x_i ≤_P x_j, which is opposite to the word order. For the single-edge graph 1→2, the linear extension L1 = (1,2,3) yields σ1 = 1 2 3, which violates the edge because σ_1 = 1 < σ_2 = 2. The correct construction is σ_L(x) = n - rank_L(x) + 1, i.e., the permutation whose decreasing-value order is L. This correction is needed for the (2⇒1) direction of Theorem 3.10. In the (1⇒2) direction, the orders defined by i ≤_σ j iff σ_i < σ_j have intersection P^op, not P; the displayed equality ≤_G = ≤_σ ∩ ≤_ρ is false as written. Replacing them by the decreasing-value orders fixes the proof and still yields dim(P) ≤ 2, because dim(P) = dim(P^op).
[Example 3.13] The incomparable set of the poset displayed in Example 3.13 is miscounted. For the graph with edges 1→4, 2→5, 3→6, 1→5, 2→6, 3→4, the pairs (1,6), (2,4), and (3,5) are also incomparable in addition to the six listed pairs; hence |Incomp(P)| = 9, not 6. The assertion that no two permutations can disagree on all six listed incomparable pairs is therefore unsupported. The example should be corrected, for instance by using the standard example S_3 with edges a_i→b_j for i≠j, or by recomputing the incomparable pairs.
[Corollary 3.17] Corollary 3.17 is incorrect as stated. For n = 3 and descent set D = {2}, the reachability poset has exactly one incomparable pair, (1,3), so the true maximum Kendall-Tau distance is 1. Substituting the natural turning points a1 = 1, a2 = 3 into the displayed formula gives (3-1)(3-3+1) = 2, which is already disproved by this example. The formula and the definition of turning points need to be corrected or the corollary removed.
[Theorem 3.16] Theorem 3.16 is stated without proof. It asserts that any 2-admissible D_h(S;n) corresponds to a dimension-2 poset and that the maximum Kendall-Tau distance equals ℓ(x) - ℓ(ω). No argument is supplied for either claim. Since this theorem is part of the paper's claimed applications, a proof must be provided or the statement should be explicitly labeled as a conjecture.
[Theorem 2.8] The proof of Theorem 2.8 does not verify that edges between the three induced subgraphs (R(k), R^{-1}(k), and the remaining vertices) respect the assigned value intervals. The construction is valid, but the proof should explicitly argue, for example, that there are no edges from R(k) to the remaining block, no edges from the remaining block to R^{-1}(k), and that the remaining cross edges are satisfied by the interval ordering. In addition, the displayed intervals in the last paragraph use |R(i)| and |R^{-1}(i)| where they should use |R(k)| and |R^{-1}(k)|.

minor comments (4)

[Theorem 3.9] In the sentence 'i⇝j =⇒ u_j ≤_1 u_i', the notation mixes u and v; it should be 'i⇝j =⇒ i ≤_1 j' (before the reversal is fixed).
[Definition 2.10] The definition of a 'division' of a descent set is unclear as written; the phrase listing sums of ℓ_i is hard to parse. Please rewrite it in terms of maximal consecutive runs with a clear indexing.
[Theorem 3.5] In the proof of transitivity, Case (3) says 'a=c and a≠b, b≠c', which is contradictory because a=c; this case should simply say 'a=c'.
[Introduction] Reference [1] (Peak sets of classical Coxeter groups) is not cited in the text; the peak-set metrics are attributed to [3]. Please add the missing citation or remove the unused reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's derivations are self-contained; the realizer-to-permutation direction error in Theorem 3.9 is a correctness gap, not a circular reduction.

full rationale

The paper contains no fitted parameters, no empirical data, and no load-bearing self-citations; its main results are proved from the definitions of restriction graphs, reachability, posets, and the two metrics. The Kendall-Tau characterization reduces to the definition of poset dimension, but that reduction is the intended theorem rather than a circular step: it connects an independent poset-theoretic invariant (dimension) to the metric diameter. The ℓ∞ result consists of a reachability-based upper bound and an explicit algorithmic construction attaining it. References to Dushnik-Miller, Trotter, Diaz-Lopez et al., and other classical sources support definitions, examples, and prior results; none of these citations is doing the work of the present proof, and none is a self-citation. The only notable issue is a direction error in Theorem 3.9: mapping realizer orders directly to permutation words lists i before j when i ≤_1 j, which would give σ_i < σ_j for an edge i → j, whereas Definition 1.1 requires σ_i > σ_j. A reverse-rank or complementary mapping is required for the constructed permutations to lie in P(G). This is a proof gap in the manuscript as written, not a circular step, so it does not change the circularity score.

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

No free parameters, data fits, or invented entities. All inputs are mathematical definitions and standard poset-theoretic facts.

assumptions (3)

standard math Definition of poset dimension: the dimension of P is the minimum number of linear extensions whose intersection is P (Dushnik-Miller).
Used in Theorems 3.9 and 3.10 to connect realizers to permutations.
standard math Every finite acyclic directed graph has a source vertex.
Used by the construction algorithm in Lemma 2.7 and Theorem 2.8.
standard math The standard example S_3 (three plus-elements and three minus-elements) has dimension 3.
Cited to Trotter [10] and used in Example 3.13; note the example's label set is a relabeling of S_3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Metrics on Permutation Families Defined by a Restriction Graph." pith.science (2026). https://pith.science/paper/SQ7GHEZ2

@misc{pith2026250710569,
  author       = {Pith},
  title        = {Pith review of: Metrics on Permutation Families Defined by a Restriction Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQ7GHEZ2}},
  note         = {Machine review of arXiv:2507.10569}
}

abstract

Understanding the metric structure of permutation families is fundamental to combinatorics and has applications in social choice theory, bioinformatics, and coding theory. We study permutation families defined by restriction graphs--oriented graphs that constrain the relative order of elements in valid permutations. For any restriction graph $G$, we determine the maximum distance achievable by two permutations under the $\ell_\infty$-metric and provide an explicit algorithm that constructs optimal permutation pairs. Our main contribution characterizes when the Kendall-Tau metric achieves its combinatorial upper bound: this occurs if and only if the poset induced by $G$ has dimension at most 2. When this condition holds, the extremal permutations form a minimal realizer of the poset, revealing a deep connection between metric geometry and poset dimension theory. We apply these results to classical permutation statistics including descent sets and Hessenberg varieties, obtaining explicit formulas and efficient algorithms for computing metric diameters.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Black hole mimickers as relativistic stars calculated from the Tolman-Oppenheimer-Volkoff equations
gr-qc 2025-04 conditional novelty 4.0 of 10

A horizonless gravastar with a mock horizon emerges from the Tolman-Oppenheimer-Volkoff equations if matter at high pressure transitions to a negative energy-density state.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages · cited by 1 Pith paper

[1]

Harris, Erik Insko, and Darleen Perez-Lavin,Peak sets of classical Coxeter groups, Involve 10 (2017), no

Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin,Peak sets of classical Coxeter groups, Involve 10 (2017), no. 2, 263–290

work page 2017
[2]

Undergrad

Alexander Diaz-Lopez, Kathryn Haymaker, Colin McGarry, and Dylan McMahon,Metrics on permutations with the same descent set, PUMP J. Undergrad. Res. 8 (2024), 57–69

work page 2024
[3]

5, 889–904

Alexander Diaz-Lopez, Kathryn Haymaker, Kathryn Keough, Jeongbin Park, and Edward White,Metrics on permutations with the same peak set, Involve 17 (2024), no. 5, 889–904

work page 2024
[4]

Ben Dushnik and E. W. Miller,Partially ordered sets, Amer. J. Math. 63 (1941), no. 3, 600–610

work page 1941
[5]

M. G. Kendall,A new measure of rank correlation, Biometrika 30 (1938), no. 1–2, 81–93

work page 1938
[6]

M. G. Kendall,The treatment of ties in ranking problems, Biometrika 33 (1945), no. 3, 239– 251

work page 1945
[7]

Knuth,The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley Professional, Reading, MA, 1998

Donald E. Knuth,The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley Professional, Reading, MA, 1998

work page 1998
[8]

MacMahon,The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer

Percy A. MacMahon,The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), no. 3, 281–322

work page 1913

Show all 10 references

[9]

Stanley,Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol

Richard P. Stanley,Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012

2012
[10]

Trotter,Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992

William T. Trotter,Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. Department of Mathematics and Statistics, W ashington University in St. Louis Email address:d....

1992

Pith tools

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

[1] [1]

Harris, Erik Insko, and Darleen Perez-Lavin,Peak sets of classical Coxeter groups, Involve 10 (2017), no

Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin,Peak sets of classical Coxeter groups, Involve 10 (2017), no. 2, 263–290

work page 2017

[2] [2]

Undergrad

Alexander Diaz-Lopez, Kathryn Haymaker, Colin McGarry, and Dylan McMahon,Metrics on permutations with the same descent set, PUMP J. Undergrad. Res. 8 (2024), 57–69

work page 2024

[3] [3]

5, 889–904

Alexander Diaz-Lopez, Kathryn Haymaker, Kathryn Keough, Jeongbin Park, and Edward White,Metrics on permutations with the same peak set, Involve 17 (2024), no. 5, 889–904

work page 2024

[4] [4]

Ben Dushnik and E. W. Miller,Partially ordered sets, Amer. J. Math. 63 (1941), no. 3, 600–610

work page 1941

[5] [5]

M. G. Kendall,A new measure of rank correlation, Biometrika 30 (1938), no. 1–2, 81–93

work page 1938

[6] [6]

M. G. Kendall,The treatment of ties in ranking problems, Biometrika 33 (1945), no. 3, 239– 251

work page 1945

[7] [7]

Knuth,The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley Professional, Reading, MA, 1998

Donald E. Knuth,The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley Professional, Reading, MA, 1998

work page 1998

[8] [8]

MacMahon,The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer

Percy A. MacMahon,The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), no. 3, 281–322

work page 1913