Kézdy–Snevily conjecture for the covering function of permutation space

About 17 years old · traced to

Let Sn\mathcal{S}_n be the set of permutations of [n]={1,2,…,n}[n]=\{1,2,\dots,n\}, with Hamming distance dHd_H. Define f(n,s)f(n,s) to be the minimum size of a subset of Sn\mathcal{S}_n having covering radius at most n−sn-s. Kézdy–Snevily conjecture. If nn is even, then f(n,2)=nf(n,2)=n; if nn is odd, then f(n,2)>nf(n,2)>n. The conjecture is motivated by its implications for the latin-square transversal conjectures, and the paper proves that its odd-nn case implies the whole conjecture. The source gives no resolution status for the conjecture itself.

References

Primary source

Kevin Hendrey and Ian M. Wanless, “Covering radius in the Hamming permutation space”, arXiv:1811.09040 (2019).

Additional references

2 papers in this index state this conjecture (2009–2018). The statement above is taken from the most recent of them; the others are arXiv:0903.5142.

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.