Conjecture on powers of Hamilton cycles in pseudorandom graphs

For k2k\geq 2, let an (ε,p,k1,k)(\varepsilon,p,k-1,k)-pseudorandom graph mean a graph satisfying the stated pseudorandomness condition with parameters (ε,p,k1,k)(\varepsilon,p,k-1,k). The kkth power of a Hamilton cycle is obtained by joining every pair of vertices whose distance on the cycle is at most kk. Powers-of-Hamilton-cycles conjecture. For all k2k\geq 2, the pseudorandomness requirement in Theorem 1 can be replaced by (ε,p,k1,k)(\varepsilon,p,k-1,k)-pseudorandomness. This would extend the result proved in the paper for squared Hamilton cycles to all higher powers, under a weaker pseudorandomness requirement.

Sources & referencesView supporting material

Primary source

Peter Allen, Julia Böttcher, Hiep Hàn, Yury Person and Yoshiharu Kohayakawa, “Powers of Hamilton cycles in pseudorandom graphs”, arXiv:1402.0984 (2014).

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.