---
OA_place: repository
OA_type: green
_id: '22184'
abstract:
- lang: eng
  text: "Ramsey's theorem states that if N\r\n is sufficiently large, then no matter
    how one colors the edges among N\r\n vertices with two colors, there are always
    k\r\n vertices spanning edges in only one color. Given this theorem, it is natural
    to ask \"how large is sufficiently large?\" Ramsey's original proof showed that
    N=k!\r\n is sufficient, and five years later Erdős and Szekeres improved this
    bound to N=4^k\r\n. And then progress stalled for almost 90 years.\r\n\r\nIn this
    survey, I present the history of the problem, and discuss some of the ideas used
    in the recent breakthrough of Campos–Griffiths–Morris–Sahasrabudhe, who proved
    that N=3.993^k\r\n is sufficient. In addition, I discuss the subsequent work of
    Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba,
    who gave an alternative, and more conceptual, proof."
- lang: fre
  text: "Le théorème de Ramsey stipule que si N\r\n est suffisamment grand, alors
    quelle que soit la manière dont l'on colore les arêtes entre N\r\n sommets avec
    deux couleurs, il y a toujours k\r\n sommets dont les arêtes ne sont colorées
    que d'une seule couleur. Compte tenu de ce théorème, il est naturel de se demander
    \"À quel point N\r\n doit être grand ?\" La preuve originale de Ramsey a montré
    que N=k!\r\n suffit, et cinq ans plus tard, Erdős et Szekeres ont amélioré cette
    borne à N=4k\r\n. Puis le progrès s'est arrêté pendant près de 90 ans.\r\n\r\nDans
    cet exposé, je présente l'histoire du problème et je discute certaines idées utilisées
    dans la percée récente de Campos--Griffiths-Morris--Sahasrabudhe, qui ont prouvé
    que N=3,993k\r\n suffit. De plus, je discute le travail suivant de Balister, Bollobás,
    Campos, Griffiths, Hurley, Morris, Sahasrabudhe, et Tiba, qui ont donné une preuve
    alternative et plus conceptuelle."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: 'Wigderson Y. Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers
    (after Campos, Griffiths, Morris, and Sahasrabudhe). <i>Astérisque</i>. 2026:85-138.
    doi:<a href="https://doi.org/10.24033/ast.1255">10.24033/ast.1255</a>'
  apa: 'Wigderson, Y. (2026). Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey
    numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). <i>Astérisque</i>.
    Societe Mathematique de France. <a href="https://doi.org/10.24033/ast.1255">https://doi.org/10.24033/ast.1255</a>'
  chicago: 'Wigderson, Yuval. “Exposé Bourbaki 1230 : Upper Bounds on Diagonal Ramsey
    Numbers (after Campos, Griffiths, Morris, and Sahasrabudhe).” <i>Astérisque</i>.
    Societe Mathematique de France, 2026. <a href="https://doi.org/10.24033/ast.1255">https://doi.org/10.24033/ast.1255</a>.'
  ieee: 'Y. Wigderson, “Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers
    (after Campos, Griffiths, Morris, and Sahasrabudhe),” <i>Astérisque</i>. Societe
    Mathematique de France, pp. 85–138, 2026.'
  ista: 'Wigderson Y. 2026. Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey
    numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). Astérisque., 85–138.'
  mla: 'Wigderson, Yuval. “Exposé Bourbaki 1230 : Upper Bounds on Diagonal Ramsey
    Numbers (after Campos, Griffiths, Morris, and Sahasrabudhe).” <i>Astérisque</i>,
    Societe Mathematique de France, 2026, pp. 85–138, doi:<a href="https://doi.org/10.24033/ast.1255">10.24033/ast.1255</a>.'
  short: Y. Wigderson, Astérisque (2026) 85–138.
date_created: 2026-06-29T12:02:59Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-07-14T09:53:07Z
day: '01'
doi: 10.24033/ast.1255
extern: '1'
external_id:
  arxiv:
  - '2411.09321'
fulldoi: https://doi.org/10.24033/ast.1255
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: 'https://doi.org/10.48550/arXiv.2411.09321 '
mathsc:
- 05D10
- 05C55
month: '01'
oa: 1
oa_version: Preprint
page: 85-138
publication: Astérisque
publication_identifier:
  issn:
  - 0303-1179
  - 2492-5926
publication_status: published
publisher: Societe Mathematique de France
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos,
  Griffiths, Morris, and Sahasrabudhe)'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
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.
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. 2025;178(3):293-320.
    doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>
  apa: KUPERWASSER, E., SAMOTIJ, W., &#38; Wigderson, Y. (2025). On the Kohayakawa–Kreuter
    conjecture. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>
  chicago: KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter
    Conjecture.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press, 2025. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>.
  ieee: E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,”
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, 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.” <i>Mathematical
    Proceedings of the Cambridge Philosophical Society</i>, vol. 178, no. 3, Cambridge
    University Press, 2025, pp. 293–320, doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>.
  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'
