|
|
来自REU12
47. (Neighbor transpositions) (a) Show that the neighbor transpositions $(12),(23), \ldots,(n-1\ n)$ generate the symmetric group $S_{n}$. (b) Show that $O\left(n^{2}\right)$ neighbor transpositions suffice to generate $S_{n}$ and $\Omega\left(n^{2}\right)$ are necessary to generate $S_{n}$. That is, there exist positive constants $c_{1}, c_{2}$ such that (b1) each element of $S_{n}$ can be expressed as the composition of at most $c_{1} n^{2}$ neighbor transpositions; and (b2) there exists a permutation which cannot be expressed as the composition of fewer than $c_{2} n^{2}$ neighbor transpositions. - The "word length" of a permutation with respect to a set of generators is the smallest length of a word in the generators that expresses the given permutation. So what you were asked to show was that the maximum word length with respect to neighbor transpositions is $\Theta\left(n^{2}\right)$, i.e., it is between $c_{2} n^{2}$ and $c_{1} n^{2}$ for some positive constants $c_{1}$ and $c_{2}$. |
|
