Factors in randomly perturbed hypergraphs

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 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, 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).

Locations

• arXiv (Cornell University) - View - PDF
• Random Structures and Algorithms - View