Conjectured threshold for powers of Hamilton cycles

From papers

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 r4r\geq 4, there exists α>0\alpha>0 such that the following holds for sufficiently large nn. If

δ(G)2ϱ(Kr)32ϱ(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 r3r\geq 3. Its resolution status is not specified here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.