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

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 nsn-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.

Sources & referencesView supporting material

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.