The asymptotic covering constant for permutations
The asymptotic covering constant for permutations
Let be the set of permutations of , and let denote the minimum number of -permutations needed to cover every -permutation. Asymptotic covering-constant conjecture. For some constant ,
and possibly . 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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.