Cycles and matchings in randomly perturbed digraphs and hypergraphs

Abstract

We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.

17 pages, 2 figures. Addressed referee's comments, streamlined proof of Lemma 6

References in corpus (1)

• Adding random edges to dense graphs

Cited by in corpus (12)

• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Hamilton Cycles in Random Graphs: a bibliography
• Triangles in randomly perturbed graphs
• Ramsey properties of randomly perturbed dense graphs
• Hamiltonicity in randomly perturbed hypergraphs
• Spanning trees in randomly perturbed graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Tree decompositions of graphs without large bipartite holes
• Factors in randomly perturbed hypergraphs
• Rainbow trees in uniformly edge-coloured graphs
• Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments