Skip to main content
MathOverflow

Return to Answer

added 133 characters in body
Source Link
Max Alekseyev
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

ADDED. A smaller set example for the same $\pi = [2, 3, 4, 1]$: $$\{ [1, 2, 3, 4], [3, 4, 1, 2], [4, 1, 2, 3] \}.$$

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

ADDED. A smaller set example for the same $\pi = [2, 3, 4, 1]$: $$\{ [1, 2, 3, 4], [3, 4, 1, 2], [4, 1, 2, 3] \}.$$

added 117 characters in body
Source Link
Max Alekseyev
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when multiplied by $\pi$.

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

Source Link
Max Alekseyev
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by $$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$ $$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$ and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when multiplied by $\pi$.