Kelly–Kühn–Osthus conjecture on directed cycle semidegree thresholds

An oriented graph is a directed graph without loops or multiple edges. For an oriented graph GG, let δ±(G)\delta^\pm(G) be its minimum semidegree, the smaller of its minimum indegree and minimum outdegree. For an integer 4\ell\ge4, let kk be the smallest integer greater than 22 that does not divide \ell. Kelly–Kühn–Osthus conjecture. For every 4\ell\ge4 there exists n0:=n0()n_0:=n_0(\ell) such that every oriented graph GG on nn0n\ge n_0 vertices with

δ±(G)nk+1k\delta^\pm(G) \ge \frac{n}{k}+\frac{1}{k}

contains a directed cycle of length exactly \ell. The conjectured threshold is best possible up to the stated additive term, as shown by balanced blow-ups of a directed kk-cycle. The conjecture is proved when k=3k=3; the paper resolves the remaining cases for cycles of length divisible by 33 but not equal to 33.

Sources & referencesView supporting material

Primary source

Andrzej Grzesik and Jan Volec, “Degree conditions forcing directed cycles”, arXiv:2102.12830 (2024).

Additional references

2 papers in this index state this conjecture (2011–2021). The statement above is taken from the most recent of them; the others are arXiv:1110.5669.

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.