---
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'
...
---
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
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: '22147'
abstract:
- lang: eng
text: "Let 1 ≤ k ≤ n and M be a random n × n matrix with independent uniformly random
{±1}-entries. We\r\nshow that there exists an absolute constant c > 0 such that\r\nP[rank(M)
≤ n − k] ≤ exp(−cnk).\r\nThis confirms a well-known prediction in the area, extending
a result of Rudelson (who previously\r\nproved this same result under the restriction
k ≤ √n, via different methods)."
acknowledgement: "Z.H. was supported by SNSF grant 200021-228014. M.K. was supported
by ERC Starting Grant “RANDSTRUCT” No. 101076777. L.S. was supported by the Deutsche
Forschungsgemeinschaft (DFG, German\r\nResearch Foundation)—CRC 1720–539309657.
This research was conducted during the period M.S. served\r\nas a Clay Research
Fellow. This work began when the authors were visiting Mathematisches Forschungsinstitut
Oberwolfach, which\r\nprovided ideal working conditions. M.S. thanks Vishesh Jain
for initial discussions regarding the problem.\r\nWe also thank the anonymous referee
for helpful comments."
article_number: rnag126
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Zach
full_name: Hunter, Zach
last_name: Hunter
- 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
- first_name: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
citation:
ama: Hunter Z, Kwan MA, Sauermann L, Sawhney M. On random matrices with large corank.
International Mathematics Research Notices. 2026;2026(12). doi:10.1093/imrn/rnag126
apa: Hunter, Z., Kwan, M. A., Sauermann, L., & Sawhney, M. (2026). On random
matrices with large corank. International Mathematics Research Notices.
Oxford University Press. https://doi.org/10.1093/imrn/rnag126
chicago: Hunter, Zach, Matthew Alan Kwan, Lisa Sauermann, and Mehtaab Sawhney. “On
Random Matrices with Large Corank.” International Mathematics Research Notices.
Oxford University Press, 2026. https://doi.org/10.1093/imrn/rnag126.
ieee: Z. Hunter, M. A. Kwan, L. Sauermann, and M. Sawhney, “On random matrices with
large corank,” International Mathematics Research Notices, vol. 2026, no.
12. Oxford University Press, 2026.
ista: Hunter Z, Kwan MA, Sauermann L, Sawhney M. 2026. On random matrices with large
corank. International Mathematics Research Notices. 2026(12), rnag126.
mla: Hunter, Zach, et al. “On Random Matrices with Large Corank.” International
Mathematics Research Notices, vol. 2026, no. 12, rnag126, Oxford University
Press, 2026, doi:10.1093/imrn/rnag126.
short: Z. Hunter, M.A. Kwan, L. Sauermann, M. Sawhney, International Mathematics
Research Notices 2026 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-28T22:01:35Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-06-29T09:19:14Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1093/imrn/rnag126
external_id:
arxiv:
- '2510.12933'
file:
- access_level: open_access
checksum: 396b47d0532d7ea509f8cd30f11392a8
content_type: application/pdf
creator: dernst
date_created: 2026-06-29T09:15:15Z
date_updated: 2026-06-29T09:15:15Z
file_id: '22151'
file_name: 2026_IMRN_Hunter.pdf
file_size: 524993
relation: main_file
success: 1
file_date_updated: 2026-06-29T09:15:15Z
has_accepted_license: '1'
intvolume: ' 2026'
issue: '12'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: International Mathematics Research Notices
publication_identifier:
eissn:
- 1687-0247
issn:
- 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: On random matrices with large corank
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: 2026
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21211'
abstract:
- lang: eng
text: "We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such
that every nvertex d-regular graph with d ≥ d0 has a collection of vertex-disjoint
F-subdivisions covering\r\nat least (1 − η)n vertices. This verifies a conjecture
of Verstraëte from 2002 and improves a\r\nrecent result of Letzter, Methuku and
Sudakov which additionally required d to be at least\r\npolylogarithmic in n.\r\n"
acknowledgement: Supported by the European Research Council (ERC) under the European
Union Horizon 2020 research and innovation programme (grant agreement No. 947978).
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: '2508.00480'
article_processing_charge: No
arxiv: 1
author:
- first_name: Richard
full_name: Montgomery, Richard
last_name: Montgomery
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
- first_name: Arjun
full_name: Ranganathan, Arjun
last_name: Ranganathan
- first_name: Jane
full_name: Tan, Jane
last_name: Tan
citation:
ama: Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular
graphs. arXiv. doi:10.48550/arXiv.2508.00480
apa: Montgomery, R., Petrova, K. H., Ranganathan, A., & Tan, J. (n.d.). Packing
subdivisions into regular graphs. arXiv. https://doi.org/10.48550/arXiv.2508.00480
chicago: Montgomery, Richard, Kalina H Petrova, Arjun Ranganathan, and Jane Tan.
“Packing Subdivisions into Regular Graphs.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2508.00480.
ieee: R. Montgomery, K. H. Petrova, A. Ranganathan, and J. Tan, “Packing subdivisions
into regular graphs,” arXiv. .
ista: Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into
regular graphs. arXiv, 2508.00480.
mla: Montgomery, Richard, et al. “Packing Subdivisions into Regular Graphs.” ArXiv,
2508.00480, doi:10.48550/arXiv.2508.00480.
short: R. Montgomery, K.H. Petrova, A. Ranganathan, J. Tan, ArXiv (n.d.).
date_created: 2026-02-10T11:32:41Z
date_published: 2025-08-01T00:00:00Z
date_updated: 2026-02-10T11:39:16Z
day: '01'
department:
- _id: MaKw
doi: 10.48550/arXiv.2508.00480
ec_funded: 1
external_id:
arxiv:
- '2508.00480'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2508.00480
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: arXiv
publication_status: submitted
status: public
title: Packing subdivisions into regular graphs
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: diamond
PlanS_conform: '1'
_id: '21263'
abstract:
- lang: eng
text: Two landmark results in combinatorial random matrix theory, due to Komlós
and Costello–Tao–Vu, show that discrete random matrices and symmetric discrete
random matrices are typically nonsingular. In particular, in the language of graph
theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi
bipartite graph G(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph
G(n,p) are both nonsingular with high probability. However, very sparse random
graphs (i.e., where p is allowed to decay rapidly with n) are typically singular,
due to the presence of “local” dependencies such as isolated vertices and pairs
of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial
description of the rank of a sparse random graph G(n,n,c/n) or G(n,c/n) in terms
of such local dependencies, for all constants c=e (and we present some evidence
that the situation is very different for c=e). This gives an essentially complete
answer to a question raised by Vu (2014). As applications of our main theorem
and its proof, we also determine the asymptotic singularity probability of the
2-core of a sparse random graph, we show that the rank of a sparse random graph
is extremely well approximated by its matching number, and we deduce a central
limit theorem for the rank of G(n,c/n).
acknowledgement: "We would like to thank Noga Alon for suggesting that our main result
gives\r\na linear-time algorithm for computing the rank. We also thank the referees
for a number of thoughtful comments and suggestions. Glasgow was supported by NSF
graduate research fellowship program award DGE1656518. Kwan was supported by ERC
Starting Grant “RANDSTRUCT” No. 101076777. Sah and Sawhney were supported by NSF
Graduate Research Fellowship Program DGE-1745302.\r\n"
article_processing_charge: No
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. The exact rank of sparse random graphs.
Journal of the European Mathematical Society. 2025. doi:10.4171/jems/1692
apa: Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). The exact rank
of sparse random graphs. Journal of the European Mathematical Society.
European Mathematical Society Press. https://doi.org/10.4171/jems/1692
chicago: Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney.
“The Exact Rank of Sparse Random Graphs.” Journal of the European Mathematical
Society. European Mathematical Society Press, 2025. https://doi.org/10.4171/jems/1692.
ieee: M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “The exact rank of sparse
random graphs,” Journal of the European Mathematical Society. European
Mathematical Society Press, 2025.
ista: Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. The exact rank of sparse random
graphs. Journal of the European Mathematical Society.
mla: Glasgow, Margalit, et al. “The Exact Rank of Sparse Random Graphs.” Journal
of the European Mathematical Society, European Mathematical Society Press,
2025, doi:10.4171/jems/1692.
short: M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the European Mathematical
Society (2025).
corr_author: '1'
date_created: 2026-02-17T07:41:59Z
date_published: 2025-09-02T00:00:00Z
date_updated: 2026-02-23T10:44:41Z
day: '02'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.4171/jems/1692
external_id:
arxiv:
- '2303.05435'
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4171/JEMS/1692
month: '09'
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 European Mathematical Society
publication_identifier:
eissn:
- 1435-9863
issn:
- 1435-9855
publication_status: epub_ahead
publisher: European Mathematical Society Press
quality_controlled: '1'
status: public
title: The exact rank of sparse random 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
year: '2025'
...
---
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: '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'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19002'
abstract:
- lang: eng
text: "A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such
that the set of\r\nvertices coloured i induce a disjoint union of cliques. The
subchromatic number, χsub(G),\r\nis the minimum k such that G admits a k-subcolouring.
Nešetril, ˇ Ossona de Mendez,\r\nPilipczuk, and Zhu (2020), recently raised the
problem of finding tight upper bounds for\r\nχsub(G2) when G is planar. We show
that χsub(G2) ≤ 43 when G is planar, improving\r\ntheir bound of 135. We give
even better bounds when the planar graph G has larger girth.\r\nMoreover, we show
that χsub(G3) ≤ 95, improving the previous bound of 364. For these\r\nwe adapt
some recent techniques of Almulhim and Kierstead (2022), while also extending\r\nthe
decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez,\r\nQuiroz,
Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that
these\r\ndecompositions are the precursors of the graph product structure theorem
of planar graphs.\r\nWe give improved bounds for χsub(Gp) for all p ≥ 2, whenever
G has bounded treewidth,\r\nbounded simple treewidth, bounded genus, or excludes
a clique or biclique as a minor.\r\nFor this we introduce a family of parameters
which form a gradation between the strong\r\nand the weak colouring numbers. We
give upper bounds for these parameters for graphs\r\ncoming from such classes.\r\nFinally,
we give a 2-approximation algorithm for the subchromatic number of graphs\r\nhaving
a layering in which each layer has bounded cliquewidth and this layering is\r\ncomputable
in polynomial time (like the class of all dth powers of planar graphs, for fixed\r\nd).
This algorithm works even if the power p and the graph G is unknown."
acknowledgement: We thank an anonymous referee for pointing out an error in an earlier
version of Theorem 3.1. We also thank an anonymous referee for pointing out numerous
typos in an earlier version of the paper.
article_number: '114377'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Pedro P.
full_name: Cortés, Pedro P.
last_name: Cortés
- first_name: Pankaj
full_name: Kumar, Pankaj
last_name: Kumar
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Patrice
full_name: Ossona de Mendez, Patrice
last_name: Ossona de Mendez
- first_name: Daniel A.
full_name: Quiroz, Daniel A.
last_name: Quiroz
citation:
ama: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers
of powers of graphs with excluded minors. Discrete Mathematics. 2025;348(4).
doi:10.1016/j.disc.2024.114377
apa: Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., & Quiroz, D.
A. (2025). Subchromatic numbers of powers of graphs with excluded minors. Discrete
Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.114377
chicago: Cortés, Pedro P., Pankaj Kumar, Benjamin Moore, Patrice Ossona de Mendez,
and Daniel A. Quiroz. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.disc.2024.114377.
ieee: P. P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, and D. A. Quiroz, “Subchromatic
numbers of powers of graphs with excluded minors,” Discrete Mathematics,
vol. 348, no. 4. Elsevier, 2025.
ista: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. 2025. Subchromatic
numbers of powers of graphs with excluded minors. Discrete Mathematics. 348(4),
114377.
mla: Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics, vol. 348, no. 4, 114377, Elsevier, 2025,
doi:10.1016/j.disc.2024.114377.
short: P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete
Mathematics 348 (2025).
corr_author: '1'
date_created: 2025-02-05T06:51:08Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-09-30T10:25:15Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.114377
external_id:
arxiv:
- '2306.02195'
isi:
- '001401656900001'
file:
- access_level: open_access
checksum: 6723cbb02b6aea0d05f37d167da00c03
content_type: application/pdf
creator: dernst
date_created: 2025-05-05T12:56:12Z
date_updated: 2025-05-05T12:56:12Z
file_id: '19657'
file_name: 2025_DiscreteMath_Cortes.pdf
file_size: 850988
relation: main_file
success: 1
file_date_updated: 2025-05-05T12:56:12Z
has_accepted_license: '1'
intvolume: ' 348'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Subchromatic numbers of powers of graphs with excluded minors
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: 348
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19017'
abstract:
- lang: eng
text: "Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform
hypergraph containing no subgraph with k edges and at most s vertices. Brown,
Erdős and Sós [New directions in the theory of graphs (Proc. Third Ann Arbor Conf.,
Univ. Michigan 1971), pp. 53--63, Academic Press 1973] conjectured that the limit
limn→∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously
determined for k=2 in the original paper of Brown, Erdős and Sós, for k=3 by Glock
[Bull. Lond. Math. Soc. 51 (2019) 230--236] and for k=4 by Glock, Joos, Kim, Kühn,
Lichev and Pikhurko [arXiv:2209.14177, accepted by Proc. Amer. Math. Soc.] while
Delcourt and Postle [arXiv:2210.01105, accepted by Proc. Amer. Math. Soc.] proved
the conjecture (without determining the limiting value).\r\nIn this paper, we
determine the value of the limit in the Brown-Erdős-Sós Problem for k∈{5,6,7}.
More generally, we obtain the value of limn→∞n−2f(r)(n;rk−2k+2,k) for all r≥3
and k∈{5,6,7}. In addition, by combining these new values with recent results
of Bennett, Cushman and Dudek [arXiv:2309.00182] we obtain new asymptotic values
for several generalised Ramsey numbers."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Stefan
full_name: Glock, Stefan
last_name: Glock
- first_name: Jaehoon
full_name: Kim, Jaehoon
last_name: Kim
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Oleg
full_name: Pikhurko, Oleg
last_name: Pikhurko
- first_name: Shumin
full_name: Sun, Shumin
last_name: Sun
citation:
ama: Glock S, Kim J, Lichev L, Pikhurko O, Sun S. On the (k + 2, k)-problem of Brown,
Erdős, and Sós for k = 5,6,7. Canadian Journal of Mathematics. 2025:1-43.
doi:10.4153/s0008414x25000021
apa: Glock, S., Kim, J., Lichev, L., Pikhurko, O., & Sun, S. (2025). On the
(k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7. Canadian Journal
of Mathematics. Cambridge University Press. https://doi.org/10.4153/s0008414x25000021
chicago: Glock, Stefan, Jaehoon Kim, Lyuben Lichev, Oleg Pikhurko, and Shumin Sun.
“On the (k + 2, k)-Problem of Brown, Erdős, and Sós for k = 5,6,7.” Canadian
Journal of Mathematics. Cambridge University Press, 2025. https://doi.org/10.4153/s0008414x25000021.
ieee: S. Glock, J. Kim, L. Lichev, O. Pikhurko, and S. Sun, “On the (k + 2, k)-problem
of Brown, Erdős, and Sós for k = 5,6,7,” Canadian Journal of Mathematics.
Cambridge University Press, pp. 1–43, 2025.
ista: Glock S, Kim J, Lichev L, Pikhurko O, Sun S. 2025. On the (k + 2, k)-problem
of Brown, Erdős, and Sós for k = 5,6,7. Canadian Journal of Mathematics., 1–43.
mla: Glock, Stefan, et al. “On the (k + 2, k)-Problem of Brown, Erdős, and Sós for
k = 5,6,7.” Canadian Journal of Mathematics, Cambridge University Press,
2025, pp. 1–43, doi:10.4153/s0008414x25000021.
short: S. Glock, J. Kim, L. Lichev, O. Pikhurko, S. Sun, Canadian Journal of Mathematics
(2025) 1–43.
date_created: 2025-02-10T08:39:46Z
date_published: 2025-01-06T00:00:00Z
date_updated: 2025-09-30T10:28:07Z
day: '06'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.4153/s0008414x25000021
external_id:
arxiv:
- '2403.04474'
isi:
- '001416788600001'
has_accepted_license: '1'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4153/s0008414x25000021
month: '01'
oa: 1
oa_version: Published Version
page: 1-43
publication: Canadian Journal of Mathematics
publication_identifier:
eissn:
- 1496-4279
issn:
- 0008-414X
publication_status: epub_ahead
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7
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
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19018'
abstract:
- lang: eng
text: "The online semi-random graph process is a one-player game which starts with
the empty graph on n vertices. At every round, a player (called Builder) is presented
with a vertex v chosen uniformly at random and independently from previous rounds,
and constructs an edge of their choice that is incident to v. Inspired by recent
advances on the semi-random graph process, we define a family of generalized online
semi-random models.\r\nWe analyse a particular instance that shares similar features
with the original semi-random graph process and determine the hitting times of
the classical graph properties minimum degree k,k-connectivity, containment of
a perfect matching, a Hamiltonian cycle and an \r\nH-factor for a fixed graph
H possessing an additional tree-like property. Along the way, we derive a few
consequences of the famous Aldous-Broder algorithm that may be of independent
interest."
acknowledgement: We are grateful to Dieter Mitsche for related discussions and to
several anonymous referees for multiple useful comments.
article_number: '104120'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sofiya
full_name: Burova, Sofiya
last_name: Burova
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
citation:
ama: Burova S, Lichev L. The semi-random tree process. European Journal of Combinatorics.
2025;126. doi:10.1016/j.ejc.2025.104120
apa: Burova, S., & Lichev, L. (2025). The semi-random tree process. European
Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104120
chicago: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European
Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104120.
ieee: S. Burova and L. Lichev, “The semi-random tree process,” European Journal
of Combinatorics, vol. 126. Elsevier, 2025.
ista: Burova S, Lichev L. 2025. The semi-random tree process. European Journal of
Combinatorics. 126, 104120.
mla: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European
Journal of Combinatorics, vol. 126, 104120, Elsevier, 2025, doi:10.1016/j.ejc.2025.104120.
short: S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025).
date_created: 2025-02-10T09:00:53Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-09-30T10:28:42Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104120
external_id:
arxiv:
- '2204.07376 '
isi:
- '001420659400001'
intvolume: ' 126'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2204.07376
month: '05'
oa: 1
oa_version: Preprint
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The semi-random tree process
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 126
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
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'
...