Körner–Malvenuto's maximal colliding-permutations conjecture

About 19 years old · traced to

Let [n]={1,…,n}[n]=\{1,\dots,n\}. Two permutations π1,π2\pi_1,\pi_2 of [n][n] are colliding if there is an index i∈[n]i\in[n] such that ∣π1(i)−π2(i)∣=1|\pi_1(i)-\pi_2(i)|=1.

Körner–Malvenuto's conjecture. The maximal number of pairwise colliding permutations of [n][n] is

(n⌊n2⌋).\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}.

The paper recalls this earlier extremal question as motivation for studying graph-different Hamiltonian paths. Its status is not specified in the source.

References

Primary source

István Kovács and Dániel Soltész, “Triangle-different Hamiltonian paths”, arXiv:1608.05237 (2016).

Additional references

3 papers in this index state this conjecture (2007–2016). The statement above is taken from the most recent of them; the others are arXiv:1106.0725, arXiv:0712.1442.

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.