Martin Klazar's paper Irreducible and connected permutations (pdf) states:

We call a permutation $\pi$ of $[n] = \{1, 2, \ldots, n\}$ disconnected iff there is an interval $I \subset [n]$, $2 \leq |I| \leq n - 1$ such that its image $\pi(I)$ also is an interval. If $\pi$ is not disconnected, it is connected.

Then it continues:

For example, all three permutations of length 1 and 2 are connected, all six permutations of length 3 are disconnected, and the only connected permutations of length 4 are $(2, 4, 1, 3)$ and $(3, 1, 4, 2)$.

I'm having trouble understanding the definitions of "connected" and "disconnected".

For instance, consider the permutation $(1, 3, 2)$, which is claimed to be disconnected. It therefore should have interval $I$ satisfying $2 \leq |I| \leq n - 1 = 2$ whose image under this permutation is also an interval. From my calculations, the images of all the sequences of length $2$ are not intervals:

  • $\pi([1, 2]) = (1, 3)$
  • $\pi([2, 3]) = (3, 2)$

(Maybe the confusion comes from a weak understanding of what an interval is in this context. Isn't it a contiguous, increasing sequence?)

Furthermore, I am curious about the broader applications of these concepts.

  • $\begingroup$ Are you using $(1,3,2)$ to denote the permutation that fixes $1$ and exchanges $2$ and $3$, or the permutation that sends $1$ to $3$, $3$ to $2$, and $2$ to $1$? In the former case, the interval $[2,3]$ is sent to itself, so you have an interval being sent to an interval (interval is a set, not an ordered set, so $\pi([2,3]) = [2,3]$); in the latter case, $\pi$ sends the interval $[2,3]=\{2,3\}$ to the interval $[1,2]=\{1,2\}$. $\endgroup$ – Arturo Magidin May 28 '11 at 22:48

If $I$ is a subset of $[n] = \{1,\ldots,n\}$ and $\pi$ is a permutation of $[n]$, then the image $\pi(I)$ is by definition the subset of $[n]$ consisting of all elements $\pi(x)$ for $x \in I$. There is no ordering on $\pi(I)$. Therefore $\pi( \{2,3\}) = \{3,2\} = \{2,3\}$, so this permutation is indeed disconnected.

I hadn't seen this definition for permutations before, so I'm not sure exactly what it's used for. (What happens in the paper?) But it does remind me of something that comes up in the theory of rearrangements of conditionally convergent series: there is a necessary and sufficient condition for a permutation $\pi$ of $\mathbb{Z}^+$ to change the sum of some convergent series: i.e., $\sum_n a_n \neq \sum_n a_{\sigma(n)}$. If I am remembering it correctly, the condition is that there should be some fixed number $N$ so that the image $\pi([n])$ is a union of at most $N$ intervals. (Note that $\pi$ is a permutation of all of $\mathbb{Z}^+$, so does not necessarily stabilize $[n]$.) Anyway, to my mathematical eye the definition "feels good": it is not hard to believe that it will be useful for something...

  • $\begingroup$ So if I understand correctly, an interval is a contiguous set (not sequence) of numbers? You do not mention anything about being contiguous. $\endgroup$ – dsg May 28 '11 at 23:59
  • $\begingroup$ @dsg: It is a set of integers which forms a contiguous interval. For example, $\{2000,2001,2002,2003\}$. In sets, the order of the elements doesn't matter. $\endgroup$ – Yuval Filmus May 29 '11 at 0:34
  • $\begingroup$ @dsg: yes, an interval is a contiguous set of numbers. I didn't mention contiguity explicitly because it didn't seem to be in question. $\endgroup$ – Pete L. Clark May 29 '11 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.