On the Longest Common Pattern Contained in Two or More Random Permutations

Autor:	Earnest, Michael, Godbole, Anant, Rudoy, Yevgeniy
Rok vydání:	2014
Předmět:	Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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})$.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1402.0137 Zobrazit plný text záznamu View this record from Arxiv