Factors in randomly perturbed hypergraphs

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 Ω(nk−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...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2022-03, Vol.60 (2), p.153-165
Main Authors: Chang, Yulin, Han, Jie, Kohayakawa, Yoshiharu, Morris, Patrick, Mota, Guilherme Oliveira
Format: Article
Language:English
Subjects:
absorbing method
Graph theory
Graphs
random graphs
randomly perturbed graphs
spanning structures
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Ω(nk−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, K4(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).
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.21035