2-universality in randomly perturbed graphs. (June 2020) - Parczyk, Olaf
Abstract: A graph G is called universal for a family of graphs F if it contains every element F ∈ F as a subgraph. Let F ( n, 2 ) be the family of all graphs with maximum degree 2. Ferber et al. (2019) proved that there exists a C such that for p ≥ C ( n − 2 ∕ 3 log 1 ∕ 3 n ) the random graph G ( n, p ) a.a.s is F ( n, 2 ) -universal, which is asymptotically optimal. For any n -vertex graph G α with minimum degree δ ( G α ) ≥ α n Aigner and Brandt (1993) proved that G α is F ( n, 2 ) -universal if α ≥ 2 ∕ 3 (and this is optimal). In this note, we consider the model of randomly perturbed graphs, which is the union G α ∪ G ( n, p ) . We prove that a.a.s. G α ∪ G ( n, p ) is F ( n, 2 ) -universal provided that α ∈ ( 0, 1 ) and p = ω ( n − 2 ∕ 3 ) . This is asymptotically optimal and improves on both results from above in the respective parameter. Furthermore, this extends a result of Böttcher et al. (in press), who embed a given F ∈ F ( n, 2 ) at these values. We also prove variants with universality for the family F ℓ ( n, 2 ), all graphs from F ( n, 2 ) with girth at least ℓ . For example, there exists an ℓ 0 depending only on α such that for all ℓ ≥ ℓ 0 already p = ω ( 1 ∕ n ) is sufficient for F ℓ ( n, 2 ) -universality.