* Allan Wechsler <acwacw@gmail.com> [Feb 18. 2010 08:21]:
OK, let me see if I understand this. We write a permutation P on the integers [1...n] as (P(1), P(2), ..., P(n)). If we cut this sequence off prematurely, at only k elements, k < n, we get a proper prefix. This is not typically a permutation itself, but sometimes it is; if this is the case, the permutation is not connected. A connected permutation is one that has no "cut"; for all k < n, the prefix of length k contains an integer greater than k.
Correct.
The reason it took me a long time to figure out what we were talking about is that this is not really a group-theoretic property, and my reflex is to think of permutations as elements of a group;
I see. There are plenty of things considered with permutations (of letters 1,2,...,n) that are anything but algebraic, such as rises and falls (e.g. in up-down perms where a0 < a1 > a2 < a3 > a4 <... ). Playful combinatorialists 8-))
in the algebraic context, the objects being permuted are abstract frobs, which can be labeled with integers or letters or anything else. Another way to say this is that you can have two similar permutations, indistinguishable algebraically, only one of which is "connected".
Similar permutations A,B, are such that there is some perm P such that A = P * B * P^{-1}. Each equiv classe contains all perms with identical cycle spectrum (corresponding to an integer partition). Now fix the partition, say n = M_1*L_1+M_2*L_2+...+M_u*L_u (M_k cycles of length L_k). Now you could choose as a representative for the class that is determined by the partition above as the (non-connected) perm that maps the M_1 prefixes of length L_1 to itself etc.
If a permutation is not the identity, it is always similar to a connected permutation; to prove this, pick any moving element x, and label x as "1" and P(x) as "n". Then the representation of P begins with an n, guaranteeing connectedness.
Yes: if there is at least one nontrivial cycle in a permutation then its class contains one where the first position is n (it contains the cycle (n -> 1 -> ...) ) [I may have been sloppy here as I didn't distinguish the permutations (maps) from actions (on the unit perm, an arrangement of letters)]
On Wed, Feb 17, 2010 at 2:02 PM, Joerg Arndt <arndt@jjj.de> wrote:
* Schroeppel, Richard <rschroe@sandia.gov> [Feb 17. 2010 19:49]:
What's "connected"? Everything in one big cycle? --Rich
A permutation is "connected" if no proper prefix is mapped to itself.
Test: compute maxima of all proper prefixes (cost is O(n)) and check the current max (for, say, length-k prefix) is greater than k (assuming you permute [1,2,...,n]).
The name "connected" may reflect that a non-connected permutation can be written as concat of two perms ( P1(prefix) . P2(suffix) ), but then maybe it's just another name as stupid as "root system".
"one big cycle" perms are "cyclic" perms (which, together with "all permutations" are trivial to create unbiased).