Factors in randomly perturbed hypergraphs. Issue 2 (20th July 2021)

• Record Type: Journal Article
• Authors: Chang, Yulin; Han, Jie; Kohayakawa, Yoshiharu; Morris, Patrick; Mota, Guilherme Oliveira
• Is Part Of: Random structures & algorithms. Volume 60:Issue 2(2022)
• Page Start: 153
• Page End: 165
• Publication Date: 2021-07-20
• Subjects: absorbing method -- random graphs -- randomly perturbed graphs -- spanning structures; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21035
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We determine, up to a multiplicative constant, the optimal number of random edges that need to be added to a k ‐graph H with minimum vertex degree Ω ( n k − 1 ) to ensure an F ‐factor with high probability, for any F that belongs to a certain class ℱ of k ‐graphs, which includes, for example, all k ‐partite k ‐graphs, K 4 ( 3 ) − and the Fano plane. In particular, taking F to be a single edge, this settles a problem of Krivelevich, Kwan, and Sudakov. We also address the case in which the host graph H is not dense, indicating that starting from certain such H is essentially the same as starting from an empty graph (namely, the purely random model).