Premium
EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
Author(s) -
Böttcher Julia,
Montgomery Richard,
Parczyk Olaf,
Person Yury
Publication year - 2020
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/mtk.12005
Subject(s) - mathematics , combinatorics , degree (music) , bounded function , vertex (graph theory) , discrete mathematics , upper and lower bounds , embedding , graph , mathematical analysis , physics , artificial intelligence , computer science , acoustics
We study the modelG α ∪ G ( n , p )of randomly perturbed dense graphs, where G α is any n ‐vertex graph with minimum degree at least α n and G ( n , p ) is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model using absorption. This approach yields simpler proofs of several known results. We also use it to derive the following two new results. For every α > 0 and Δ ≥ 5 , and every n ‐vertex graph F with maximum degree at most Δ, we show that if p = ω ( n − 2 / ( Δ + 1 ) ) , thenG α ∪ G ( n , p )with high probability contains a copy of F . The bound used for p here is lower by a log ‐factor in comparison to the conjectured threshold for the general appearance of such subgraphs in G ( n , p ) alone, a typical feature of previous results concerning randomly perturbed dense graphs. We also give the first example of graphs where the appearance threshold inG α ∪ G ( n , p )is lower than the appearance threshold in G ( n , p ) by substantially more than a log ‐factor. We prove that, for every k ≥ 2 and α > 0 , there is some η > 0 for which the k th power of a Hamilton cycle with high probability appears inG α ∪ G ( n , p )when p = ω ( n − 1 / k − η ) . The appearance threshold of the k th power of a Hamilton cycle in G ( n , p ) alone is known to be n − 1 / k , up to a log ‐term when k = 2 , and exactly for k > 2 .