2-universality in randomly perturbed graphs. (June 2020)

• Record Type: Journal Article
• Authors: Parczyk, Olaf
• Is Part Of: European journal of combinatorics. Volume 87(2020)
• Publication Date: 2020-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103118
• Languages: English
• ISSNs: 0195-6698

Abstract

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.