Factors in randomly perturbed hypergraphs

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 $\Omega (n^{k-1})$ to ensure an $F$-factor with high probability, for any $F$ that belongs to a certain class $\mathcal{F}$ of $k$-graphs, which includes, e.g., 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 [Combin. Probab. Comput. 25 (2016), 909--927]. 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).

arXiv comment13 pages, minor updates after referee comments. To appear in Random Structures & Algorithms (RSA)

References in corpus (5)

• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Embedding bounded degree spanning trees in random graphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Adding random edges to create the square of a Hamilton cycle
• Ramsey properties of randomly perturbed dense graphs

Cited by in corpus (1)

• A Ramsey-Turán theory for tilings in graphs