...
---
OA_place: repository
OA_type: green
_id: '22165'
abstract:
- lang: eng
  text: "The book graph \U0001D435(\U0001D458)\r\n\U0001D45B consists of \U0001D45B
    copies of \U0001D43E\U0001D458+1 joined along a common \U0001D43E\U0001D458. In
    the prequel to this paper, we studied the diagonal Ramsey number \U0001D45F⁡(\U0001D435(\U0001D458)\r\n\U0001D45B,\U0001D435(\U0001D458)\r\n\U0001D45B).
    Here we consider the natural off-diagonal variant \U0001D45F⁡(\U0001D435(\U0001D458)\r\n\U0001D450⁢\U0001D45B,\U0001D435(\U0001D458)\r\n\U0001D45B)
    for fixed \U0001D450 ∈(0,1]. In this more general setting, we show that an interesting
    dichotomy emerges: for very small \U0001D450, a simple \U0001D458-partite construction
    dictates the Ramsey function and all nearly-extremal colourings are close to being
    \U0001D458-partite, while, for \U0001D450 bounded away from 0, random colourings
    of an appropriate density are asymptotically optimal and all nearly-extremal colourings
    are quasirandom. Our investigations also open up a range of questions about what
    happens for intermediate values of \U0001D450.\r\n\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David
  full_name: Conlon, David
  last_name: Conlon
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Conlon D, Fox J, Wigderson Y. Off-diagonal book Ramsey numbers. <i>Combinatorics,
    Probability and Computing</i>. 2023;32(3):516-545. doi:<a href="https://doi.org/10.1017/s0963548322000360">10.1017/s0963548322000360</a>
  apa: Conlon, D., Fox, J., &#38; Wigderson, Y. (2023). Off-diagonal book Ramsey numbers.
    <i>Combinatorics, Probability and Computing</i>. Cambridge University Press. <a
    href="https://doi.org/10.1017/s0963548322000360">https://doi.org/10.1017/s0963548322000360</a>
  chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Off-Diagonal Book Ramsey
    Numbers.” <i>Combinatorics, Probability and Computing</i>. Cambridge University
    Press, 2023. <a href="https://doi.org/10.1017/s0963548322000360">https://doi.org/10.1017/s0963548322000360</a>.
  ieee: D. Conlon, J. Fox, and Y. Wigderson, “Off-diagonal book Ramsey numbers,” <i>Combinatorics,
    Probability and Computing</i>, vol. 32, no. 3. Cambridge University Press, pp.
    516–545, 2023.
  ista: Conlon D, Fox J, Wigderson Y. 2023. Off-diagonal book Ramsey numbers. Combinatorics,
    Probability and Computing. 32(3), 516–545.
  mla: Conlon, David, et al. “Off-Diagonal Book Ramsey Numbers.” <i>Combinatorics,
    Probability and Computing</i>, vol. 32, no. 3, Cambridge University Press, 2023,
    pp. 516–45, doi:<a href="https://doi.org/10.1017/s0963548322000360">10.1017/s0963548322000360</a>.
  short: D. Conlon, J. Fox, Y. Wigderson, Combinatorics, Probability and Computing
    32 (2023) 516–545.
date_created: 2026-06-29T10:53:47Z
date_published: 2023-05-01T00:00:00Z
date_updated: 2026-07-14T08:27:40Z
day: '01'
doi: 10.1017/s0963548322000360
extern: '1'
external_id:
  arxiv:
  - '2110.14483'
fulldoi: https://doi.org/10.1017/s0963548322000360
intvolume: '        32'
issue: '3'
keyword:
- Ramsey theory
- book graphs
- Ramsey goodness
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2110.14483
mathsc:
- 05C55
- 05D10
month: '05'
oa: 1
oa_version: Preprint
page: 516-545
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: Off-diagonal book Ramsey numbers
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22161'
abstract:
- lang: eng
  text: "Recently, Souza introduced blowup Ramsey numbers as a gener-\r\nalization
    of bipartite Ramsey numbers. For graphs G and H, say\r\nG r\r\n−→ H if every r-edge-coloring
    of G contains a monochromatic\r\ncopy of H. Let H[t] denote the t-blowup of H.
    Then the blowup\r\nRamsey number of G, H, r, and t is defined as the minimum n\r\nsuch
    that G[n] r\r\n−→ H[t]. Souza proved upper and lower bounds on\r\nn that are exponential
    in t, and conjectured that the exponential\r\nconstant does not depend on G. We
    prove that the dependence on\r\nG in the exponential constant is indeed unnecessary,
    but conjecture\r\nthat some dependence on G is unavoidable.\r\nAn important step
    in both Souza’s proof and ours is a theorem of\r\nNikiforov, which says that if
    a graph contains a constant fraction\r\nof the possible copies of H, then it contains
    a blowup of H of\r\nlogarithmic size. We also provide a new proof of this theorem
    with\r\na better quantitative dependence."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Sammy
  full_name: Luo, Sammy
  last_name: Luo
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, Luo S, Wigderson Y. Extremal and Ramsey results on graph blowups. <i>Journal
    of Combinatorics</i>. 2021;12(1):1-15. doi:<a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">10.4310/joc.2021.v12.n1.a1</a>
  apa: Fox, J., Luo, S., &#38; Wigderson, Y. (2021). Extremal and Ramsey results on
    graph blowups. <i>Journal of Combinatorics</i>. International Press of Boston.
    <a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>
  chicago: Fox, Jacob, Sammy Luo, and Yuval Wigderson. “Extremal and Ramsey Results
    on Graph Blowups.” <i>Journal of Combinatorics</i>. International Press of Boston,
    2021. <a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>.
  ieee: J. Fox, S. Luo, and Y. Wigderson, “Extremal and Ramsey results on graph blowups,”
    <i>Journal of Combinatorics</i>, vol. 12, no. 1. International Press of Boston,
    pp. 1–15, 2021.
  ista: Fox J, Luo S, Wigderson Y. 2021. Extremal and Ramsey results on graph blowups.
    Journal of Combinatorics. 12(1), 1–15.
  mla: Fox, Jacob, et al. “Extremal and Ramsey Results on Graph Blowups.” <i>Journal
    of Combinatorics</i>, vol. 12, no. 1, International Press of Boston, 2021, pp.
    1–15, doi:<a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">10.4310/joc.2021.v12.n1.a1</a>.
  short: J. Fox, S. Luo, Y. Wigderson, Journal of Combinatorics 12 (2021) 1–15.
