Links and the Diaconis-Graham Inequality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929327560458240 |
|---|---|
| author | Cornwell, Christopher McNew, Nathan |
| author_facet | Cornwell, Christopher McNew, Nathan |
| contents | In 1977 Diaconis and Graham proved two inequalities relating different measures of disarray in permutations, and asked for a characterization of those permutations for which equality holds in one of these inequalities. Such a characterization was first given in 2013. Recently, another characterization was given by Woo, using a topological link in $\mathbb R^3$ that can be associated to the cycle diagram of a permutation. We show that Woo's characterization extends much further: for any permutation, the discrepancy in Diaconis and Graham's inequality is directly related to the Euler characteristic of the associated link. This connection provides a new proof of the original result of Diaconis and Graham. We also characterize permutations with a fixed discrepancy in terms of their associated links and find that the stabilized-interval-free permutations are precisely those whose associated links are nonsplit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16755 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Links and the Diaconis-Graham Inequality Cornwell, Christopher McNew, Nathan Combinatorics Geometric Topology 05A05, 57K10, 05A15 In 1977 Diaconis and Graham proved two inequalities relating different measures of disarray in permutations, and asked for a characterization of those permutations for which equality holds in one of these inequalities. Such a characterization was first given in 2013. Recently, another characterization was given by Woo, using a topological link in $\mathbb R^3$ that can be associated to the cycle diagram of a permutation. We show that Woo's characterization extends much further: for any permutation, the discrepancy in Diaconis and Graham's inequality is directly related to the Euler characteristic of the associated link. This connection provides a new proof of the original result of Diaconis and Graham. We also characterize permutations with a fixed discrepancy in terms of their associated links and find that the stabilized-interval-free permutations are precisely those whose associated links are nonsplit. |
| title | Links and the Diaconis-Graham Inequality |
| topic | Combinatorics Geometric Topology 05A05, 57K10, 05A15 |
| url | https://arxiv.org/abs/2404.16755 |