Return to Answer

added 709 characters in body

Source Link

edited Dec 22, 2021 at 15:46

4.6k
32
45

An easy upper bound for $S^*_N$ is $\lceil N(N-1)/4 \rceil$, the integer ceiling of half the length of a legal sequence taking $[1,\ldots,N]$ to $[N,\ldots, 1]$. If some transposition $(i, i+1)$ occurred more often in the sequence, there would be two $(i, i+1)$ in a row which would cancel each other out / cannot happen in a legal sequence.

A small example shows that this bound is sharp. In the Dauvergne paper Sam mentioned in the comments, Figure 5 on p8 shows the permutahedron, a visualization of the $N = 4$ case. By Stanley's formula (1) on p3, there are 16 legal paths from $[1,2,3,4]$ at the bottom to $[4,3,2,1]$ on the top, each of length 6. Some of these paths have two transpositions each of $(1,2)$, $(2,3)$, and $(3,4)$, while some have an unequal distribution. The one along the right-hand side of the figure, for example, is red-green-red-blue-green-red, i.e., $(3,4),(2,3),(3,4),(1,2),(2,3),(3,4)$. By the reasoning above, no legal path / reduced word could have a certain transposition in 4 of the 6 steps, so $S^*_4 = 3$. The fussiness about the integer ceiling comes from the easier example of $N=3$ where the only possibilities are $(1,2),(2,3),(1,2)$ and $(2,3),(1,2),(2,3)$ which shows $S^*_3 = 2 = \lceil 3/2 \rceil$.

Edit: After convincing myself that there are no examples of legal length 10 sequences for $N = 5$ with any one transposition occurring 5 times, I wonder if there's actually an upper bound for $S^*_n$ that's linear in $N$. The intuition is that there are "balanced" sequences where each of the $N-1$ transpositions appear roughly an equal number of times (frequencies differ by at most 1); how much could the frequency for a given transposition vary from that?

Data: The balanced sequence $$(1,2),(4,5),(2,3),(3,4),(1,2),(4,5),(2,3),(3,4),(1,2),(2,3)$$ has frequencies $3,3,2,2$, while the sequence $$(1,2),(2,3),(3,4),(4,5),(1,2),(2,3),(3,4),(1,2),(2,3),(1,2)$$ has frequencies $4,3,2,1$.

An easy upper bound for $S^*_N$ is $\lceil N(N-1)/4 \rceil$, the integer ceiling of half the length of a legal sequence taking $[1,\ldots,N]$ to $[N,\ldots, 1]$. If some transposition $(i, i+1)$ occurred more often in the sequence, there would be two $(i, i+1)$ in a row which would cancel each other out / cannot happen in a legal sequence.

A small example shows that this bound is sharp. In the Dauvergne paper Sam mentioned in the comments, Figure 5 on p8 shows the permutahedron, a visualization of the $N = 4$ case. By Stanley's formula (1) on p3, there are 16 legal paths from $[1,2,3,4]$ at the bottom to $[4,3,2,1]$ on the top, each of length 6. Some of these paths have two transpositions each of $(1,2)$, $(2,3)$, and $(3,4)$, while some have an unequal distribution. The one along the right-hand side of the figure, for example, is red-green-red-blue-green-red, i.e., $(3,4),(2,3),(3,4),(1,2),(2,3),(3,4)$. By the reasoning above, no legal path / reduced word could have a certain transposition in 4 of the 6 steps, so $S^*_4 = 3$. The fussiness about the integer ceiling comes from the easier example of $N=3$ where the only possibilities are $(1,2),(2,3),(1,2)$ and $(2,3),(1,2),(2,3)$ which shows $S^*_3 = 2 = \lceil 3/2 \rceil$.

An easy upper bound for $S^*_N$ is $\lceil N(N-1)/4 \rceil$, the integer ceiling of half the length of a legal sequence taking $[1,\ldots,N]$ to $[N,\ldots, 1]$. If some transposition $(i, i+1)$ occurred more often in the sequence, there would be two $(i, i+1)$ in a row which would cancel each other out / cannot happen in a legal sequence.

A small example shows that this bound is sharp. In the Dauvergne paper Sam mentioned in the comments, Figure 5 on p8 shows the permutahedron, a visualization of the $N = 4$ case. By Stanley's formula (1) on p3, there are 16 legal paths from $[1,2,3,4]$ at the bottom to $[4,3,2,1]$ on the top, each of length 6. Some of these paths have two transpositions each of $(1,2)$, $(2,3)$, and $(3,4)$, while some have an unequal distribution. The one along the right-hand side of the figure, for example, is red-green-red-blue-green-red, i.e., $(3,4),(2,3),(3,4),(1,2),(2,3),(3,4)$. By the reasoning above, no legal path / reduced word could have a certain transposition in 4 of the 6 steps, so $S^*_4 = 3$. The fussiness about the integer ceiling comes from the easier example of $N=3$ where the only possibilities are $(1,2),(2,3),(1,2)$ and $(2,3),(1,2),(2,3)$ which shows $S^*_3 = 2 = \lceil 3/2 \rceil$.

Edit: After convincing myself that there are no examples of legal length 10 sequences for $N = 5$ with any one transposition occurring 5 times, I wonder if there's actually an upper bound for $S^*_n$ that's linear in $N$. The intuition is that there are "balanced" sequences where each of the $N-1$ transpositions appear roughly an equal number of times (frequencies differ by at most 1); how much could the frequency for a given transposition vary from that?

Data: The balanced sequence $$(1,2),(4,5),(2,3),(3,4),(1,2),(4,5),(2,3),(3,4),(1,2),(2,3)$$ has frequencies $3,3,2,2$, while the sequence $$(1,2),(2,3),(3,4),(4,5),(1,2),(2,3),(3,4),(1,2),(2,3),(1,2)$$ has frequencies $4,3,2,1$.

Source Link

created Dec 21, 2021 at 2:22

4.6k
32
45

An easy upper bound for $S^*_N$ is $\lceil N(N-1)/4 \rceil$, the integer ceiling of half the length of a legal sequence taking $[1,\ldots,N]$ to $[N,\ldots, 1]$. If some transposition $(i, i+1)$ occurred more often in the sequence, there would be two $(i, i+1)$ in a row which would cancel each other out / cannot happen in a legal sequence.

A small example shows that this bound is sharp. In the Dauvergne paper Sam mentioned in the comments, Figure 5 on p8 shows the permutahedron, a visualization of the $N = 4$ case. By Stanley's formula (1) on p3, there are 16 legal paths from $[1,2,3,4]$ at the bottom to $[4,3,2,1]$ on the top, each of length 6. Some of these paths have two transpositions each of $(1,2)$, $(2,3)$, and $(3,4)$, while some have an unequal distribution. The one along the right-hand side of the figure, for example, is red-green-red-blue-green-red, i.e., $(3,4),(2,3),(3,4),(1,2),(2,3),(3,4)$. By the reasoning above, no legal path / reduced word could have a certain transposition in 4 of the 6 steps, so $S^*_4 = 3$. The fussiness about the integer ceiling comes from the easier example of $N=3$ where the only possibilities are $(1,2),(2,3),(1,2)$ and $(2,3),(1,2),(2,3)$ which shows $S^*_3 = 2 = \lceil 3/2 \rceil$.