Outdegree threshold conjecture for directed cycles

An oriented graph is a directed graph without loops or multiple edges. For an oriented graph GG, let δ+(G)\delta^+(G) denote its minimum outdegree, and let CC_\ell denote a directed cycle of length \ell. For 4\ell\ge4, let kk be the smallest integer greater than 22 that does not divide \ell. Outdegree threshold conjecture. Fix an integer 4\ell\ge4 and let kk be the smallest integer greater than 22 that does not divide \ell. There exists n0:=n0()n_0:=n_0(\ell) such that every oriented graph GG on nn0n\ge n_0 vertices with

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

contains CC_\ell. The conjecture concerns the gap between outdegree and semidegree thresholds; the paper notes that these thresholds differ by less than one is expected, but does not establish this statement in general.

Sources & referencesView supporting material

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