A linear lower bound for directed-path length in terms of girth and minimum out-degree

For a digraph DD, let ell(D)ell(D) be the length of a longest directed path, let g(D)g(D) be its girth, and let δ+(D)\delta^+(D) be its minimum out-degree. Proposed weaker Thomassé conjecture. There is some constant c>0c>0 such that

(D)cg(D)δ+(D)\ell(D) \ge c\,g(D)\,\delta^+(D)

for every digraph DD.

This conjecture weakens Thomassé's proposed bound and is motivated by the paper's lower bounds for regular digraphs. The supplied text does not state whether it is known or remains open, so its database status is left open.

Sources & referencesView supporting material

Primary source

Yangyang Cheng and Peter Keevash, “On the length of directed paths in digraphs”, arXiv:2402.16776 (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.