<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Dense Packing of Patterns in a Permutation
Henrik Eriksson1, Kimmo Eriksson2, Svante Linusson3, and Johan Wästlund4
1NADA, KTH, SE-100 44 Stockholm, Sweden
henrik@nada.kth.se
2IMA, Mälardalens högskola, SE-721 23 Västerås, Sweden
kimmo.eriksson@mdh.se
3Department of Mathematics, KTH, SE-100 44 Stockholm, Sweden
linusson@math.kth.se
4MaI, Linköpings universitet, SE-581 83 Linköping, Sweden
jowas@mai.liu.se
Annals of Combinatorics 11 (3-4) p.459-470 September, 2007
AMS Subject Classification:05A05, 05D40
Abstract:
We study the length Lk of the shortest permutation containing all patterns of length k. We establish the bounds e-2k2< Lk ≤(2⁄3+o(1))k2. We also prove that as k →∞, there are permutations of length (1⁄4+o(1))k2 containing almost all patterns of length k.
Keywords: pattern containment, permutation statistic

References:

1. M.H. Albert, M. Coleman, R. Flynn, and I. Leader, Permutations containing many patterns, Ann. Combin., to appear.

2. N. Alon and J. Spencer, The Probabilistic Method, John Wiley & Sons, New York, 2000.

3. R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin. 6 (1999) #N1.

4. F. Chung, P. Diaconis, and R. Graham, Universal cycles for combinatorial structures, Discrete Math. 110 (1-3) (1992) 43--59.

5. K. Eriksson, Strong convergence and a game of numbers, Europ. J. Combin. 17 (4) (1996) 379--390.

6. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383-- 406.