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.
Classification :
03C15, 03C60, 03C65, 05A05, 05D10, 06A07, 22F50
Mots-clés :
random permutation, reduct, Ramsey theory, canonical function
Affiliations des auteurs :
Julie Linman
1
;
Michael Pinsker
2
1
University of Colorado, Boulder
2
Technische Universität Wien
Julie Linman; Michael Pinsker. Permutations on the random permutation. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4910
@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
