On random digraphs and cores

An acyclic homomorphism of a digraph $C$ to a digraph $D$ is a function $ρ\colon V(C)\to V(D)$ such that for every arc $uv$ of $C$, either $ρ(u)=ρ(v)$, or $ρ(u)ρ(v)$ is an arc of $D$ and for every vertex $v\in V(D)$, the subdigraph of $C$ induced by $ρ^{-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.

No reviews yet.

No comments yet.