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

P. Allen, Y. Kohayakawa, G. O. Mota, R. F. Parente

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}$.


Keywords


directed graphs; random graphs; orientations

Full Text: PDF