A note on counting orientations

Let H → be an orientation of a graph H. Alon and Yuster [The number of orientations having no fixed tournament, Combinatorica, 26 (2006), no. 1, 1–16] proposed the problem of determining or estimating D ( n , m , H → ) , the maximum number of H → -free orientations a graph with n vertices and m edges may have. If we replace the maximum by ʼessential maximumʼ, that is, if we are allowed to consider the maximum over the majority of n-vertex graphs with m edges, as opposed to all of them, the problem becomes more accessible. We show that this essential maximum is 2 o ( m ) if H → is the directed cycle C → ℓ of length ℓ ( ℓ ⩾ 3 ) , as long as m ≫ n 1 + 1 / ( ℓ − 1 ) , whereas it is 2 ( 1 − o ( 1 ) ) m if m ≪ n 1 + 1 / ( ℓ − 1 ) . The proof method yields results of the same nature for oriented bipartite graphs H → that contain a directed cycle.