Timeline for Maximal pairwise distance between $k$ permutations

7 events

when toggle format	what		by	license	comment
Sep 17, 2016 at 11:55	comment	added	Bogdan Chornomaz		Thanks, your example has led me to the proof of your first conjecture, which I put below. I think the proof can also be strengthened to show that you can have $c_k$ instead of $O(n)$, for large $n$, and possibly even to show that your second conjecture also holds.
Sep 17, 2016 at 6:26	history	edited	Aaron Meyerowitz	CC BY-SA 3.0	deleted 77 characters in body
Sep 16, 2016 at 22:35	history	edited	Aaron Meyerowitz	CC BY-SA 3.0	added 16 characters in body
Sep 16, 2016 at 22:34	comment	added	Aaron Meyerowitz		Yes for $k=4$ (so also $k=3$) the pairwise distances can all be exactly $\frac23$ in case $n$ is a multiple of $6.$ I revised the answer to make that clearer. I was going for a quick intro before.
Sep 16, 2016 at 22:07	history	edited	Aaron Meyerowitz	CC BY-SA 3.0	added 588 characters in body
Sep 16, 2016 at 14:16	comment	added	Bogdan Chornomaz		Sure, it is true that the distance $\frac{1}{2}$ can be achieved by random permutations, as well as that the upper bound $\frac{j}{2 j - 1}$ approaches $\frac{1}{2}$ as $k$ grows. On the other hand, at least for $k=3$, one can do better. For example, take three permutations: identical, one that reverses first $\alpha n$, and one that reverses last $\alpha n$ elements. Then optimal $\alpha$ would be $\frac{4+\sqrt{2}}{7}$, giving the pairwise distance about $0.598$, which is substantially larger than $\frac{1}{2}$.
Sep 16, 2016 at 9:17	history	answered	Aaron Meyerowitz	CC BY-SA 3.0