---
OA_place: publisher
OA_type: hybrid
_id: '19503'
abstract:
- lang: eng
text: "A tantalizing open problem, posed independently by Stiebitz in 1995 and by
Alon in 1996 and again in 2006, asks whether for every pair of integers s,t≥1
there exists a finite number F(s,t)\r\nsuch that the vertex set of every digraph
of minimum out-degree at least F(s,t) can be partitioned into non-empty parts
\ A and B such that the subdigraphs induced on A\r\n and B have minimum
out-degree at least s and t , respectively.\r\nIn this short note, we prove
that if F(2,2) exists, then all the numbers F(s,t) with s,t≥1\r\n exist
and satisfy F(s,t)=Θ(s+t) . In consequence, the problem of Alon and Stiebitz
reduces to the case s=t=2 . Moreover, the numbers F(s,t) with s,t≥2 either
all exist and grow linearly, or all of them do not exist."
acknowledgement: Funded by SNSF Ambizione grant No. 216071. This project has received
funding from the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie grant agreement No, 101034413. Funded by SNSF grant
CRSII5, 173721.
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Micha
full_name: Christoph, Micha
last_name: Christoph
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
- first_name: Raphael
full_name: Steiner, Raphael
last_name: Steiner
citation:
ama: Christoph M, Petrova KH, Steiner R. A note on digraph splitting. Combinatorics
Probability and Computing. 2025;34(4):559-564. doi:10.1017/S0963548325000045
apa: Christoph, M., Petrova, K. H., & Steiner, R. (2025). A note on digraph
splitting. Combinatorics Probability and Computing. Cambridge University
Press. https://doi.org/10.1017/S0963548325000045
chicago: Christoph, Micha, Kalina H Petrova, and Raphael Steiner. “A Note on Digraph
Splitting.” Combinatorics Probability and Computing. Cambridge University
Press, 2025. https://doi.org/10.1017/S0963548325000045.
ieee: M. Christoph, K. H. Petrova, and R. Steiner, “A note on digraph splitting,”
Combinatorics Probability and Computing, vol. 34, no. 4. Cambridge University
Press, pp. 559–564, 2025.
ista: Christoph M, Petrova KH, Steiner R. 2025. A note on digraph splitting. Combinatorics
Probability and Computing. 34(4), 559–564.
mla: Christoph, Micha, et al. “A Note on Digraph Splitting.” Combinatorics Probability
and Computing, vol. 34, no. 4, Cambridge University Press, 2025, pp. 559–64,
doi:10.1017/S0963548325000045.
short: M. Christoph, K.H. Petrova, R. Steiner, Combinatorics Probability and Computing
34 (2025) 559–564.
date_created: 2025-04-06T22:01:32Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2025-09-30T11:26:00Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/S0963548325000045
ec_funded: 1
external_id:
arxiv:
- '2310.08449'
isi:
- '001449245700001'
file:
- access_level: open_access
checksum: 98491e59b4f0d05d69f608bbd5706f1a
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T12:54:06Z
date_updated: 2025-08-05T12:54:06Z
file_id: '20135'
file_name: 2025_CombProbComputing_Christoph.pdf
file_size: 188818
relation: main_file
success: 1
file_date_updated: 2025-08-05T12:54:06Z
has_accepted_license: '1'
intvolume: ' 34'
isi: 1
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 559-564
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
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: A note on digraph splitting
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 34
year: '2025'
...
---
_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. Combinatorics, Probability and Computing. 2016;25(6):909-927.
doi:10.1017/s0963548316000079
apa: 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
chicago: 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.
ieee: 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.
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.” Combinatorics, Probability and Computing, vol. 25, no.
6, Cambridge University Press, 2016, pp. 909–27, doi:10.1017/s0963548316000079.
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'
...