Outdegree threshold conjecture for directed cycles
Outdegree threshold conjecture for directed cycles
An oriented graph is a directed graph without loops or multiple edges. For an oriented graph , let denote its minimum outdegree, and let denote a directed cycle of length . For , let be the smallest integer greater than that does not divide . Outdegree threshold conjecture. Fix an integer and let be the smallest integer greater than that does not divide . There exists such that every oriented graph on vertices with
contains . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.