On the Number of Orientations of Random Graphs with No Directed Cycles of a Given Length
Oct 14, 2014
P. Allen, Y. Kohayakawa, G. O. Mota, R. F. Parente
Let H⃗ be an orientation of a graph H. Alon and Yuster 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. We consider the maximum number of H⃗-free orientations of typical graphs G(n,m) with n vertices and m edges. Suppose H⃗ =C↻ℓ is the directed cycle of length ℓ≥3. We show that if m≫n^(1+1/(ℓ−1)), then this maximum is 2^o(m), while if m≪n^(1+1/(ℓ−1)), then it is 2^(1−o(1))m.
The whole paper is available here.
Share on Facebook
