On the number of orientations of random graphs with no directed cycles of a given length (Q405150)

Summary: Let \(\vec H\) be an orientation of a graph \(H\). \textit{N. Alon} and \textit{R. Yuster} [Combinatorica 26, No. 1, 1--16 (2006; Zbl 1107.05040)] proposed the problem of determining or estimating \(D(n,m,\vec H)\), the maximum number of \(\vec H\)-free orientations a graph with \(n\) vertices and \(m\) edges may have. We consider the maximum number of \(\vec H\)-free orientations of typical graphs \(G(n,m)\) with \(n\)~vertices and \(m\) edges. Suppose \(\vec H =C^\circlearrowright_\ell \) is the directed cycle of length \(\ell\geq 3\). We show that if \({m\gg n^{1+1/(\ell-1)}}\), then this maximum is \(2^{o(m)}\), while if \({m\ll n^{1+1/(\ell-1)}}\), then it is \(2^{(1-o(1))m}\).