Counting paths in digraphs

Say a digraph is kk-free if it has no directed cycles of length at most kk, for k∈Z+k∈Z+. Thomassé conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on nn vertices is at most (n−1)n(n+1)/15(n−1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n3/252n3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n3/16n3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n4/754n4/75 using Bondy’s result for Thomassé’s conjecture.