Journal of Combinatorics

Volume 7 (2016)

Number 4

On the longest common pattern contained in two or more random permutations

Pages: 531 – 541

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n4.a1

Authors

Michael Earnest (Department of Mathematics, University of Southern California, Los Angeles, Calif., U.S.A.)

Anant Godbole (Department of Mathematics and Statistics, East Tennessee State University, Johnson City, Tenn., U.S.A.)

Yevgeniy Rudoy (Department of Mathematics, The Johns Hopkins University, Baltimore, Maryland, U.S.A.)

Abstract

We provide upper and lower bounds for the expected length $\mathbb{E} (L_{n,m})$ of the longest common pattern contained in m random permutations of length $n$.We also address the tightness of the concentration of $ L_{n,m}$ around $\mathbb{E} (L_{n,m})$.

Keywords

longest common pattern, pattern containment, random permutations

Full Text (PDF format)

Published 16 August 2016