Universality of random permutations

He X, Kwan MA. 2020. Universality of random permutations. Bulletin of the London Mathematical Society. 52(3), 515–529.


Journal Article | Published | English

Scopus indexed
Author
Abstract
It is a classical fact that for any ε>0, a random permutation of length n=(1+ε)k2/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(k2logk), a random length-n permutation is typically k-universal. We make the first significant progress towards Alon's conjecture by showing that n=2000k2loglogk suffices.
Publishing Year
Date Published
2020-06-01
Journal Title
Bulletin of the London Mathematical Society
Volume
52
Issue
3
Page
515-529
ISSN
eISSN
IST-REx-ID

Cite this

He X, Kwan MA. Universality of random permutations. Bulletin of the London Mathematical Society. 2020;52(3):515-529. doi:10.1112/blms.12345
He, X., & Kwan, M. A. (2020). Universality of random permutations. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12345
He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.” Bulletin of the London Mathematical Society. Wiley, 2020. https://doi.org/10.1112/blms.12345.
X. He and M. A. Kwan, “Universality of random permutations,” Bulletin of the London Mathematical Society, vol. 52, no. 3. Wiley, pp. 515–529, 2020.
He X, Kwan MA. 2020. Universality of random permutations. Bulletin of the London Mathematical Society. 52(3), 515–529.
He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.” Bulletin of the London Mathematical Society, vol. 52, no. 3, Wiley, 2020, pp. 515–29, doi:10.1112/blms.12345.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1911.12878

Search this title in

Google Scholar