Definition of infinite permutations I've been trying to find a definition of an infinite permutation on-line without much success. Does there exist a canonical definition or are there various ways one might go about defining this?
The obvious candidate I guess would be a bijection p : {1,2,...} -> {1,2,...} between the natural numbers. One might also try to use the Robinson-Schensted correspondence between permutations of length n and pairs of standard Young tableaux of size n. Then one would need a definition of infinite Young tableaux.
Another correspondence that might be used is between permutations and permutation matrices.
 A: There are two closely related definitions which satisfy the properties you want. 
First, consider the group $\Sigma_k$ of all bijections $\pi: \Bbb Z \to \Bbb Z$ such that $\pi(x+k) = \pi(x)+k$ for all $x$.  Note that $S_k$ is a subgroup in $\Sigma_k$ - simply take any permutation of $\{1,\ldots,k\}$ and extend it periodically to all $x$.  This group (introduced by Lusztig) is finitely generated and is closely related to affine Lie algebra $\widehat A_k$.  The RSK algorithm does not exactly work here, but Lusztig does study the shape of Young diagrams (of what would be resulting two tableaux). The shape is a partition of $k$, and can be described using decreasing subsequences, extending Curtis Greene's theorem (I forgot if this is in Lusztig's paper or my own easy observation). 
Second, a somewhat related definition is the group $\Phi_k$ of bijections $\pi: \Bbb N \to \Bbb N$ such that $\pi(x+k) = \pi(x)+k$ for all $x$ large enough.  I studied this definition in this paper.  This group $\Phi_k$ is also finitely generated. It is very suitable for RSK, which is not always, but sometimes invertible.  The asymptotic shape I defined is essentially the same as Lusztig's.  Neither I nor anyone else studied the infinite matrix extension.  The infinite permutation version is already difficult enough.  
A: A permutation on a set A (which need not be countable) is just a bijective map A -> A.
A: Fon-Der-Flaass and Frid have recently introduced and studied infinite permutations as linear orderings of countable sets with respect to a given "natural" linear ordering. That is, given a countable set X (usually ℕ or ℤ), an infinite permutation π of X is a linear ordering ≤π of X that may differ from the "natural" linear ordering of X. If we take X to be finite, then this definition coincides with usual definition of a finite permutation as a bijective map from X to itself.
A: You might also be interested in the "juggling patterns" of Knutson, Lam, and Speyer, defined here: http://arxiv.org/abs/1111.3660.
Also known as bounded affine permutations, these are a subset of the affine permutations that Lusztig introduced mentioned by Igor Pak. Namely, they are the affine permutations $\Sigma_n$ (so $\pi$ a permutation $\mathbb{Z} \to \mathbb{Z}$ with $\pi(i+n) = \pi(i)+n$) that also satisfy $i \leq \pi(i) \leq i + n$. They are related to total positivity and the positroid stratification. There is a nice way to visualize them as juggling patterns, where the number of balls being juggled is equal to the average $\frac{1}{n}\sum_{i=1}^{n}(f(i) -i)$.
A: The bijection definition is fine, although it's not a very nice group.  One might also consider the group generated by all transpositions on {1, 2, ...}, which is the subgroup of all bijections that fix all but finitely many elements, and this group is likely to be much nicer; it's countable, for one thing.
Edit:  I guess it's worth noting that as far as I can tell the term infinite symmetric group is used by mathematicians to refer to the subgroup I described.  
