A note on counting orientations

Let 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 , the maximum number of -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 2o(m) if is the directed cycle of length ℓ(ℓ⩾3), as long as m≫n1+1/(ℓ−1), whereas it is 2(1−o(1))m if m≪n1+1/(ℓ−1). The proof method yields results of the same nature for oriented bipartite graphs that contain a directed cycle.