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²

¹London School of Economics
²Universidade de São Paulo

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

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

Détail

DOI : 10.37236/3699

Classification : 05C80, 05C20, 05C35, 05C38
Mots-clés : directed graphs, random graphs, orientations