Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 23, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Patryk Morawski
In this talk I will present the results of my semester project with Kalina Petrova. 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 Aruaujo, 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(a, b) such that if T is an oriented tree with maximum degree b and D is an n-vertex digraph with minimum semidegree a*n then the graph obtained by adding cn uniformly random edges to D will contain T with high probability. Our proof involves a new technique for finding enough absorbers in the host graph D.
Automatic MiSe System Software Version 1.4803M | admin login