---
_id: '9591'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Krivelevich, Michael
  last_name: Krivelevich
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
citation:
  ama: Krivelevich M, Kwan MA, Sudakov B. Cycles and matchings in randomly perturbed
    digraphs and hypergraphs. <i>Combinatorics, Probability and Computing</i>. 2016;25(6):909-927.
    doi:<a href="https://doi.org/10.1017/s0963548316000079">10.1017/s0963548316000079</a>
  apa: Krivelevich, M., Kwan, M. A., &#38; Sudakov, B. (2016). Cycles and matchings
    in randomly perturbed digraphs and hypergraphs. <i>Combinatorics, Probability
    and Computing</i>. Cambridge University Press. <a href="https://doi.org/10.1017/s0963548316000079">https://doi.org/10.1017/s0963548316000079</a>
  chicago: Krivelevich, Michael, Matthew Alan Kwan, and Benny Sudakov. “Cycles and
    Matchings in Randomly Perturbed Digraphs and Hypergraphs.” <i>Combinatorics, Probability
    and Computing</i>. Cambridge University Press, 2016. <a href="https://doi.org/10.1017/s0963548316000079">https://doi.org/10.1017/s0963548316000079</a>.
  ieee: M. Krivelevich, M. A. Kwan, and B. Sudakov, “Cycles and matchings in randomly
    perturbed digraphs and hypergraphs,” <i>Combinatorics, Probability and Computing</i>,
    vol. 25, no. 6. Cambridge University Press, pp. 909–927, 2016.
  ista: Krivelevich M, Kwan MA, Sudakov B. 2016. Cycles and matchings in randomly
    perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing.
    25(6), 909–927.
  mla: Krivelevich, Michael, et al. “Cycles and Matchings in Randomly Perturbed Digraphs
    and Hypergraphs.” <i>Combinatorics, Probability and Computing</i>, vol. 25, no.
    6, Cambridge University Press, 2016, pp. 909–27, doi:<a href="https://doi.org/10.1017/s0963548316000079">10.1017/s0963548316000079</a>.
  short: M. Krivelevich, M.A. Kwan, B. Sudakov, Combinatorics, Probability and Computing
    25 (2016) 909–927.
date_created: 2021-06-22T12:35:13Z
date_published: 2016-11-01T00:00:00Z
date_updated: 2023-02-23T14:02:07Z
day: '01'
doi: 10.1017/s0963548316000079
extern: '1'
external_id:
  arxiv:
  - '1501.04816'
intvolume: '        25'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1501.04816
month: '11'
oa: 1
oa_version: Preprint
page: 909-927
publication: Combinatorics, Probability and Computing
publication_identifier:
  eissn:
  - 1469-2163
  issn:
  - 0963-5483
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cycles and matchings in randomly perturbed digraphs and hypergraphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 25
year: '2016'
...