Asymptotic odd-cycle-different Hamiltonian paths conjecture

For integers k>1k>1, let C2k+1C_{2k+1} denote the cycle of odd length 2k+12k+1. Two Hamiltonian paths on nn vertices are C2k+1C_{2k+1}-different if their union contains a subgraph isomorphic to C2k+1C_{2k+1}.

Asymptotic odd-cycle-different Hamiltonian paths conjecture. If k>1k>1, then the maximal number of pairwise C2k+1C_{2k+1}-different Hamiltonian paths on nn vertices is at least

2no(n).2^{n-o(n)}.

This is stated as a weaker version of the preceding odd-cycle conjecture. The authors report that it is proved when 2k2k is a power of two, while the general case remains open.

Sources & referencesView supporting material

Primary source

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

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.