The asymptotic covering constant for permutations

Let SnS_n be the set of permutations of {1,,n}\{1,\ldots,n\}, and let κn\kappa_n denote the minimum number of (n+1)(n+1)-permutations needed to cover every nn-permutation. Asymptotic covering-constant conjecture. For some constant AA,

lim supnκn(n+1)!/n2=A,\limsup_{n\to\infty}\frac{\kappa_n}{(n+1)!/n^2}=A,

and possibly A2A\le 2. The preceding argument gives an upper bound of the same order, while the hypergraph formulation suggests that the covering number has a well-defined asymptotic constant; determining this constant, and in particular whether it is at most 22, remains open.

Sources & referencesView supporting material

Primary source

Taylor Allison, Anant Godbole, Kathryn Hawley and Bill Kay, “Covering n-Permutations with (n+1)-Permutations”, arXiv:1203.5433 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.