{"id":"409fa952-5b1a-4caa-b54b-e351320518d7","arxiv_id":"2507.10569","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The maximum Kendall-Tau distance between two permutations allowed by an acyclic constraint graph equals the number of incomparable pairs exactly when the induced poset has dimension at most 2.","lead":"This paper studies permutation families that satisfy ordering constraints encoded by a directed graph, and asks how far apart two allowed permutations can be. It shows that the answer for one natural distance is governed by the dimension of the associated partial order, and gives constructions that attain the maximum.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.9's realizer-to-permutation mapping is reversed; as written the constructed permutations do not satisfy the graph, and Theorem 3.10 inherits this gap in its forward direction.","rationale":"The paper's main theorem, Theorem 3.10, is mathematically true: P(G) consists precisely of the total orders that reverse the reachability poset P, and two such orders flip every incomparable pair exactly when they form a 2-element realizer of P^op, equivalently when dim P≤2. The upper bound and the (1⇒2) argument are essentially sound, but the final step has a sign error: the two total orders defined by σ and ρ realize the dual poset P^op, so the displayed equality ≤_G=≤_σ∩≤_ρ is false as written and the orders must be reversed before concluding dim P≤2. The more serious gap is the (2⇒1) construction in Theorem 3.9: mapping a realizer's total orders directly to permutation words produces permutations that satisfy the opposite inequalities. The concrete 3-element example shows the literal construction fails, while the reverse-rank construction succeeds. Since the flaw is real but localized and the mathematical claim is correct with a standard repair, the reader's CONDITIONAL verdict remains appropriate; no verdict change is needed. The reader's weakest assumption correctly identified the Theorem 3.9 conversion, but I do not regard Lemma 2.7 as load-bearing for the central characterization, since any total order extending the dual poset automatically satisfies G; hence partial agreement.","tokens_in":9974,"tokens_out":17727,"duration_ms":195906,"concrete_test":"Take the 3-vertex dimension-2 poset with G={1→3,2→3} and realizer L1=(1,2,3), L2=(2,1,3). Apply the paper's literal mapping: σ1=123, σ2=213. Check edge 1→3: σ1 has σ_3=3>σ_1=1, so σ1∉P(G). Apply the corrected reverse-rank mapping: σ1'=321 and σ2'=312, which both satisfy G and are discordant exactly on (1,2), giving dK=1=|Incomp(P)|. This confirms the concern and isolates the required repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central characterization is true, but the proof as written contains a direction error that breaks the construction. In Theorem 3.9, a realizer (≤1,≤2) of P is mapped to permutation words σ1=v1v2...vn and σ2=u1u2...un, where the word lists the realizer order from smallest to largest. For an edge i→j in G, we have i≤_P j, hence i≤_1 j, so i appears before j in the word and σ_i<σ_j, which violates the required inequality σ_i>σ_j. Thus the permutations constructed in Theorem 3.9 do not lie in P(G). The same reversal is needed in the final step of Theorem 3.10: the total orders defined by σ and ρ realize P^op, not P, so the written equality ≤_G=≤_σ∩≤_ρ is false. Both directions are restorable by using reverse-rank mappings, but the manuscript as written does not prove the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10138,"tokens_out":22652,"duration_ms":206453,"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":[{"comment":"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).","section":"Theorems 3.9 and 3.10"},{"comment":"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.","section":"Example 3.13"},{"comment":"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.","section":"Corollary 3.17"},{"comment":"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.","section":"Theorem 3.16"},{"comment":"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)|.","section":"Theorem 2.8"}],"minor_comments":[{"comment":"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).","section":"Theorem 3.9"},{"comment":"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.","section":"Definition 2.10"},{"comment":"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'.","section":"Theorem 3.5"},{"comment":"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.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The central idea is good and the main characterization appears to be correct in substance, but the current manuscript contains a load-bearing direction error in the proof of Theorems 3.9 and 3.10, plus a false example and an incorrect corollary. These are fixable, but the paper needs careful revision and re-verification of all stated formulas before it can be considered for publication. The paper also has several unpolished proofs that would benefit from a thorough rewriting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":10661,"tokens_out":4094,"would_cite":true,"duration_ms":47644,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","06A07","05E10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["restriction graph","Kendall-Tau metric","poset dimension","permutation metrics","descent sets","Hessenberg varieties","realizer","reachability poset"],"falsifier":"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.","tokens_in":9761,"feed_emoji":"🔀","tokens_out":5779,"duration_ms":57662,"temperature":0.7,"pith_summary":"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.","feed_headline":"Kendall-Tau distance peaks exactly at poset dimension 2","feed_subtitle":"Acyclic restriction graphs: two permutations reverse every incomparable pair precisely when their order is 2-dimensional.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the descent-set metric results that the restriction-graph framework extends and simplifies.","marker":"[2]"},{"why":"Previous work on maximum Kendall-Tau distance for peak-set families, generalized here to arbitrary restriction graphs.","marker":"[3]"},{"why":"Introduces poset dimension and the realizer construction that the main characterization relies on.","marker":"[4]"},{"why":"Introduces the Kendall rank correlation metric whose number of discordant pairs is the Kendall-Tau distance.","marker":"[5]"},{"why":"Provides dimension-theory background and the standard dimension-3 example used to illustrate strict deficiency.","marker":"[10]"}],"fun_headline_variants":["Kendall-Tau cap reached exactly for dimension-2 posets","Poset dimension 2: the exact threshold for Kendall-Tau diameter","When does Kendall-Tau reverse all incomparables? Dimension ≤2","Kendall-Tau distance peaks iff poset dimension at most 2","Maximum Kendall-Tau distance? Only if dimension ≤2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Kendall-Tau cap reached exactly for dimension-2 posets","Poset dimension 2: the exact threshold for Kendall-Tau diameter","When does Kendall-Tau reverse all incomparables? Dimension ≤2","Kendall-Tau distance peaks iff poset dimension at most 2","Maximum Kendall-Tau distance? Only if dimension ≤2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000443,"raw_usage":{"total_tokens":2227,"prompt_tokens":914,"completion_tokens":1313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":530,"completion_tokens_details":{"reasoning_tokens":1219}},"tokens_in":530,"tokens_out":1313,"duration_ms":11803,"temperature":1.0,"reasoning_tokens":1219,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:08:35.187139+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Undergrad","cited_arxiv_id":null,"evidence_quote":"Supplies the descent-set metric results that the restriction-graph framework extends and simplifies."},{"cited_title":"5, 889–904","cited_arxiv_id":null,"evidence_quote":"Previous work on maximum Kendall-Tau distance for peak-set families, generalized here to arbitrary restriction graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces poset dimension and the realizer construction that the main characterization relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Kendall rank correlation metric whose number of discordant pairs is the Kendall-Tau distance."},{"cited_title":"Trotter,Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992","cited_arxiv_id":null,"evidence_quote":"Provides dimension-theory background and the standard dimension-3 example used to illustrate strict deficiency."}],"review_version":1}