Conjecture on powers of Hamilton cycles in pseudorandom graphs

About 12 years old · traced to

For k≥2k\geq 2, let an (ε,p,k−1,k)(\varepsilon,p,k-1,k)-pseudorandom graph mean a graph satisfying the stated pseudorandomness condition with parameters (ε,p,k−1,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 k≥2k\geq 2, the pseudorandomness requirement in Theorem 1 can be replaced by (ε,p,k−1,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.

References

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.