Factors in randomly perturbed hypergraphs

Yulin Chang, Jie Han*, Yoshiharu Kohayakawa, Patrick Morris, Guilherme Oliveira Mota

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 (Formula presented.) to ensure an F-factor with high probability, for any F that belongs to a certain class (Formula presented.) of k-graphs, which includes, for example, all k-partite k-graphs, (Formula presented.) 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).

Original languageEnglish
Pages (from-to)153-165
Number of pages13
JournalRandom Structures and Algorithms
Volume60
Issue number2
DOIs
Publication statusPublished - Mar 2022

Fingerprint

Dive into the research topics of 'Factors in randomly perturbed hypergraphs'. Together they form a unique fingerprint.

Cite this

Chang, Y., Han, J., Kohayakawa, Y., Morris, P., & Mota, G. O. (2022). Factors in randomly perturbed hypergraphs. Random Structures and Algorithms, 60(2), 153-165. https://doi.org/10.1002/rsa.21035