Universality of random permutations

DOI10.1112/BLMS.12345MaRDI QIDQ3300092zbMATH OpenOpenAlexFDO

Authors Xiaoyu He, Matthew Kwan

Publication date 27 July 2020

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.12878

zbMATH Keywords

Alon's conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: It is a classical fact that for any $varepsilon>0$, a random permutation of length $n=(1+varepsilon)k^2/4$ typically contains a monotone subsequence of length $k$. As a far-reaching generalization, Alon conjectured that a random permutation of this same length $n$ is typically $k$-universal, meaning that it simultaneously contains every pattern of length $k$. He also made the simple observation that for $n=O(k^{2}logk)$, a random length-$n$ permutation is typically $k$-universal. We make the first significant progress towards Alon's conjecture by showing that $n=2000k^{2}loglogk$ suffices.

Recommendations

• Universality for random permutations and some other groups
• On the longest common pattern contained in two or more random permutations
• Lower bounds for superpatterns and universal sequences
• scientific article; zbMATH DE number 1047715
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern

Cites work

• A variational problem for random Young tableaux
• Adjacency labeling schemes and induced-universal graphs
• Asymptotic bounds for permutations containing many different patterns
• Asymptotically optimal induced universal graphs
• Better upper bounds on the Füredi-Hajnal limits of permutations
• Classification of bijections between 321- and 132-avoiding permutations
• Combinatorics and probability. Abstracts from the workshop held April 17--23, 2016
• Concentration of Measure for the Analysis of Randomized Algorithms
• Containing all permutations
• Dense packing of patterns in a permutation
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Hammersley's interacting particle process and longest increasing subsequences
• On minimal n-universal graphs
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• The surprising mathematics of longest increasing subsequences
• Universal graphs and universal functions

Cited in

(9)

• The match of a random permutation has the FKG property
• Lower bounds for superpatterns and universal sequences
• Universality for random permutations and some other groups
• Indifferentiability of truncated random permutations
• Universal arrays
• A note on universal and canonically coloured sequences
• scientific article; zbMATH DE number 524370 (Why is no real title available?)
• An alternative proof for the expected number of distinct consecutive patterns in a random permutation
• On ordered Ramsey numbers of matchings versus triangles (extended abstract)

This page was built for publication: Universality of random permutations

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