On random digraphs and cores

Abstract

An acyclic homomorphism of a digraph $C$ to a digraph $D$ is a function $\rho :V(C)\to V(D)$ such that for every arc $uv$ of $C$, either $\rho (u)=\rho (v)$, or $\rho (u)\rho (v)$ is an arc of $D$ and for every vertex $v\in V(D)$, the subdigraph of $C$ induced by ${\rho }^{-1}(v)$ is acyclic. A digraph $D$ is a core if the only acyclic homomorphisms of $D$ to itself are automorphisms. In this paper, we prove that for certain choices of $p(n)$, random digraphs $D\in D(n,p(n))$ are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Prałat, The good, the bad, and the great: homomorphisms and cores of random graphs, Discrete Math., 309 (2009), no. 18, 5535-5539; MR2567955] concerning random graphs and cores.

9 pages, to appear in Australasian Journal of Combinatorics