← All problems

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

15 years old · traced to

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 n≥n0n\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.

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.

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

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.