Permutations on the random permutation

MaRDI QIDQ491556zbMATH OpenFDO

Authors Julie Linman, Michael Pinsker

Publication date 26 August 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.4297, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p54

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ramsey theoryrandom permutationcanonical functionreduct

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Groups as automorphisms of other structures (22F50) Ramsey theory (05D10) Model theory of denumerable and separable structures (03C15)

Abstract: The random permutation is the Fra"iss'e 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.

Recommendations

• The permutation group induced on a moiety
• Reducts of the random partial order
• A new operation on partially ordered sets.
• scientific article; zbMATH DE number 475365
• scientific article; zbMATH DE number 66613

Cites work

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Decidability of definability
• Directed graphs and boron trees
• Homogeneous permutations
• Minimal functions on the random graph
• New Ramsey classes from old
• Ramsey properties of permutations
• Reducts of Ramsey structures
• Reducts of random hypergraphs
• Reducts of the random graph
• Reducts of the random partial order
• The 116 reducts of (ℚ, <, a)
• The 42 reducts of the random ordered graph
• Transitivity of permutation groups on unordered sets

Cited in

(10)

• The match of a random permutation has the FKG property
• Tractable combinations of temporal CSPs
• The 42 reducts of the random ordered graph
• NIP ω$\omega$‐categorical structures: The rank 1 case
• Quasirandom permutations
• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• Random list permutations in place
• scientific article; zbMATH DE number 4204349 (Why is no real title available?)

This page was built for publication: Permutations on the random permutation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491556)