date_created: 2026-06-29T10:52:13Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2026-07-08T10:41:31Z
day: '01'
doi: 10.4310/joc.2021.v12.n1.a1
extern: '1'
external_id:
  arxiv:
  - '1912.08328'
fulldoi: https://doi.org/10.4310/joc.2021.v12.n1.a1
intvolume: '        12'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1912.08328
mathsc:
- 05C35
- 05C55
month: '01'
oa: 1
oa_version: Preprint
page: 1-15
publication: Journal of Combinatorics
publication_identifier:
  eissn:
  - 2150-959X
  issn:
  - 2156-3527
publication_status: published
publisher: International Press of Boston
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extremal and Ramsey results on graph blowups
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2021'
...
---
OA_place: repository
OA_type: green
_id: '22185'
abstract:
- lang: eng
  text: "A weakly optimal Ks-free (n,d,λ)-graph is ad-regular Ks-free graph on n vertices
    with d= Θ(n1−α) and spectral expansion λ= Θ(n1−(s−1)α),  for some fixed α >0.
    \ Such a graph is called optimal if additionally α=12s−3.  We prove that if s1,...,sk>3
    are fixed positive integers and weakly optimal Ksi-free pseudorandom graphs exist
    for each 1<i<k, then the multicolor Ramsey numbers satisfy \r\n\r\nΩ(tS+1log2St)6r(s1,...,sk,t)6O(tS+1logSt),\r\nas
    t→∞, where S=∑ki=1(si−2). This generalizes previous results of Mubayi andVerstraete,
    who proved the case k= 1, and Alon and Rodl, who proved the cases1=···=sk= 3.
    \ Both previous results used the existence of optimal rather than weakly optimal
    Ksi-free graphs"
article_number: P1.32
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: He X, Wigderson Y. Multicolor Ramsey numbers via pseudorandom graphs. <i>The
    Electronic Journal of Combinatorics</i>. 2020;27(1). doi:<a href="https://doi.org/10.37236/9071">10.37236/9071</a>
  apa: He, X., &#38; Wigderson, Y. (2020). Multicolor Ramsey numbers via pseudorandom
    graphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal
    of Combinatorics. <a href="https://doi.org/10.37236/9071">https://doi.org/10.37236/9071</a>
  chicago: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
    Graphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal
    of Combinatorics, 2020. <a href="https://doi.org/10.37236/9071">https://doi.org/10.37236/9071</a>.
  ieee: X. He and Y. Wigderson, “Multicolor Ramsey numbers via pseudorandom graphs,”
    <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1. The Electronic
    Journal of Combinatorics, 2020.
  ista: He X, Wigderson Y. 2020. Multicolor Ramsey numbers via pseudorandom graphs.
    The Electronic Journal of Combinatorics. 27(1), P1.32.
  mla: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
    Graphs.” <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1, P1.32,
    The Electronic Journal of Combinatorics, 2020, doi:<a href="https://doi.org/10.37236/9071">10.37236/9071</a>.
  short: X. He, Y. Wigderson, The Electronic Journal of Combinatorics 27 (2020).
date_created: 2026-06-29T12:06:14Z
date_published: 2020-02-01T00:00:00Z
date_updated: 2026-07-14T09:42:53Z
day: '01'
doi: 10.37236/9071
extern: '1'
external_id:
  arxiv:
  - '1910.06287'
fulldoi: https://doi.org/10.37236/9071
intvolume: '        27'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1910.06287
mathsc:
- 05C55
- 05D10
month: '02'
oa: 1
oa_version: Preprint
publication: The Electronic Journal of Combinatorics
publication_identifier:
  eissn:
  - 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multicolor Ramsey numbers via pseudorandom graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2020'
...