The random permutation is the Fraïssé limit of the class of finite structures with two linear orders. Answering a problem stated by Peter Cameron in 2002, we use a recent Ramsey-theoretic technique to show that there exist precisely 39 closed supergroups of the automorphism group of the random permutation, and thereby expose all symmetries of this structure. Equivalently, we classify all structures which have a first-order definition in the random permutation.
@article{10_37236_4910,
author = {Julie Linman and Michael Pinsker},
title = {Permutations on the random permutation},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/4910},
zbl = {1528.03155},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4910/}
}
TY - JOUR
AU - Julie Linman
AU - Michael Pinsker
TI - Permutations on the random permutation
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/4910/
DO - 10.37236/4910
ID - 10_37236_4910
ER -
%0 Journal Article
%A Julie Linman
%A Michael Pinsker
%T Permutations on the random permutation
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4910/
%R 10.37236/4910
%F 10_37236_4910
Julie Linman; Michael Pinsker. Permutations on the random permutation. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4910
