---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '22752'
abstract:
- lang: eng
text: "In this note we outline a new and simple approach to proving central limit
theorems for various ‘global’ graph parameters that have robust ‘local’ approximations,
using the Efron–Stein inequality, which relies on a combinatorial analysis of
the stability of these approximations under resampling an edge. As an application,
we give short proofs of a central limit theorem for the order of the giant component
and of the \U0001D458\r\n-core for sparse random graphs."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) [10.55776/P36131 (Joshua Erde), 10.55776/I6502 (Mihyun Kang), 10.55776/ESP3863424
(Michael Anastos)] and by the Swiss National Science Foundation (SNSF) [P500-2_235474]
(Vincent Pfenninger). For open access purposes, the authors have applied a CC BY
public copyright license to any author accepted manuscript version arising from
this submission. The authors thank the reviewers for helpful comments on the paper,
and for bringing the particular form of Theorem 2.2 to our attention.
article_number: e70464
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: Joshua
full_name: Erde, Joshua
last_name: Erde
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Vincent
full_name: Pfenninger, Vincent
last_name: Pfenninger
citation:
ama: Anastos M, Erde J, Kang M, Pfenninger V. A short proof of a central limit theorem
for the order of the giant component and k-core. Bulletin of the London Mathematical
Society. 2026;58(8). doi:10.1112/blms.70464
apa: Anastos, M., Erde, J., Kang, M., & Pfenninger, V. (2026). A short proof
of a central limit theorem for the order of the giant component and k-core. Bulletin
of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.70464
chicago: Anastos, Michael, Joshua Erde, Mihyun Kang, and Vincent Pfenninger. “A
Short Proof of a Central Limit Theorem for the Order of the Giant Component and
K-Core.” Bulletin of the London Mathematical Society. Wiley, 2026. https://doi.org/10.1112/blms.70464.
ieee: M. Anastos, J. Erde, M. Kang, and V. Pfenninger, “A short proof of a central
limit theorem for the order of the giant component and k-core,” Bulletin of
the London Mathematical Society, vol. 58, no. 8. Wiley, 2026.
ista: Anastos M, Erde J, Kang M, Pfenninger V. 2026. A short proof of a central
limit theorem for the order of the giant component and k-core. Bulletin of the
London Mathematical Society. 58(8), e70464.
mla: Anastos, Michael, et al. “A Short Proof of a Central Limit Theorem for the
Order of the Giant Component and K-Core.” Bulletin of the London Mathematical
Society, vol. 58, no. 8, e70464, Wiley, 2026, doi:10.1112/blms.70464.
short: M. Anastos, J. Erde, M. Kang, V. Pfenninger, Bulletin of the London Mathematical
Society 58 (2026).
das_tickbox: '0'
date_created: 2026-08-23T22:01:47Z
date_published: 2026-08-01T00:00:00Z
date_updated: 2026-09-07T13:56:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/blms.70464
external_id:
arxiv:
- '2506.11651'
file:
- access_level: open_access
checksum: b4b21f05c3fc62fde243a5ddd46cef49
content_type: application/pdf
creator: dernst
date_created: 2026-09-07T13:53:26Z
date_updated: 2026-09-07T13:53:26Z
file_id: '22845'
file_name: 2026_BulletinLondonMathSoc_Anastos.pdf
file_size: 248641
relation: main_file
success: 1
file_date_updated: 2026-09-07T13:53:26Z
fulldoi: https://doi.org/10.1112/blms.70464
has_accepted_license: '1'
intvolume: ' 58'
issue: '8'
language:
- iso: eng
mathsc:
- 05C80
- 60F05
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- 1469-2120
issn:
- 0024-6093
publication_status: published
publisher: Wiley
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A short proof of a central limit theorem for the order of the giant component
and k-core
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: 58
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '23155'
abstract:
- lang: eng
text: "In this work we establish several monotonicity and decomposition results
in the framework of random regular graphs. Among other results, we\r\nshow that,
for a wide range of parameters d1 ≤ d2, there exists a coupling of\r\nG(n,d1)
and G(n,d2) satisfying that G(n,d1) ⊆ G(n,d2) with high probability, confirming
a conjecture of Gao, Isaev and McKay in a new regime.\r\nOur contributions include
new tools for analysing contiguity and total variation distance between random
regular graph models, a novel procedure for\r\ngenerating unions of random edge-disjoint
perfect matchings, and refined estimates of Gao’s bounds on the number of perfect
matchings in random regular graphs. In addition, we make progress towards another
conjecture of Isaev,\r\nMcKay, Southwell and Zhukovskii."
acknowledgement: "We are grateful to Béla Bollobás, to Matthew Kwan and to Fabio\r\nToninelli
for their helpful comments and suggestions, and to Nicholas Wormald for useful\r\nremarks
on a preliminary version of this work and pointing us towards the reference [29].\r\nThe
authors would also like to thank several anonymous referees for many useful suggestions,\r\nincluding
pointing out that Lemma 2.10 already appeared in [11].\r\nPart of this research
was done during a visit of the fourth author to IST Austria. We thank\r\nIST Austria
for its hospitality.\r\nFor open access purposes, the authors have applied a CC
BY public copyright license to\r\nany author accepted manuscript version arising
from this submission. L. Hollom was supported by the Internal Graduate Studentship
of Trinity College, Cambridge.\r\nL. Lichev was supported by the Austrian Science
Fund (FWF) grant No. 10.55776/ESP624.\r\nA. Mond was supported by UK Research and
Innovation grant MR/W007320/2. Wang was\r\nsupported by the ERC Starting Grant “RANDSTRUCT”
No. 101076777."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Lawrence
full_name: Hollom, Lawrence
last_name: Hollom
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Adva
full_name: Mond, Adva
last_name: Mond
- first_name: Julien
full_name: Portier, Julien
last_name: Portier
- first_name: Yiting
full_name: Wang, Yiting
id: 1917d194-076e-11ed-97cd-837255f88785
last_name: Wang
citation:
ama: Hollom L, Lichev L, Mond A, Portier J, Wang Y. Monotonicity and decompositions
of random regular graphs. Annals of Applied Probability. 2026;36(5):4716-4738.
doi:10.1214/26-AAP2345
apa: Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Monotonicity
and decompositions of random regular graphs. Annals of Applied Probability.
Institute of Mathematical Statistics. https://doi.org/10.1214/26-AAP2345
chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting
Wang. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of
Applied Probability. Institute of Mathematical Statistics, 2026. https://doi.org/10.1214/26-AAP2345.
ieee: L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Monotonicity and
decompositions of random regular graphs,” Annals of Applied Probability,
vol. 36, no. 5. Institute of Mathematical Statistics, pp. 4716–4738, 2026.
ista: Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Monotonicity and decompositions
of random regular graphs. Annals of Applied Probability. 36(5), 4716–4738.
mla: Hollom, Lawrence, et al. “Monotonicity and Decompositions of Random Regular
Graphs.” Annals of Applied Probability, vol. 36, no. 5, Institute of Mathematical
Statistics, 2026, pp. 4716–38, doi:10.1214/26-AAP2345.
short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Annals of Applied Probability
36 (2026) 4716–4738.
das_tickbox: '0'
date_created: 2026-10-18T22:01:52Z
date_published: 2026-10-01T00:00:00Z
date_updated: 2026-10-19T07:39:17Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
- _id: GradSch
doi: 10.1214/26-AAP2345
external_id:
arxiv:
- '2505.22875'
file:
- access_level: open_access
checksum: 46101e61d29cf40f0a204801d15a848f
content_type: application/pdf
creator: dernst
date_created: 2026-10-19T07:33:58Z
date_updated: 2026-10-19T07:33:58Z
file_id: '23165'
file_name: 2026_AnnalsAppliedProbability_Hollom.pdf
file_size: 320593
relation: main_file
success: 1
file_date_updated: 2026-10-19T07:33:58Z
fulldoi: https://doi.org/10.1214/26-AAP2345
has_accepted_license: '1'
intvolume: ' 36'
issue: '5'
keyword:
- Random regular graphs
- coupling
- contiguity
- total variation distance
- decomposition
language:
- iso: eng
mathsc:
- 05C80
month: '10'
oa: 1
oa_version: Published Version
page: 4716-4738
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
- _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8
grant_number: E624
name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS
publication: Annals of Applied Probability
publication_identifier:
eissn:
- 2168-8737
issn:
- 1050-5164
publication_status: published
publisher: Institute of Mathematical Statistics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Monotonicity and decompositions of random regular 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: 36
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22157'
abstract:
- lang: eng
text: "A graph \U0001D43A is said to be Ramsey for a tuple of graphs(\U0001D43B
1 , … , \U0001D43B\U0001D45F ) if every \U0001D45F-coloring of the edges of \U0001D43A
con-tains a monochromatic copy of \U0001D43B\U0001D456 in color \U0001D456, for
some \U0001D456.A fundamental question at the intersection of Ramseytheory and
the theory of random graphs is to deter-mine the threshold at which the binomial
randomgraph \U0001D43A\U0001D45B,\U0001D45D becomes asymptotically almost surely
Ram-sey for a fixed tuple (\U0001D43B 1 , … , \U0001D43B\U0001D45F ), and a famous
conjectureof Kohayakawa and Kreuter predicts this threshold.Earlier work of Mousset–Nenadov–Samotij,
Bowtell–Hancock–Hyde, and Kuperwasser–Samotij–Wigdersonhas reduced this probabilistic
problem to a determinis-tic graph decomposition conjecture. In this paper, weresolve
this deterministic problem, thus proving theKohayakawa–Kreuter conjecture. Along
the way, weprove a number of novel graph decomposition resultsthat may be of independent
interest."
article_number: e70013
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Micha
full_name: Christoph, Micha
last_name: Christoph
- first_name: Anders
full_name: Martinsson, Anders
last_name: Martinsson
- first_name: Raphael
full_name: Steiner, Raphael
last_name: Steiner
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Christoph M, Martinsson A, Steiner R, Wigderson Y. Resolution of the Kohayakawa–Kreuter
conjecture. Proceedings of the London Mathematical Society. 2025;130(1).
doi:10.1112/plms.70013
apa: Christoph, M., Martinsson, A., Steiner, R., & Wigderson, Y. (2025). Resolution
of the Kohayakawa–Kreuter conjecture. Proceedings of the London Mathematical
Society. Wiley. https://doi.org/10.1112/plms.70013
chicago: Christoph, Micha, Anders Martinsson, Raphael Steiner, and Yuval Wigderson.
“Resolution of the Kohayakawa–Kreuter Conjecture.” Proceedings of the London
Mathematical Society. Wiley, 2025. https://doi.org/10.1112/plms.70013.
ieee: M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson, “Resolution of
the Kohayakawa–Kreuter conjecture,” Proceedings of the London Mathematical
Society, vol. 130, no. 1. Wiley, 2025.
ista: Christoph M, Martinsson A, Steiner R, Wigderson Y. 2025. Resolution of the
Kohayakawa–Kreuter conjecture. Proceedings of the London Mathematical Society.
130(1), e70013.
mla: Christoph, Micha, et al. “Resolution of the Kohayakawa–Kreuter Conjecture.”
Proceedings of the London Mathematical Society, vol. 130, no. 1, e70013,
Wiley, 2025, doi:10.1112/plms.70013.
short: M. Christoph, A. Martinsson, R. Steiner, Y. Wigderson, Proceedings of the
London Mathematical Society 130 (2025).
date_created: 2026-06-29T10:50:35Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2026-07-08T10:24:21Z
day: '01'
ddc:
- '500'
doi: 10.1112/plms.70013
extern: '1'
external_id:
arxiv:
- '2402.03045'
fulldoi: https://doi.org/10.1112/plms.70013
intvolume: ' 130'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2402.03045
mathsc:
- 05C70
- 05D10
- 05C80
month: '01'
oa: 1
oa_version: Preprint
publication: Proceedings of the London Mathematical Society
publication_identifier:
eissn:
- 1460-244X
issn:
- 0024-6115
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resolution of the Kohayakawa–Kreuter conjecture
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: repository
OA_type: green
_id: '22168'
abstract:
- lang: eng
text: "Let us say that a graph G is Ramsey for a tuple (H1, ... , Hr) of graphs
if every r-colouring\r\nof the edges of G contains a monochromatic copy of Hi
in colour i, for some i ∈ [[r]].\r\nA famous conjecture of Kohayakawa and Kreuter,
extending seminal work of Rödl and\r\nRucinski, predicts the threshold at which
the binomial random graph ´ Gn,p becomes Ramsey\r\nfor (H1, ... , Hr) asymptotically
almost surely.\r\nIn this paper, we resolve the Kohayakawa–Kreuter conjecture
for almost all tuples of\r\ngraphs. Moreover, we reduce its validity to the truth
of a certain deterministic statement,\r\nwhich is a clear necessary condition
for the conjecture to hold. All of our results actually hold in greater generality,
when one replaces the graphs H1, ... , Hr by finite families\r\nH1, ... , Hr.
Additionally, we pose a natural (deterministic) graph-partitioning conjecture,\r\nwhich
we believe to be of independent interest, and whose resolution would imply the\r\nKohayakawa–Kreuter
conjecture."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: EDEN
full_name: KUPERWASSER, EDEN
last_name: KUPERWASSER
- first_name: WOJCIECH
full_name: SAMOTIJ, WOJCIECH
last_name: SAMOTIJ
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: KUPERWASSER E, SAMOTIJ W, Wigderson Y. On the Kohayakawa–Kreuter conjecture.
Mathematical Proceedings of the Cambridge Philosophical Society. 2025;178(3):293-320.
doi:10.1017/s0305004125000143
apa: KUPERWASSER, E., SAMOTIJ, W., & Wigderson, Y. (2025). On the Kohayakawa–Kreuter
conjecture. Mathematical Proceedings of the Cambridge Philosophical Society.
Cambridge University Press. https://doi.org/10.1017/s0305004125000143
chicago: KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter
Conjecture.” Mathematical Proceedings of the Cambridge Philosophical Society.
Cambridge University Press, 2025. https://doi.org/10.1017/s0305004125000143.
ieee: E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,”
Mathematical Proceedings of the Cambridge Philosophical Society, vol. 178,
no. 3. Cambridge University Press, pp. 293–320, 2025.
ista: KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture.
Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.
mla: KUPERWASSER, EDEN, et al. “On the Kohayakawa–Kreuter Conjecture.” Mathematical
Proceedings of the Cambridge Philosophical Society, vol. 178, no. 3, Cambridge
University Press, 2025, pp. 293–320, doi:10.1017/s0305004125000143.
short: E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the
Cambridge Philosophical Society 178 (2025) 293–320.
date_created: 2026-06-29T10:55:00Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2026-07-14T08:38:08Z
day: '28'
doi: 10.1017/s0305004125000143
extern: '1'
external_id:
arxiv:
- '2307.16611'
fulldoi: https://doi.org/10.1017/s0305004125000143
intvolume: ' 178'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2307.16611
mathsc:
- 05C80
- 05C55
- 05D10
month: '04'
oa: 1
oa_version: Preprint
page: 293-320
publication: Mathematical Proceedings of the Cambridge Philosophical Society
publication_identifier:
eissn:
- 1469-8064
issn:
- 0305-0041
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the Kohayakawa–Kreuter conjecture
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 178
year: '2025'
...