---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '21884'
abstract:
- lang: eng
text: "We show that a randomly perturbed digraph, where we start with a dense digraph
Dα and add a small number of random edges to it, will typically contain a fixed
orientation of a bounded-degree spanning tree. This answers a question posed by
Araujo, Balogh, Krueger, Piga and Treglown and generalizes the corresponding result
for randomly perturbed graphs by Krivelevich, Kwan and Sudakov. More specifically,
we prove that there exists a constant c=c(α,Δ) such that if \r\nT is an oriented
tree with maximum degree Δ and Dα is an n-vertex digraph with minimum semidegree
αn, then the graph obtained by adding cn uniformly random edges to Dα will contain
T with high probability."
acknowledgement: "We thank the anonymous referees for many helpful comments on an
earlier version of this\r\narticle. Kalina Petrova was supported by grant no. CRSII5
173721 of the Swiss National\r\nScience Foundation, and by the European Union’s
Horizon 2020 research and innovation\r\nprogramme under the Marie Sk lodowska-Curie
grant agreement No. 101034413"
article_number: P2.24
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Patryk
full_name: Morawski, Patryk
last_name: Morawski
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
citation:
ama: Morawski P, Petrova KH. Randomly perturbed digraphs also have bounded-degree
spanning trees. Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/13316
apa: Morawski, P., & Petrova, K. H. (2026). Randomly perturbed digraphs also
have bounded-degree spanning trees. Electronic Journal of Combinatorics.
Electronic Journal of Combinatorics. https://doi.org/10.37236/13316
chicago: Morawski, Patryk, and Kalina H Petrova. “Randomly Perturbed Digraphs Also
Have Bounded-Degree Spanning Trees.” Electronic Journal of Combinatorics.
Electronic Journal of Combinatorics, 2026. https://doi.org/10.37236/13316.
ieee: P. Morawski and K. H. Petrova, “Randomly perturbed digraphs also have bounded-degree
spanning trees,” Electronic Journal of Combinatorics, vol. 33, no. 2. Electronic
Journal of Combinatorics, 2026.
ista: Morawski P, Petrova KH. 2026. Randomly perturbed digraphs also have bounded-degree
spanning trees. Electronic Journal of Combinatorics. 33(2), P2.24.
mla: Morawski, Patryk, and Kalina H. Petrova. “Randomly Perturbed Digraphs Also
Have Bounded-Degree Spanning Trees.” Electronic Journal of Combinatorics,
vol. 33, no. 2, P2.24, Electronic Journal of Combinatorics, 2026, doi:10.37236/13316.
short: P. Morawski, K.H. Petrova, Electronic Journal of Combinatorics 33 (2026).
corr_author: '1'
date_created: 2026-05-17T22:02:11Z
date_published: 2026-05-08T00:00:00Z
date_updated: 2026-05-18T08:50:18Z
day: '08'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/13316
ec_funded: 1
external_id:
arxiv:
- '2306.14648'
file:
- access_level: open_access
checksum: 9e8402cb2e8870ba7ded9ae7b308201a
content_type: application/pdf
creator: dernst
date_created: 2026-05-18T08:46:26Z
date_updated: 2026-05-18T08:46:26Z
file_id: '21893'
file_name: 2026_ElectrJournCombinatorics_Morawski.pdf
file_size: 399969
relation: main_file
success: 1
file_date_updated: 2026-05-18T08:46:26Z
has_accepted_license: '1'
intvolume: ' 33'
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Randomly perturbed digraphs also have bounded-degree spanning trees
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20422'
abstract:
- lang: eng
text: "We show that if n is odd and p>=Clog n/n, then with high probability Hamilton
cycles in G(n,p) span its cycle space. More generally, we show this holds for
a class of graphs satisfying certain natural pseudorandom properties. The proof
is based on a novel idea of parity-switchers, which can be thought of as analogues
of absorbers in the context of cycle spaces. As another application of our method,
we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with
odd n vertices and minimum degree n/2+C for sufficiently large constant C, span
its cycle space.\r\n"
acknowledgement: 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. Image 1 Part of this research was conducted while the author was at
Department of Computer Science, ETH Zürich, Switzerland. This author was supported
by grant no. CRSII5 173721 of the Swiss National Science Foundation.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Micha
full_name: Christoph, Micha
last_name: Christoph
- first_name: Rajko
full_name: Nenadov, Rajko
last_name: Nenadov
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
citation:
ama: Christoph M, Nenadov R, Petrova KH. The Hamilton space of pseudorandom graphs.
Journal of Combinatorial Theory Series B. 2026;176:254-267. doi:10.1016/j.jctb.2025.09.002
apa: Christoph, M., Nenadov, R., & Petrova, K. H. (2026). The Hamilton space
of pseudorandom graphs. Journal of Combinatorial Theory Series B. Elsevier.
https://doi.org/10.1016/j.jctb.2025.09.002
chicago: Christoph, Micha, Rajko Nenadov, and Kalina H Petrova. “The Hamilton Space
of Pseudorandom Graphs.” Journal of Combinatorial Theory Series B. Elsevier,
2026. https://doi.org/10.1016/j.jctb.2025.09.002.
ieee: M. Christoph, R. Nenadov, and K. H. Petrova, “The Hamilton space of pseudorandom
graphs,” Journal of Combinatorial Theory Series B, vol. 176. Elsevier,
pp. 254–267, 2026.
ista: Christoph M, Nenadov R, Petrova KH. 2026. The Hamilton space of pseudorandom
graphs. Journal of Combinatorial Theory Series B. 176, 254–267.
mla: Christoph, Micha, et al. “The Hamilton Space of Pseudorandom Graphs.” Journal
of Combinatorial Theory Series B, vol. 176, Elsevier, 2026, pp. 254–67, doi:10.1016/j.jctb.2025.09.002.
short: M. Christoph, R. Nenadov, K.H. Petrova, Journal of Combinatorial Theory Series
B 176 (2026) 254–267.
corr_author: '1'
date_created: 2025-10-05T22:01:34Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-01-05T13:29:52Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.jctb.2025.09.002
ec_funded: 1
external_id:
arxiv:
- '2402.01447'
isi:
- '001585783400001'
file:
- access_level: open_access
checksum: 60676af4af4b3243ba187e7d65440d99
content_type: application/pdf
creator: dernst
date_created: 2026-01-05T13:29:34Z
date_updated: 2026-01-05T13:29:34Z
file_id: '20953'
file_name: 2026_JourCombTheoryB_Christoph.pdf
file_size: 688924
relation: main_file
success: 1
file_date_updated: 2026-01-05T13:29:34Z
has_accepted_license: '1'
intvolume: ' 176'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 254-267
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of Combinatorial Theory Series B
publication_identifier:
eissn:
- 1096-0902
issn:
- 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Hamilton space of pseudorandom graphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 176
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20482'
abstract:
- lang: eng
text: 'In his study of graph codes, Alon introduced the concept of the odd-Ramsey
number of a family of graphs H in Kn, defined as the minimum number of colours
needed to colour the edges of K so that every copy of a graph H E H intersects
some colour class in an odd number of edges. In this paper, we focus on complete
bipartite graphs. First, we completely resolve the problem when H is the family
of all spanning complete bipartite graphs on n vertices. We then focus on its
subfamilies, that is, {Kt,n-t : t E T} for a fixed set of integers T c [[n/2]].
We prove that the odd-Ramsey problem is equivalent to determining the maximum
dimension of a linear binary code avoiding codewords of given weights, and leverage
known results from coding theory to deduce asymptotically tight bounds in our
setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is,
non-spanning) complete bipartite subgraphs.'
acknowledgement: "The authors would like to thank Gilles Zémor for a helpful clarification
on [3], Deepak Bal and Patrick Bennett for bringing [25] to their attention, and
both referees for several helpful comments.\r\nS.B.: Most of this research was conducted
while the author was at the School of Mathematics, University of Birmingham, Birmingham,
United Kingdom. The research leading to these results was supported by EPSRC, United
Kingdom, grant no. EP/V048287/1 and by ERC Advanced Grants “GeoScape”, no. 882971
and “ERMiD”, no. 101054936. There are no additional data beyond that contained within
the main manuscript.\r\nS.D.: Research supported by Taiwan NSTC grants 111-2115-M-002-009-MY2
and 113-2628-M-002-008-MY4.\r\nK.P.: 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. Parts of this research was conducted
while K.P. was at the Department of Computer Science, ETH Zürich, Switzerland, supported
by Swiss National Science Foundation, Switzerland , grant no. CRSII5 173721."
article_number: '104235'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Simona
full_name: Boyadzhiyska, Simona
last_name: Boyadzhiyska
- first_name: Shagnik
full_name: Das, Shagnik
last_name: Das
- first_name: Thomas
full_name: Lesgourgues, Thomas
last_name: Lesgourgues
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
citation:
ama: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. Odd-Ramsey numbers of complete
bipartite graphs. European Journal of Combinatorics. 2026;131. doi:10.1016/j.ejc.2025.104235
apa: Boyadzhiyska, S., Das, S., Lesgourgues, T., & Petrova, K. H. (2026). Odd-Ramsey
numbers of complete bipartite graphs. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104235
chicago: Boyadzhiyska, Simona, Shagnik Das, Thomas Lesgourgues, and Kalina H Petrova.
“Odd-Ramsey Numbers of Complete Bipartite Graphs.” European Journal of Combinatorics.
Elsevier, 2026. https://doi.org/10.1016/j.ejc.2025.104235.
ieee: S. Boyadzhiyska, S. Das, T. Lesgourgues, and K. H. Petrova, “Odd-Ramsey numbers
of complete bipartite graphs,” European Journal of Combinatorics, vol.
131. Elsevier, 2026.
ista: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. 2026. Odd-Ramsey numbers
of complete bipartite graphs. European Journal of Combinatorics. 131, 104235.
mla: Boyadzhiyska, Simona, et al. “Odd-Ramsey Numbers of Complete Bipartite Graphs.”
European Journal of Combinatorics, vol. 131, 104235, Elsevier, 2026, doi:10.1016/j.ejc.2025.104235.
short: S. Boyadzhiyska, S. Das, T. Lesgourgues, K.H. Petrova, European Journal of
Combinatorics 131 (2026).
corr_author: '1'
date_created: 2025-10-16T13:14:34Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-01-05T13:34:48Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104235
ec_funded: 1
external_id:
arxiv:
- '2410.05887'
isi:
- '001573380700001'
file:
- access_level: open_access
checksum: 52883daa217398396cbf9b8ad9ddae92
content_type: application/pdf
creator: dernst
date_created: 2026-01-05T13:34:40Z
date_updated: 2026-01-05T13:34:40Z
file_id: '20954'
file_name: 2026_EuropJourCombinatorics_Boyadzhiyska.pdf
file_size: 563029
relation: main_file
success: 1
file_date_updated: 2026-01-05T13:34:40Z
has_accepted_license: '1'
intvolume: ' 131'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Odd-Ramsey numbers of complete bipartite graphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 131
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21159'
abstract:
- lang: eng
text: "One of the foundational theorems of extremal graph theory is Dirac’s theorem,
which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then
G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later
work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have
many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler
and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles
and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter
of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings
in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let
md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching
in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to
determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless
able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex
k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any
constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan
entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof
Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin."
acknowledgement: We would like to thank the referees for a number of helpful comments
and suggestions, which have substantially improved the paper. Open access funding
provided by Institute of Science and Technology (IST Austria).
article_number: '5'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- 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: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Yiting
full_name: Wang, Yiting
id: 1917d194-076e-11ed-97cd-837255f88785
last_name: Wang
orcid: 0000-0002-2856-767X
citation:
ama: Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs.
Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8
apa: Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings
in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8
chicago: Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting
Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature,
2026. https://doi.org/10.1007/s00493-025-00194-8.
ieee: M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in
Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.
ista: Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac
hypergraphs. Combinatorica. 46, 5.
mla: Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.”
Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.
short: M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
corr_author: '1'
date_created: 2026-02-08T23:02:49Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-02-16T09:55:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
- _id: MoHe
doi: 10.1007/s00493-025-00194-8
external_id:
arxiv:
- '2408.09589'
file:
- access_level: open_access
checksum: 47b0031d90b0e6b9a843f422a1486089
content_type: application/pdf
creator: dernst
date_created: 2026-02-16T09:52:38Z
date_updated: 2026-02-16T09:52:38Z
file_id: '21228'
file_name: 2026_Combinatorica_Kwan.pdf
file_size: 539646
relation: main_file
success: 1
file_date_updated: 2026-02-16T09:52:38Z
has_accepted_license: '1'
intvolume: ' 46'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting perfect matchings in Dirac hypergraphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21706'
abstract:
- lang: eng
text: "Consider a quadratic polynomial Q(ξ1, . . . , ξn) of independent Rademacher
random variables ξ1, . . . , ξn. To what extent can Q(ξ1, . . . , ξn) concentrate
on a single value? This quadratic version of the classical Littlewood–Offord problem
was popularised by Costello, Tao and Vu in their study of symmetric random matrices.
In this paper, we obtain an essentially optimal bound for this problem, as conjectured
by Nguyen and Vu. Specifically, if Q(ξ1, . . . , ξn) ‘robustly depends on at least
m of the ξi’ in the sense that there is no way to pin down the value of Q(ξ1,
. . . , ξn) by fixing values for fewer than m of the variables ξi, then we have
Pr[Q(ξ1, . . . , ξn) = 0] ≤ O(1/√m). This also implies a similar result in the
case where ξ1, . . . , ξn have arbitrary distributions. Our proof combines a number
of ideas that may be of independent interest, including an inductive decoupling
scheme that reduces quadratic anticoncentration problems\r\nto high-dimensional
linear anticoncentration problems. Also, one application of our main result is
the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related
to graph inducibility. "
acknowledgement: We would like to thank the anonymous referee for a number of helpful
comments and suggestions. Matthew Kwan was supported by ERC Starting Grant “RANDSTRUCT”
No. 101076777. Lisa Sauermann was supported in part by NSF Award DMS-2100157 and
a Sloan Research Fellowship, and in part by the DFG Heisenberg Program.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- 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: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
citation:
ama: Kwan MA, Sauermann L. Resolution of the quadratic Littlewood–Offord problem.
Compositio Mathematica. 2025;161(12):3089-3139. doi:10.1112/S0010437X25102789
apa: Kwan, M. A., & Sauermann, L. (2025). Resolution of the quadratic Littlewood–Offord
problem. Compositio Mathematica. Cambridge University Press. https://doi.org/10.1112/S0010437X25102789
chicago: Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord
Problem.” Compositio Mathematica. Cambridge University Press, 2025. https://doi.org/10.1112/S0010437X25102789.
ieee: M. A. Kwan and L. Sauermann, “Resolution of the quadratic Littlewood–Offord
problem,” Compositio Mathematica, vol. 161, no. 12. Cambridge University
Press, pp. 3089–3139, 2025.
ista: Kwan MA, Sauermann L. 2025. Resolution of the quadratic Littlewood–Offord
problem. Compositio Mathematica. 161(12), 3089–3139.
mla: Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord
Problem.” Compositio Mathematica, vol. 161, no. 12, Cambridge University
Press, 2025, pp. 3089–139, doi:10.1112/S0010437X25102789.
short: M.A. Kwan, L. Sauermann, Compositio Mathematica 161 (2025) 3089–3139.
corr_author: '1'
date_created: 2026-04-12T22:01:48Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2026-05-04T09:42:57Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/S0010437X25102789
external_id:
arxiv:
- '2312.13826'
file:
- access_level: open_access
checksum: bd3415bb435da9d0b39f6f9a18c61abb
content_type: application/pdf
creator: dernst
date_created: 2026-05-04T09:41:25Z
date_updated: 2026-05-04T09:41:25Z
file_id: '21787'
file_name: 2025_CompositioMath_Kwan.pdf
file_size: 858727
relation: main_file
success: 1
file_date_updated: 2026-05-04T09:41:25Z
has_accepted_license: '1'
intvolume: ' 161'
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 3089-3139
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Compositio Mathematica
publication_identifier:
eissn:
- 1570-5846
issn:
- 0010-437X
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resolution of the quadratic Littlewood–Offord problem
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 161
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19418'
abstract:
- lang: eng
text: The size-Ramsey number r^(H) of a graph H is the smallest number of edges
a (host) graph G can have, such that for any red/blue colouring of G, there is
a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that
if H is a graph on n vertices and maximum degree three, then r^(H)=O(n8/5), improving
upon the upper bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi.
In this paper we show that r^(H)≤n3/2+o(1). While the previously used host graphs
were vanilla binomial random graphs, we prove our result using a novel host graph
construction. Our bound hits a natural barrier of the existing methods.
acknowledgement: 'We would like to thank Rajko Nenadov and Miloš Trujić for helpful
comments and discussions, as well as the anonymous referees for their very useful
feedback, which improved the paper considerably. This research was supported by
SNSF Project 217926. Part of this research was conducted while Nemanja Draganić
was at ETH Zürich, Switzerland, and partially supported by SNSF Grant 200021_196965.
This project has received funding from the European Union''s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie Grant Agreement Number:
101034413. Part of this research was conducted while Kalina Petrova was at the Department
of Computer Science, ETH Zürich, Switzerland, supported by SNSF Grant CRSII5 173721.'
article_number: e70116
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nemanja
full_name: Draganić, Nemanja
last_name: Draganić
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
citation:
ama: Draganić N, Petrova KH. Size‐Ramsey numbers of graphs with maximum degree three.
Journal of the London Mathematical Society. 2025;111(3). doi:10.1112/jlms.70116
apa: Draganić, N., & Petrova, K. H. (2025). Size‐Ramsey numbers of graphs with
maximum degree three. Journal of the London Mathematical Society. Wiley.
https://doi.org/10.1112/jlms.70116
chicago: Draganić, Nemanja, and Kalina H Petrova. “Size‐Ramsey Numbers of Graphs
with Maximum Degree Three.” Journal of the London Mathematical Society.
Wiley, 2025. https://doi.org/10.1112/jlms.70116.
ieee: N. Draganić and K. H. Petrova, “Size‐Ramsey numbers of graphs with maximum
degree three,” Journal of the London Mathematical Society, vol. 111, no.
3. Wiley, 2025.
ista: Draganić N, Petrova KH. 2025. Size‐Ramsey numbers of graphs with maximum degree
three. Journal of the London Mathematical Society. 111(3), e70116.
mla: Draganić, Nemanja, and Kalina H. Petrova. “Size‐Ramsey Numbers of Graphs with
Maximum Degree Three.” Journal of the London Mathematical Society, vol.
111, no. 3, e70116, Wiley, 2025, doi:10.1112/jlms.70116.
short: N. Draganić, K.H. Petrova, Journal of the London Mathematical Society 111
(2025).
date_created: 2025-03-19T09:03:37Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-30T11:05:07Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/jlms.70116
ec_funded: 1
external_id:
arxiv:
- '2207.05048'
isi:
- '001450645400019'
file:
- access_level: open_access
checksum: d8e0a03286a44c4f672709e3c829206e
content_type: application/pdf
creator: dernst
date_created: 2025-03-20T09:46:20Z
date_updated: 2025-03-20T09:46:20Z
file_id: '19427'
file_name: 2025_JournLondonMath_Draganic.pdf
file_size: 625974
relation: main_file
success: 1
file_date_updated: 2025-03-20T09:46:20Z
has_accepted_license: '1'
intvolume: ' 111'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of the London Mathematical Society
publication_identifier:
eissn:
- 1469-7750
issn:
- 0024-6107
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Size‐Ramsey numbers of graphs with maximum degree three
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: 111
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '19433'
abstract:
- lang: eng
text: An ordered r-matching is an r-uniform hypergraph matching equipped with an
ordering on its vertices. These objects can be viewed as natural generalisations
of r-dimensional orders. The theory of ordered 2-matchings is well developed and
has connections and applications to extremal and enumerative combinatorics, probability
and geometry. On the other hand, in the case r≥3 much less is known, largely
due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński
made some first steps towards a general theory of ordered r-matchings, and in
this paper we substantially improve several of their results and introduce some
new directions of study. Many intriguing open questions remain.
acknowledgement: We would like to thank Timo Seppäläinen for some illuminating discussion
about random high-dimensional orders and for bringing our attention to [59]. We
would also like to thank the referees for helpful feedback. Michael Anastos is supported
by the European Union’s Horizon 2020 research and innovation programme under the
Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan is supported
by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union.
Zhihan Jin and Benny Sudakov are supported by SNSF grant 200021-228014.
article_number: e55
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Zhihan
full_name: Jin, Zhihan
last_name: Jin
- 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: Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic
results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 2025;13.
doi:10.1017/fms.2024.144
apa: Anastos, M., Jin, Z., Kwan, M. A., & Sudakov, B. (2025). Extremal, enumerative
and probabilistic results on ordered hypergraph matchings. Forum of Mathematics,
Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2024.144
chicago: Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal,
Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum
of Mathematics, Sigma. Cambridge University Press, 2025. https://doi.org/10.1017/fms.2024.144.
ieee: M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and
probabilistic results on ordered hypergraph matchings,” Forum of Mathematics,
Sigma, vol. 13. Cambridge University Press, 2025.
ista: Anastos M, Jin Z, Kwan MA, Sudakov B. 2025. Extremal, enumerative and probabilistic
results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 13, e55.
mla: Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on
Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma, vol. 13, e55,
Cambridge University Press, 2025, doi:10.1017/fms.2024.144.
short: M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13
(2025).
corr_author: '1'
date_created: 2025-03-20T12:59:14Z
date_published: 2025-03-14T00:00:00Z
date_updated: 2025-09-30T11:18:57Z
day: '14'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/fms.2024.144
ec_funded: 1
external_id:
arxiv:
- '2308.12268'
isi:
- '001444429200001'
file:
- access_level: open_access
checksum: f396270ad78c1ed67095c8e5a66fca26
content_type: application/pdf
creator: dernst
date_created: 2025-04-03T11:24:35Z
date_updated: 2025-04-03T11:24:35Z
file_id: '19468'
file_name: 2025_ForumMathSigma_Anastos.pdf
file_size: 630297
relation: main_file
success: 1
file_date_updated: 2025-04-03T11:24:35Z
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Forum of Mathematics, Sigma
publication_identifier:
issn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extremal, enumerative and probabilistic results on ordered hypergraph matchings
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: 13
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19440'
abstract:
- lang: eng
text: Let μ(G) denote the minimum number of edges whose addition to G results in
a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition
to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in
the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there
exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if
G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n.
Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on
μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random
graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability,
μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p)
and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial
time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability,
the algorithm returns a set of edges of size μ(G) whose addition to G results
in a pancyclic (and therefore also Hamiltonian) graph.
acknowledgement: The authors would like to express their thanks to the referees of
the article for their valuable input towards improving the presentation of our result.
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.
article_number: e21286
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Yahav
full_name: Alon, Yahav
last_name: Alon
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity
in random graphs. Random Structures and Algorithms. 2025;66(2). doi:10.1002/rsa.21286
apa: Alon, Y., & Anastos, M. (2025). The completion numbers of hamiltonicity
and pancyclicity in random graphs. Random Structures and Algorithms. Wiley.
https://doi.org/10.1002/rsa.21286
chicago: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
and Pancyclicity in Random Graphs.” Random Structures and Algorithms. Wiley,
2025. https://doi.org/10.1002/rsa.21286.
ieee: Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity
in random graphs,” Random Structures and Algorithms, vol. 66, no. 2. Wiley,
2025.
ista: Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity
in random graphs. Random Structures and Algorithms. 66(2), e21286.
mla: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
and Pancyclicity in Random Graphs.” Random Structures and Algorithms, vol.
66, no. 2, e21286, Wiley, 2025, doi:10.1002/rsa.21286.
short: Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025).
date_created: 2025-03-23T23:01:26Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-30T11:15:41Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1002/rsa.21286
ec_funded: 1
external_id:
arxiv:
- '2304.03710'
isi:
- '001420226800001'
file:
- access_level: open_access
checksum: 6067747e805fa356d560dc45f2a89918
content_type: application/pdf
creator: dernst
date_created: 2025-03-25T11:46:27Z
date_updated: 2025-03-25T11:46:27Z
file_id: '19459'
file_name: 2025_RandomStruc_Alon.pdf
file_size: 549236
relation: main_file
success: 1
file_date_updated: 2025-03-25T11:46:27Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Random Structures and Algorithms
publication_identifier:
eissn:
- 1098-2418
issn:
- 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The completion numbers of hamiltonicity and pancyclicity in random graphs
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 66
year: '2025'
...
---
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'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '19508'
abstract:
- lang: eng
text: We consider random two-player zero-sum dynamic games with perfect information
on a class of infinite directed graphs. Starting from a fixed vertex, the players
take turns to move a token along the edges of the graph. Every vertex is assigned
a payoff known in advance by both players. Every time the token visits a vertex,
Player 2 pays Player 1 the corresponding payoff. We consider a distribution over
such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic
directed graphs of bounded degree and sub-exponential expansion, we show that,
when the duration of the game tends to infinity, the value converges almost surely
to a constant at an exponential rate dominated in terms of the expansion. On the
other hand, for the infinite d-ary tree (that does not fall into the previous
class of graphs), we show convergence at a double-exponential rate.
acknowledgement: Open access funding provided by Institute of Science and Technology
(IST Austria). This work was supported by the French Agence Nationale de la Recherche
(ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002
(GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC
CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a
1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at
University of Chile in 2023, under the IRL program of CNRS. This work was supported
by Fondation CFM pour la Recherche. This paper has also been funded by the Agence
Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir
program).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Luc
full_name: Attia, Luc
last_name: Attia
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Dieter
full_name: Mitsche, Dieter
last_name: Mitsche
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Bruno
full_name: Ziliotto, Bruno
last_name: Ziliotto
citation:
ama: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum
dynamic games on infinite directed graphs. Dynamic Games and Applications.
2025;15:1517-1535. doi:10.1007/s13235-025-00636-4
apa: Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto,
B. (2025). Random zero-sum dynamic games on infinite directed graphs. Dynamic
Games and Applications. Springer Nature. https://doi.org/10.1007/s13235-025-00636-4
chicago: Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and
Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” Dynamic
Games and Applications. Springer Nature, 2025. https://doi.org/10.1007/s13235-025-00636-4.
ieee: L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random
zero-sum dynamic games on infinite directed graphs,” Dynamic Games and Applications,
vol. 15. Springer Nature, pp. 1517–1535, 2025.
ista: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random
zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications.
15, 1517–1535.
mla: Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.”
Dynamic Games and Applications, vol. 15, Springer Nature, 2025, pp. 1517–35,
doi:10.1007/s13235-025-00636-4.
short: L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic
Games and Applications 15 (2025) 1517–1535.
corr_author: '1'
date_created: 2025-04-06T22:01:32Z
date_published: 2025-11-01T00:00:00Z
date_updated: 2026-04-07T12:31:21Z
day: '01'
ddc:
- '000'
department:
- _id: MaKw
- _id: KrCh
doi: 10.1007/s13235-025-00636-4
ec_funded: 1
external_id:
isi:
- '001449708900001'
file:
- access_level: open_access
checksum: b3a1b7eef40c9ac2acf3fef563081694
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T08:13:04Z
date_updated: 2025-12-30T08:13:04Z
file_id: '20891'
file_name: 2025_DynGamesAppl_Attia.pdf
file_size: 570994
relation: main_file
success: 1
file_date_updated: 2025-12-30T08:13:04Z
has_accepted_license: '1'
intvolume: ' 15'
isi: 1
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1517-1535
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Dynamic Games and Applications
publication_identifier:
eissn:
- 2153-0793
issn:
- 2153-0785
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '20234'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Random zero-sum dynamic games on infinite directed graphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19554'
abstract:
- lang: eng
text: 'In 1981, Karp and Sipser proved a law of large numbers for the matching number
of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called
differential equation method for analysis of random graph processes. Strengthening
this classical result, and answering a question of Aronson, Frieze and Pittel,
we prove a central limit theorem in the same setting: the fluctuations in the
matching number of a sparse random graph are asymptotically Gaussian. Our new
contribution is to prove this central limit theorem in the subcritical and critical
regimes, according to a celebrated algorithmic phase transition first observed
by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem
has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation
of the differential equation method (comparing the so-called Karp–Sipser process
to a system of stochastic differential equations). Our proof builds on these methods,
and introduces new techniques to handle certain degeneracies present in the subcritical
and critical cases. Curiously, our new techniques lead to a non-constructive result:
we are able to characterise the fluctuations of the matching number around its
mean, despite these fluctuations being much smaller than the error terms in our
best estimates of the mean. We also prove a central limit theorem for the rank
of the adjacency matrix of a sparse random graph.'
acknowledgement: "We would like to thank Christina Goldschmidt and Eleonora Kreačić
for insightful discussions and clarifications about their work in the thesis [26].
Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Ashwin
Sah and Mehtaab Sawhney were supported by NSF Graduate Research Fellowship Program
DGE-2141064. Ashwin Sah was supported by the PD Soros Fellowship.\r\nOpen access
funding provided by Institute of Science and Technology Austria/KEMÖ."
article_number: e70101
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Margalit
full_name: Glasgow, Margalit
last_name: Glasgow
- 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: Ashwin
full_name: Sah, Ashwin
last_name: Sah
- first_name: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
citation:
ama: Glasgow M, Kwan MA, Sah A, Sawhney M. A central limit theorem for the matching
number of a sparse random graph. Journal of the London Mathematical Society.
2025;111(4). doi:10.1112/jlms.70101
apa: Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). A central limit
theorem for the matching number of a sparse random graph. Journal of the London
Mathematical Society. Wiley. https://doi.org/10.1112/jlms.70101
chicago: Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney.
“A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” Journal
of the London Mathematical Society. Wiley, 2025. https://doi.org/10.1112/jlms.70101.
ieee: M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “A central limit theorem for
the matching number of a sparse random graph,” Journal of the London Mathematical
Society, vol. 111, no. 4. Wiley, 2025.
ista: Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. A central limit theorem for the
matching number of a sparse random graph. Journal of the London Mathematical Society.
111(4), e70101.
mla: Glasgow, Margalit, et al. “A Central Limit Theorem for the Matching Number
of a Sparse Random Graph.” Journal of the London Mathematical Society,
vol. 111, no. 4, e70101, Wiley, 2025, doi:10.1112/jlms.70101.
short: M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the London Mathematical
Society 111 (2025).
corr_author: '1'
date_created: 2025-04-13T22:01:19Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-09-30T11:35:55Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/jlms.70101
external_id:
arxiv:
- '2402.05851'
isi:
- '001473087200024'
file:
- access_level: open_access
checksum: 69ce9feaf64e776b99f3afd1041b1b11
content_type: application/pdf
creator: dernst
date_created: 2025-04-15T13:18:43Z
date_updated: 2025-04-15T13:18:43Z
file_id: '19564'
file_name: 2025_JourLondMathSoc_Glasgow.pdf
file_size: 392208
relation: main_file
success: 1
file_date_updated: 2025-04-15T13:18:43Z
has_accepted_license: '1'
intvolume: ' 111'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Journal of the London Mathematical Society
publication_identifier:
eissn:
- 1469-7750
issn:
- 0024-6107
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A central limit theorem for the matching number of a sparse random graph
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 111
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19603'
abstract:
- lang: eng
text: "MaxCut is a classical NP-complete problem and a crucial building block in
many\r\ncombinatorial algorithms. The famousEdwards-Erdös bound states that any
connected\r\ngraph on n vertices with m edges contains a cut of size at least
m/2 + n−1/4 . Crowston,\r\nJones and Mnich [Algorithmica, 2015] showed that the
MaxCut problem on simple\r\nconnected graphs admits an FPT algorithm, where the
parameter k is the difference\r\nbetween the desired cut size c and the lower
bound given by the Edwards-Erdös\r\nbound. This was later improved by Etscheid
and Mnich [Algorithmica, 2017] to run\r\nin parameterized linear time, i.e., f
(k) · O(m). We improve upon this result in two\r\nways: Firstly, we extend the
algorithm to work also for multigraphs (alternatively,\r\ngraphs with positive
integer weights). Secondly, we change the parameter; instead of\r\nthe difference
to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík\r\nbound.
The Poljak-Turzík bound states that any weighted graph G has a cut of weight\r\nat
least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF
(G)\r\ndenotes the weight of its minimum spanning forest. In connected simple
graphs the\r\ntwo bounds are equivalent, but for multigraphs the Poljak-Turzík
bound can be larger\r\nand thus yield a smaller parameter k. Our algorithm also
runs in parameterized linear\r\ntime, i.e., f (k) · O(m + n)."
acknowledgement: "Kalina Petrova is supported by the Swiss National Science Foundation,
grant no. CRSII5 173721, and also receives funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413. Simon Weber is supported by the Swiss National Science Foundation
under project no. 204320.\r\nOpen access funding provided by Swiss Federal Institute
of Technology Zurich."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jonas
full_name: Lill, Jonas
last_name: Lill
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
- first_name: Simon
full_name: Weber, Simon
last_name: Weber
citation:
ama: Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. Algorithmica. 2025;87:983-1007. doi:10.1007/s00453-025-01306-y
apa: Lill, J., Petrova, K. H., & Weber, S. (2025). Linear-time MaxCut in multigraphs
parameterized above the Poljak-Turzík bound. Algorithmica. Springer Nature.
https://doi.org/10.1007/s00453-025-01306-y
chicago: Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in
Multigraphs Parameterized above the Poljak-Turzík Bound.” Algorithmica.
Springer Nature, 2025. https://doi.org/10.1007/s00453-025-01306-y.
ieee: J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound,” Algorithmica, vol. 87. Springer Nature,
pp. 983–1007, 2025.
ista: Lill J, Petrova KH, Weber S. 2025. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. Algorithmica. 87, 983–1007.
mla: Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above
the Poljak-Turzík Bound.” Algorithmica, vol. 87, Springer Nature, 2025,
pp. 983–1007, doi:10.1007/s00453-025-01306-y.
short: J. Lill, K.H. Petrova, S. Weber, Algorithmica 87 (2025) 983–1007.
date_created: 2025-04-20T22:01:28Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2026-01-05T13:46:08Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1007/s00453-025-01306-y
ec_funded: 1
external_id:
isi:
- '001463103800001'
file:
- access_level: open_access
checksum: eab3f1834b0ba347b05ae9897729c0ad
content_type: application/pdf
creator: dernst
date_created: 2026-01-05T13:45:57Z
date_updated: 2026-01-05T13:45:57Z
file_id: '20957'
file_name: 2025_Algorithmica_Lill.pdf
file_size: 448554
relation: main_file
success: 1
file_date_updated: 2026-01-05T13:45:57Z
has_accepted_license: '1'
intvolume: ' 87'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 983-1007
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18758'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19798'
abstract:
- lang: eng
text: In an n×n array filled with symbols, a transversal is a collection of entries
with distinct rows, columns and symbols. In this note we show that if no symbol
appears more than βn times, the array contains a transversal of size (1−β/4−o(1))n
. In particular, if the array is filled with n symbols, each appearing n times
(an equi- n square), we get transversals of size (3/4−o(1))n. Moreover, our
proof gives a deterministic algorithm with polynomial running time, that finds
these transversals.
acknowledgement: "We are very grateful to Matthew Kwan and Alp Müyesser with whom
we had many interesting discussions leading to the results of this note. We also
thank the anonymous reviewers for their suggestions improving the presentation of
this note.\r\n\r\nMA was supported by the Austrian Science Fund (FWF) [10.55776/ESP3863424]
and by the European Union's Horizon 2020 research and innovation programme under
the Marie Skłodowska-Curie grant—project number 101034413. PM was supported by the
European Union's Horizon Europe Marie Skłodowska-Curie grant RAND-COMB-DESIGN—project
number 101106032."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Patrick
full_name: Morris, Patrick
last_name: Morris
citation:
ama: Anastos M, Morris P. A note on finding large transversals efficiently. Journal
of Combinatorial Designs. 2025;33(9):338-342. doi:10.1002/jcd.21990
apa: Anastos, M., & Morris, P. (2025). A note on finding large transversals
efficiently. Journal of Combinatorial Designs. Wiley. https://doi.org/10.1002/jcd.21990
chicago: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
Efficiently.” Journal of Combinatorial Designs. Wiley, 2025. https://doi.org/10.1002/jcd.21990.
ieee: M. Anastos and P. Morris, “A note on finding large transversals efficiently,”
Journal of Combinatorial Designs, vol. 33, no. 9. Wiley, pp. 338–342, 2025.
ista: Anastos M, Morris P. 2025. A note on finding large transversals efficiently.
Journal of Combinatorial Designs. 33(9), 338–342.
mla: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
Efficiently.” Journal of Combinatorial Designs, vol. 33, no. 9, Wiley,
2025, pp. 338–42, doi:10.1002/jcd.21990.
short: M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 338–342.
date_created: 2025-06-08T22:01:23Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2025-12-30T08:37:37Z
day: '01'
department:
- _id: MaKw
doi: 10.1002/jcd.21990
ec_funded: 1
external_id:
arxiv:
- '2412.05891'
isi:
- '001495472300001'
intvolume: ' 33'
isi: 1
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.05891
month: '09'
oa: 1
oa_version: Preprint
page: 338-342
project:
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of Combinatorial Designs
publication_identifier:
eissn:
- 1520-6610
issn:
- 1063-8539
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on finding large transversals efficiently
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2025'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '19859'
abstract:
- lang: eng
text: "We consider a recently introduced model of color-avoiding percolation (abbreviated
CA-percolation) defined as follows. Every edge in a graph G is colored in some
of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and
v may be connected using any subset of k-1 colors. CA-connectivity defines an
equivalence relation on the vertex set of G whose classes are called CA-components.\r\nWe
study the component structure of a randomly colored Erdős–Rényi random graph of
constant average degree. We distinguish three regimes for the size of the largest
component: a supercritical regime, a so-called intermediate regime, and a subcritical
regime, in which the largest CA-component has respectively linear, logarithmic,
and bounded size. Interestingly, in the subcritical regime, the bound is deterministic
and given by the number of colors."
acknowledgement: "We thank Dieter Mitsche for enlightening discussions, Balázs Ráth
for a number of comments\r\nand corrections on a first version of this paper, and
an anonymous referee for several useful remarks."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Bruno
full_name: Schapira, Bruno
last_name: Schapira
citation:
ama: Lichev L, Schapira B. Color-avoiding percolation on the Erdős–Rényi random
graph. Annales Henri Lebesgue. 2025;8:35-65. doi:10.5802/ahl.228
apa: Lichev, L., & Schapira, B. (2025). Color-avoiding percolation on the Erdős–Rényi
random graph. Annales Henri Lebesgue. École normale supérieure de Rennes.
https://doi.org/10.5802/ahl.228
chicago: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the
Erdős–Rényi Random Graph.” Annales Henri Lebesgue. École normale supérieure
de Rennes, 2025. https://doi.org/10.5802/ahl.228.
ieee: L. Lichev and B. Schapira, “Color-avoiding percolation on the Erdős–Rényi
random graph,” Annales Henri Lebesgue, vol. 8. École normale supérieure
de Rennes, pp. 35–65, 2025.
ista: Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi
random graph. Annales Henri Lebesgue. 8, 35–65.
mla: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi
Random Graph.” Annales Henri Lebesgue, vol. 8, École normale supérieure
de Rennes, 2025, pp. 35–65, doi:10.5802/ahl.228.
short: L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.
corr_author: '1'
date_created: 2025-06-22T22:02:07Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-06-23T12:01:36Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5802/ahl.228
external_id:
arxiv:
- '2211.16086 '
file:
- access_level: open_access
checksum: cca22d171b7affa010d17f5e793b0045
content_type: application/pdf
creator: dernst
date_created: 2025-06-23T11:59:22Z
date_updated: 2025-06-23T11:59:22Z
file_id: '19875'
file_name: 2025_AnnalesHenriLebesgue_Lichev.pdf
file_size: 746588
relation: main_file
success: 1
file_date_updated: 2025-06-23T11:59:22Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 35-65
publication: Annales Henri Lebesgue
publication_identifier:
eissn:
- 2644-9463
publication_status: published
publisher: École normale supérieure de Rennes
quality_controlled: '1'
scopus_import: '1'
status: public
title: Color-avoiding percolation on the Erdős–Rényi random graph
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19879'
abstract:
- lang: eng
text: We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations,
i.e., plane graphs where all faces except possibly for the outer one have length
three, all vertices not incident with the outer face have even degree, and exactly
the vertices incident with the outer face are precolored. We give a necessary
topological condition for the precoloring to extend, and give a complete characterization
when the outer face has length at most five and when all vertices of the outer
face have odd degree and are colored using only three colors.
acknowledgement: Supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation. An extended abstract appeared in Proceedings of the
12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)
article_number: '104138'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Zdeněk
full_name: Dvořák, Zdeněk
last_name: Dvořák
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Michaela
full_name: Seifrtová, Michaela
last_name: Seifrtová
- first_name: Robert
full_name: Šámal, Robert
last_name: Šámal
citation:
ama: Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations.
European Journal of Combinatorics. 2025;127. doi:10.1016/j.ejc.2025.104138
apa: Dvořák, Z., Moore, B., Seifrtová, M., & Šámal, R. (2025). Precoloring extension
in planar near-Eulerian-triangulations. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104138
chicago: Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring
Extension in Planar Near-Eulerian-Triangulations.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104138.
ieee: Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in
planar near-Eulerian-triangulations,” European Journal of Combinatorics,
vol. 127. Elsevier, 2025.
ista: Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar
near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.
mla: Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.”
European Journal of Combinatorics, vol. 127, 104138, Elsevier, 2025, doi:10.1016/j.ejc.2025.104138.
short: Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics
127 (2025).
corr_author: '1'
date_created: 2025-06-23T13:54:46Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-09-30T13:42:59Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104138
external_id:
arxiv:
- '2312.13061'
isi:
- '001443061400001'
file:
- access_level: open_access
checksum: 8b3585df45b25091fba9bee9854b7d01
content_type: application/pdf
creator: dernst
date_created: 2025-06-24T06:33:30Z
date_updated: 2025-06-24T06:33:30Z
file_id: '19887'
file_name: 2025_EuropJournCombinatorics_Dvorak.pdf
file_size: 564203
relation: main_file
success: 1
file_date_updated: 2025-06-24T06:33:30Z
has_accepted_license: '1'
intvolume: ' 127'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precoloring extension in planar near-Eulerian-triangulations
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: 127
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20007'
abstract:
- lang: eng
text: 'There is no known polynomial-time algorithm for graph isomorphism testing,
but elementary combinatorial “refinement” algorithms seem to be very efficient
in practice. Some philosophical justification for this phenomenon is provided
by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
assigns labels to vertices in a way that easily permits isomorphism-testing against
any other graph.'
acknowledgement: All authors were supported by ERC Starting Grant “RANDSTRUCT” No.
101076777. Michael Anastos was also supported in part by the Austrian Science Fund
(FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.
For Open Access purposes, the authors have applied a CC BY public copyright license
to any author accepted manuscript version arising from this submission.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- 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: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: 'Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In:
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association
for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173'
apa: 'Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph
isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing
(pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173'
chicago: Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis
for Graph Isomorphism.” In Proceedings of the 57th Annual ACM Symposium on
Theory of Computing, 2098–2106. Association for Computing Machinery, 2025.
https://doi.org/10.1145/3717823.3718173.
ieee: M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,”
in Proceedings of the 57th Annual ACM Symposium on Theory of Computing,
Prague, Czechia, 2025, pp. 2098–2106.
ista: 'Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on Theory of Computing, 2098–2106.'
mla: Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.
short: M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp.
2098–2106.
conference:
end_date: 2025-06-27
location: Prague, Czechia
name: 'STOC: Symposium on Theory of Computing'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2025-07-14T06:33:50Z
day: '15'
ddc:
- '000'
department:
- _id: MaKw
doi: 10.1145/3717823.3718173
ec_funded: 1
external_id:
arxiv:
- '2410.06095'
file:
- access_level: open_access
checksum: cf0ab9cb9c6abda188de13dc3f9a4c9b
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T06:13:10Z
date_updated: 2025-07-14T06:13:10Z
file_id: '20012'
file_name: 2025_STOC_Anastos.pdf
file_size: 706445
relation: main_file
success: 1
file_date_updated: 2025-07-14T06:13:10Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2098-2106
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400715105'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothed analysis for graph isomorphism
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20320'
abstract:
- lang: eng
text: "The pseudoforest version of the Strong Nine Dragon Tree Conjecture states
that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most
2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in
one pseudoforest F the components of F have at most d edges. This was proven in
2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that
we can find such a decomposition where additionally F is acyclic, the diameter
of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ +
1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N,
we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter
bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree
Conjecture for pseudoforests and its original conjecture for forests. In fact,
they are still optimal even if we only enforce F to have any constant maximum
degree, instead of enforcing every component of F to have at most d edges."
acknowledgement: This work was completed while Benjamin Moore was a postdoc at Charles
University, supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation, Czechia.
article_number: '104214'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Sebastian
full_name: Mies, Sebastian
last_name: Mies
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Evelyne
full_name: Smith-Roberge, Evelyne
last_name: Smith-Roberge
citation:
ama: Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon
Tree theorem. European Journal of Combinatorics. 2025;130(12). doi:10.1016/j.ejc.2025.104214
apa: Mies, S., Moore, B., & Smith-Roberge, E. (2025). Beyond the pseudoforest
strong Nine Dragon Tree theorem. European Journal of Combinatorics. Elsevier.
https://doi.org/10.1016/j.ejc.2025.104214
chicago: Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the
Pseudoforest Strong Nine Dragon Tree Theorem.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104214.
ieee: S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine
Dragon Tree theorem,” European Journal of Combinatorics, vol. 130, no.
12. Elsevier, 2025.
ista: Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine
Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.
mla: Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.”
European Journal of Combinatorics, vol. 130, no. 12, 104214, Elsevier,
2025, doi:10.1016/j.ejc.2025.104214.
short: S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130
(2025).
corr_author: '1'
date_created: 2025-09-10T05:36:50Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2025-12-30T10:19:10Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104214
external_id:
arxiv:
- '2310.00931'
isi:
- '001529769300002'
file:
- access_level: open_access
checksum: b1536e9256c4510a0e21452032e43a26
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T10:18:56Z
date_updated: 2025-12-30T10:18:56Z
file_id: '20913'
file_name: 2025_EuropJournCombinatorics_Mies.pdf
file_size: 737845
relation: main_file
success: 1
file_date_updated: 2025-12-30T10:18:56Z
has_accepted_license: '1'
intvolume: ' 130'
isi: 1
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Beyond the pseudoforest strong Nine Dragon Tree theorem
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 130
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18157'
abstract:
- lang: eng
text: "Interest in sliding block puzzles dates back to the 15-puzzle, seemingly
invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating
history of the puzzle). The game consists of fifteen movable square blocks numbered
\r\n and arranged within a \r\n square box, leaving one empty space (see Figure
1). The task at hand is to start from a given configuration of the numbered blocks
and reach the desired target configuration, where the only allowed move is to
slide a numbered block into an adjacent empty space. This task seemed to be unpredictably
either very easy to accomplish, or completely impossible, and the puzzle turned
into a worldwide sensation in the spring of 1880. A particularly challenging instance,
known as the 13-15-14 puzzle, consisted of initial and target configurations that
differed by a single swap (historically this swap involved the blocks labeled
14 and 15). The craze of this puzzle was such that it consistently made newspaper
headlines in 1880, with an article in the New York Times lamenting that it was
“threatening our free institutions” [23, p. 9]. Various prizes were offered for
anyone who could solve this challenge, beginning with a $25 set of teeth and culminating
with Sam Loyd’s famous $1,000 cash prize."
acknowledgement: Open access funding provided by Copenhagen University.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Florestan R
full_name: Brunck, Florestan R
id: 6ab6e556-f394-11eb-9cf6-9dfb78f00d8d
last_name: Brunck
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
citation:
ama: 'Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding
block puzzles. Mathematical Intelligencer. 2025;47:52-65. doi:10.1007/s00283-024-10358-x'
apa: 'Brunck, F. R., & Kwan, M. A. (2025). Books, Hallways, and social butterflies:
A note on sliding block puzzles. Mathematical Intelligencer. Springer Nature.
https://doi.org/10.1007/s00283-024-10358-x'
chicago: 'Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social
Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer.
Springer Nature, 2025. https://doi.org/10.1007/s00283-024-10358-x.'
ieee: 'F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A
note on sliding block puzzles,” Mathematical Intelligencer, vol. 47. Springer
Nature, pp. 52–65, 2025.'
ista: 'Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note
on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.'
mla: 'Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social
Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer,
vol. 47, Springer Nature, 2025, pp. 52–65, doi:10.1007/s00283-024-10358-x.'
short: F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.
date_created: 2024-09-29T22:01:38Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-05-19T14:00:09Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: MaKw
doi: 10.1007/s00283-024-10358-x
external_id:
arxiv:
- '2303.09459'
isi:
- '001318056000001'
file:
- access_level: open_access
checksum: c932ebe45c460d4a73f5b2dcca643db1
content_type: application/pdf
creator: dernst
date_created: 2025-04-08T11:17:45Z
date_updated: 2025-04-08T11:17:45Z
file_id: '19530'
file_name: 2025_MathIntelligencer_Brunck.pdf
file_size: 1760643
relation: main_file
success: 1
file_date_updated: 2025-04-08T11:17:45Z
has_accepted_license: '1'
intvolume: ' 47'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 52-65
publication: Mathematical Intelligencer
publication_identifier:
issn:
- 0343-6993
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Books, Hallways, and social butterflies: A note on sliding block puzzles'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18478'
abstract:
- lang: eng
text: For a given graph G=(V,E), we define its \emph{nth subdivision} as the graph
obtained from G by replacing every edge by a path of length n. We also define
the \emph{mth power} of G as the graph on vertex set V where we connect every
pair of vertices at distance at most m in G. In this paper, we study the chromatic
number of powers of subdivisions of graphs and resolve the case m=n asymptotically.
In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in
the case m=n=3 in a strong sense.
acknowledgement: "This work was initiated at the annual workshop of the Combinatorics
and Graph Theory group of Freie Universität Berlin in Wilhelmsaue in September 2023.
The authors would like to thank the institution for enabling this research. Finally,
the fourth author would like to thank Tibor Szabó and the Combinatorics and Graph
Theory group at Freie Universität Berlin for their hospitality during the research
visit. Additionally, we thank Moharram Iradmusa for bringing the papers [5], [7]
to our attention. Finally, we thank the anonymous referees for their suggestions
on the manuscript, which have improved the quality of the document.\r\nM.A.: 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
.\r\nS.B.: The research leading to these results was supported by EPSRC, UK, grant
no. EP/V048287/1. There are no additional data beyond that contained within the
main manuscript.\r\nS.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics
Research Center MATH+ (EXC-2046/1, project ID: 390685689).\r\nJ.R. acknowledges
the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033,
Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of
Excellence in R&D, Spain (CEX2020-001084-M)."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Simona
full_name: Boyadzhiyska, Simona
last_name: Boyadzhiyska
- first_name: Silas
full_name: Rathke, Silas
last_name: Rathke
- first_name: Juanjo
full_name: Rué, Juanjo
last_name: Rué
citation:
ama: Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers
of subdivisions of graphs. Discrete Applied Mathematics. 2025;360:506-511.
doi:10.1016/j.dam.2024.10.002
apa: Anastos, M., Boyadzhiyska, S., Rathke, S., & Rué, J. (2025). On the chromatic
number of powers of subdivisions of graphs. Discrete Applied Mathematics.
Elsevier. https://doi.org/10.1016/j.dam.2024.10.002
chicago: Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On
the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied
Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.dam.2024.10.002.
ieee: M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number
of powers of subdivisions of graphs,” Discrete Applied Mathematics, vol.
360. Elsevier, pp. 506–511, 2025.
ista: Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2025. On the chromatic number
of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511.
mla: Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions
of Graphs.” Discrete Applied Mathematics, vol. 360, Elsevier, 2025, pp.
506–11, doi:10.1016/j.dam.2024.10.002.
short: M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics
360 (2025) 506–511.
corr_author: '1'
date_created: 2024-10-27T23:01:44Z
date_published: 2025-01-15T00:00:00Z
date_updated: 2025-04-14T07:54:56Z
day: '15'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.dam.2024.10.002
ec_funded: 1
external_id:
arxiv:
- '2404.05542'
isi:
- '001343647000001'
file:
- access_level: open_access
checksum: bd20a13e56b3ea01daf5e7aca5247c60
content_type: application/pdf
creator: dernst
date_created: 2025-01-13T09:25:59Z
date_updated: 2025-01-13T09:25:59Z
file_id: '18836'
file_name: 2025_DiscreteApplMath_Anastos.pdf
file_size: 441060
relation: main_file
success: 1
file_date_updated: 2025-01-13T09:25:59Z
has_accepted_license: '1'
intvolume: ' 360'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 506-511
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the chromatic number of powers of subdivisions of graphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 360
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18753'
abstract:
- lang: eng
text: "We continue a line of research which studies which hereditary families of
digraphs have bounded dichromatic number. For a class of digraphs C, a hero in
\ C is any digraph H\r\n such that H -free digraphs in C have bounded dichromatic
number. We show that if F\r\n is an oriented star of degree at least five, the
only heroes for the class of F -free digraphs are transitive tournaments. For
oriented stars F of degree exactly four, we show the only heroes in F -free
digraphs are transitive tournaments, or possibly special joins of transitive tournaments.
Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs
almost completely, and we show the same characterization for the class of {H,rK1+P3→}
-free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of
brooms, then every transitive tournament is a hero for this class of digraphs."
acknowledgement: "We thank the anonymous referees for their careful proofreading which
helped improve the presentation of this paper. We also thank one of the anonymous
referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore
finished this project while a postdoctoral researcher at Charles University, and
was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the
Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777,
and appreciates the gracious support. We acknowledge the support of the Natural
Sciences and Engineering Research Council of Canada (NSERC), [funding reference
number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches
en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912].
This project was funded in part by the Government of Ontario ."
article_number: '104104'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Alvaro
full_name: Carbonero, Alvaro
last_name: Carbonero
- first_name: Hidde
full_name: Koerts, Hidde
last_name: Koerts
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Sophie
full_name: Spirkl, Sophie
last_name: Spirkl
citation:
ama: Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden
induced forests. European Journal of Combinatorics. 2025;125. doi:10.1016/j.ejc.2024.104104
apa: Carbonero, A., Koerts, H., Moore, B., & Spirkl, S. (2025). On heroes in
digraphs with forbidden induced forests. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2024.104104
chicago: Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On
Heroes in Digraphs with Forbidden Induced Forests.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2024.104104.
ieee: A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with
forbidden induced forests,” European Journal of Combinatorics, vol. 125.
Elsevier, 2025.
ista: Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with
forbidden induced forests. European Journal of Combinatorics. 125, 104104.
mla: Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.”
European Journal of Combinatorics, vol. 125, 104104, Elsevier, 2025, doi:10.1016/j.ejc.2024.104104.
short: A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics
125 (2025).
corr_author: '1'
date_created: 2025-01-05T23:01:55Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-05-19T14:06:00Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2024.104104
external_id:
arxiv:
- '2306.04710'
isi:
- '001400113700001'
file:
- access_level: open_access
checksum: 2c75f78f40ebb93d16fe3765bda2905a
content_type: application/pdf
creator: dernst
date_created: 2025-04-16T09:16:25Z
date_updated: 2025-04-16T09:16:25Z
file_id: '19577'
file_name: 2025_EuropJournCombinatorics_Carbonero.pdf
file_size: 1110657
relation: main_file
success: 1
file_date_updated: 2025-04-16T09:16:25Z
has_accepted_license: '1'
intvolume: ' 125'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On heroes in digraphs with forbidden induced forests
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 125
year: '2025'
...