Factors in randomly perturbed hypergraphs

DOI10.1002/RSA.21035MaRDI QIDQ6074679zbMATH OpenOpenAlexFDO

Authors Yu-Lin Chang, Jie Han, Yoshiharu Kohayakawa, Patrick Morris, G. O. Mota

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.01031

zbMATH Keywords

absorbing methodrandom graphsrandomly perturbed graphsspanning structures

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

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 $mathcalF$ 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).

Recommendations

• Tiling multipartite hypergraphs in quasi-random hypergraphs
• Factors in random graphs
• \(H(n)\)-factors in random graphs
• Triangles in randomly perturbed graphs
• Hamiltonicity in randomly perturbed hypergraphs

Cites work

• \(H\)-factors in dense graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Embedding large subgraphs into dense graphs
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Factors in random graphs
• Hamilton -cycles in randomly perturbed hypergraphs
• Hamiltonicity in randomly perturbed hypergraphs
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Nonvertex-balanced factors in random graphs
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• On smoothed analysis in dense graphs and formulas
• On the Complexity of General Graph Factor Problems
• Powers of Hamiltonian cycles in randomly augmented graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Proof of the Alon-Yuster conjecture
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Recent advances on Dirac-type problems for hypergraphs
• Spanning trees in random graphs
• Spanning trees in randomly perturbed graphs
• Sprinkling a few random edges doubles the power
• Supersaturated graphs and hypergraphs
• The minimum degree threshold for perfect graph packings
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Vertex Ramsey properties of randomly perturbed graphs

Cited in

(5)

• Tiling multipartite hypergraphs in quasi-random hypergraphs
• Embedding clique-factors in graphs with low -independence number
• Graph Tilings in Incompatibility Systems
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Clique-factors in graphs with sublinear -independence number

This page was built for publication: Factors in randomly perturbed hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074679)