---
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
_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: 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
PlanS_conform: '1'
_id: '20504'
abstract:
- lang: eng
text: "Let r, k, be integers such that 0 ≤ ≤ (k/r). Given a large r-uniform hypergraph
G, we consider the\r\nfraction of k-vertex subsets that span exactly edges. If
\ is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete),
but for all other values of , one might suspect that this fraction is always significantly
smaller than 1.\r\nIn this paper we prove an essentially optimal result along
these lines: if is not 0 or (k/r), then this\r\nfraction is at most (1/e) + ε,
assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently
large in terms of k. Previously, this was only known for a very limited range
of values of r, k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic).
Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested
this as a hypergraph generalization of their edge-statistics conjecture. We also
prove a much stronger bound when is far from 0 and (k/r)."
acknowledgement: "This work was supported by NSF CAREER award DMS-2237646 [to V.J.],
ERC Starting Grant “RANDSTRUCT” [no. 101076777 to M.K.], NSF grant DMS-2153576 [to
D.M.], and the National Key Research and Development Program of China [2023YFA101020
to T.T.].\r\nWe would like to thank Lisa Sauermann for her helpful comments. We
would also like to thank Alex Grebennikov for identifying an oversight in the application
of Theorem 7.1 (in a previous version of this paper)."
article_number: rnaf273
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Vishesh
full_name: Jain, Vishesh
last_name: Jain
- 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: Dhruv
full_name: Mubayi, Dhruv
last_name: Mubayi
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
citation:
ama: Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs.
International Mathematics Research Notices. 2025;2025(18). doi:10.1093/imrn/rnaf273
apa: Jain, V., Kwan, M. A., Mubayi, D., & Tran, T. (2025). The edge-statistics
conjecture for hypergraphs. International Mathematics Research Notices.
Oxford University Press. https://doi.org/10.1093/imrn/rnaf273
chicago: Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics
Conjecture for Hypergraphs.” International Mathematics Research Notices.
Oxford University Press, 2025. https://doi.org/10.1093/imrn/rnaf273.
ieee: V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture
for hypergraphs,” International Mathematics Research Notices, vol. 2025,
no. 18. Oxford University Press, 2025.
ista: Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for
hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273.
mla: Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” International
Mathematics Research Notices, vol. 2025, no. 18, rnaf273, Oxford University
Press, 2025, doi:10.1093/imrn/rnaf273.
short: V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research
Notices 2025 (2025).
corr_author: '1'
date_created: 2025-10-20T11:08:57Z
date_published: 2025-09-11T00:00:00Z
date_updated: 2025-12-01T13:00:35Z
day: '11'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1093/imrn/rnaf273
external_id:
arxiv:
- '2505.03954'
isi:
- '001575137400001'
file:
- access_level: open_access
checksum: 016aa4df9453dc180ae7504ac77bf72f
content_type: application/pdf
creator: dernst
date_created: 2025-10-21T07:36:56Z
date_updated: 2025-10-21T07:36:56Z
file_id: '20511'
file_name: 2025_IMRN_Jain.pdf
file_size: 774323
relation: main_file
success: 1
file_date_updated: 2025-10-21T07:36:56Z
has_accepted_license: '1'
intvolume: ' 2025'
isi: 1
issue: '18'
language:
- iso: eng
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: International Mathematics Research Notices
publication_identifier:
eissn:
- 1687-0247
issn:
- 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: The edge-statistics conjecture for 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: 2025
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
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
_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'
...