Timeline for Maximal pairwise distance between $k$ permutations
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2016 at 23:24 | comment | added | benblumsmith | I posted the followup question here: mathoverflow.net/questions/251351/… | |
| Oct 3, 2016 at 22:39 | comment | added | benblumsmith | Regarding Hamming distance between sets, the group model is the Coxeter group generated by the reflections in the coordinate hyperplanes $x_i=0$. I would want an optimal distribution of $k$ points on the $n-1$-sphere and then to study how this distribution performs in terms of Hamming distance. If $n$ is large relative to $k$ (in fact as soon as $n\geq k$) one can achieve the minimum distance of $1/2$ (normalized by $\pi$) in the Euclidean case by taking $k$ orthonormal vectors (not optimal but not bad); then the corresponding Hamming distances will also be close to $1/2$ (normalized by $n$). | |
| Oct 3, 2016 at 22:14 | comment | added | benblumsmith | I would be surprised if the difference between Euclidean and Cayley-graph-metric distance were not bounded by a reasonably small constant fraction of each, however I'm not sure where to start to look for this result. I will post a followup question and link to it. | |
| Sep 9, 2016 at 13:57 | comment | added | Bogdan Chornomaz | On the other hand, I was kind of expecting that this problem would already be taken to pieces at some handbook. Because the question looks very natural to me. | |
| Sep 9, 2016 at 13:52 | comment | added | Bogdan Chornomaz | In case of sets, it seems that optimal asymptotic (over $n$) distance between $k$ sets is $\lceil \frac{k}{2} \rceil \lfloor \frac{k}{2} \rfloor/\binom{k}{2}$. I wonder to what extent does it comply with your group-action approach? | |
| Sep 9, 2016 at 13:44 | comment | added | Bogdan Chornomaz | Thanks for the answer, it clearly makes sense. On the other hand, correspondence between distance on the sphere and distance in group actions may not be that straightforward. For example, let us consider simpler example - Hamming distance between sets. For three sets, $A$, $B$ and $C$, minimal pairwise distance, normalized by $n$, would be $2/3$, for example if $|A\cap B| = |A\cap C| = |B\cap C| = 1/3$ and $|A\cap B \cap C = 0|$. However now we may add an empty set $I$, with distance between $I$ and $A$, $B$ or $C$ being also $2/3$. This clearly cannot be achieved in Euclidean metric. | |
| Sep 8, 2016 at 1:44 | history | edited | benblumsmith | CC BY-SA 3.0 |
Added a concrete example
|
| Sep 2, 2016 at 14:28 | history | edited | benblumsmith | CC BY-SA 3.0 |
added 1168 characters in body
|
| Sep 2, 2016 at 13:35 | history | edited | benblumsmith | CC BY-SA 3.0 |
Improved formatting by putting the upshot at the beginning, and edited for clarity.
|
| Sep 2, 2016 at 13:25 | history | answered | benblumsmith | CC BY-SA 3.0 |