Abstract
An acyclic homomorphism of a digraph C to a digraph D is a function ρ: V (C) → 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 ε 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 ε D(n, p(n)) are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Prałat, Discrete Math. 309 (18) (2009), 5535- 5539; MR2567955] concerning random graphs and cores.
| Original language | English |
|---|---|
| Pages (from-to) | 371-379 |
| Number of pages | 9 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 79 |
| State | Published - Feb 2021 |
Funding
∗ Partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll), and partially supported by a 2017 University of Montana Graduate Student Summer Research Award funded by the George and Dorothy Bryan Endowment. This work forms part of the author’s PhD dissertation [7]. † Partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll).
| Funders | Funder number |
|---|---|
| Simons Foundation | 279367 |