New answers tagged permutations
3
Here is a quick argument showing that $P(\mathbf{md}(\pi)>m)\le Ce^{-cm}$ though I'll not try to make the bounds sharp. Let us consider $n$ independent random variables $X_k$ uniformly distributed on $[0,1]$. The rearrangement $\pi$ will be determined from that model as $\pi(k)=\#\{i\in[n]:X_i\le X_k\}$. Clearly, we have all orderings of $X$ equally ...
7
It seems that this is a lower bound of $\Omega(n^2)$.
Take an $n$ and an $a=\Theta( n) $ coprime with $n$ (with $a<n/2$). Then the permutations $\sigma=(12\dots n) $ and $\tau=(1, a+1) $ generate $S_n$.
On the other hand, all residues modulo $n$ form a cycle where the neighbors differ by $a$. The only way to change this cyclic order is to apply $\tau$. ...
Top 50 recent answers are included
