On the Number of Orientations of Random Graphs with No Directed Cycles of a Given Length

Abstract

Let $\vec H$ be an orientation of a graph $H$. Alon and Yuster 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}$.