Suppose $H$ is the following 4-vertex digraph : $$\langle V=\{a,b,c,d\}, E=\{ab,bd,ac,cd\}\rangle .$$ The digraph is drawn below:
Can one help me to prove upper bound $n^4/55$ on the number of $H$s in any n-vertex digraph G for G's that out-degree of every vertex is exactly $n/3$ and doesn't contain any directed triangle.
I would appreciate any help, thanks.
edit #1: In fact, I want an asymptotic bound (i.e. when n tends to infinity).
On
Just a quick clarification: is your digraph G simple? (no loops, no oriented cycles of length 2). Second, do you care about copies of H in G or induced copies of H in G? There is a paper by A.J.Bondy - Counting Subgraphs - which appeared in Discrete Mathematics in 1997 which I believe it could be useful.
If you don't specify any other structure of $G$ then you can have up to $4!{n \choose 4} = O(n^4)$ such subgraphs.
Edit. If you want to bound the number of such two paths you can argue as follows. Every such path is defined by a source vertex $v$, two of its neighbours $v',v''$ and a common neighbor of $v',v''.$ There are (being shallow with floorings/ceilings) up to ${n/3 \choose 2}$ ways to choose $v',v''$ and it can happen that $v',v''$ have $n/3$ common neighbours giving us a total of ${n/3 \choose 2}n/3$ such paths with start vertex $v$ and hence a total of ${n/3 \choose 2}n^2/3$ such subgraphs.