On the number of orientations of random graphs with no directed cycles of a given length
2014
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}$.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
8
Citations
NaN
KQI