Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees - Morawski, Patryk; Petrova, Kalina (The Electronic Journal of Combinatorics, 2026)
We show that a randomly perturbed digraph, where we start with a dense digraph D_α and add a small number of random edges to it, will typically contain a fixed orientation of a bounded-degree spanning tree. This answers a question posed by Araujo, Balogh, Krueger, Piga and Treglown and generalizes the corresponding result for randomly perturbed graphs by Krivelevich, Kwan and Sudakov. More specifically, we prove that there exists a constant c = c(α, Δ) such that if T is an oriented tree with maximum degree Δ and D_α is an n-vertex digraph with minimum semidegree α n, then the graph obtained by adding cn uniformly random edges to D_α will contain T with high probability.