Cycles and matchings in randomly perturbed digraphs and hypergraphs

Krivelevich M, Kwan MA, Sudakov B. 2016. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing. 25(6), 909–927.


Journal Article | Published | English

Scopus indexed
Author
Krivelevich, Michael; Kwan, Matthew AlanIST Austria; Sudakov, Benny
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.
Publishing Year
Date Published
2016-11-01
Journal Title
Combinatorics, Probability and Computing
Volume
25
Issue
6
Page
909-927
ISSN
eISSN
IST-REx-ID

Cite this

Krivelevich M, Kwan MA, Sudakov B. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing. 2016;25(6):909-927. doi:10.1017/s0963548316000079
Krivelevich, M., Kwan, M. A., & Sudakov, B. (2016). Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing. Cambridge University Press. https://doi.org/10.1017/s0963548316000079
Krivelevich, Michael, Matthew Alan Kwan, and Benny Sudakov. “Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs.” Combinatorics, Probability and Computing. Cambridge University Press, 2016. https://doi.org/10.1017/s0963548316000079.
M. Krivelevich, M. A. Kwan, and B. Sudakov, “Cycles and matchings in randomly perturbed digraphs and hypergraphs,” Combinatorics, Probability and Computing, vol. 25, no. 6. Cambridge University Press, pp. 909–927, 2016.
Krivelevich M, Kwan MA, Sudakov B. 2016. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing. 25(6), 909–927.
Krivelevich, Michael, et al. “Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs.” Combinatorics, Probability and Computing, vol. 25, no. 6, Cambridge University Press, 2016, pp. 909–27, doi:10.1017/s0963548316000079.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1501.04816

Search this title in

Google Scholar