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 Twitter Share on FacebookNeuroCineMat |
---|
Featuring this week: |
Newsletter |
---|
Stay informed on our latest news! |
Follow Us on Facebook |
---|