Journal of Combinatorics

Volume 7 (2016)

Number 4

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

Pages: 531 – 541



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.)


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})$.


longest common pattern, pattern containment, random permutations

Full Text (PDF format)