Conjectured threshold for powers of Hamilton cycles

About 3 years old · traced to

Let ϱ(Kr)\varrho(K_r) denote the graph parameter used in the source, and let GG be an nn-vertex graph with minimum degree δ(G)\delta(G) and independence number α(G)\alpha(G). The rr-th power of a Hamilton cycle is obtained by joining every pair of vertices at cyclic distance at most rr on a Hamilton cycle.

Connecting-barrier conjecture. Given μ>0\mu>0 and r≥4r\geq 4, there exists α>0\alpha>0 such that the following holds for sufficiently large nn. If

δ(G)≥2−ϱ(Kr)3−2ϱ(Kr)n+μn\delta(G)\geq \frac{2-\varrho(K_r)}{3-2\varrho(K_r)}n+\mu n

and

α(G)≤αn,\alpha(G)\leq \alpha n,

then GG contains an rr-th power of a Hamilton cycle.

The conjecture is motivated by a construction called the connecting barrier, which gives a matching asymptotic lower bound in the source for r≥3r\geq 3. Its resolution status is not specified here.

References

Primary source

Ming Chen, Jie Han, Yantao Tang and Donglei Yang, “On powers of Hamilton cycles in Ramsey-Turán Theory”, arXiv:2305.17360 (2023).

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.