Metrics on Permutation Families Defined by a Restriction Graph
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909689235636224 |
|---|---|
| author | Tymoshenko, Danylo Nagel, Leonhard |
| author_facet | Tymoshenko, Danylo Nagel, Leonhard |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10569 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Metrics on Permutation Families Defined by a Restriction Graph Tymoshenko, Danylo Nagel, Leonhard Discrete Mathematics Combinatorics 06A07, 05A05, 05C12, 05C85, 68R05 G.2.1; G.2.2; F.2.2 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. |
| title | Metrics on Permutation Families Defined by a Restriction Graph |
| topic | Discrete Mathematics Combinatorics 06A07, 05A05, 05C12, 05C85, 68R05 G.2.1; G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2507.10569 |