@article{22184, abstract = {Ramsey's theorem states that if N is sufficiently large, then no matter how one colors the edges among N vertices with two colors, there are always k 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! is sufficient, and five years later Erdős and Szekeres improved this bound to N=4^k . And then progress stalled for almost 90 years. In 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 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.}, author = {Wigderson, Yuval}, issn = {0303-1179}, journal = {Astérisque}, pages = {85--138}, publisher = {Societe Mathematique de France}, title = {{Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe)}}, doi = {10.24033/ast.1255}, year = {2026}, } @article{22168, abstract = {Let us say that a graph G is Ramsey for a tuple (H1, ... , Hr) of graphs if every r-colouring of the edges of G contains a monochromatic copy of Hi in colour i, for some i ∈ [[r]]. A famous conjecture of Kohayakawa and Kreuter, extending seminal work of Rödl and Rucinski, predicts the threshold at which the binomial random graph ´ Gn,p becomes Ramsey for (H1, ... , Hr) asymptotically almost surely. In this paper, we resolve the Kohayakawa–Kreuter conjecture for almost all tuples of graphs. Moreover, we reduce its validity to the truth of a certain deterministic statement, which 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 H1, ... , Hr. Additionally, we pose a natural (deterministic) graph-partitioning conjecture, which we believe to be of independent interest, and whose resolution would imply the Kohayakawa–Kreuter conjecture.}, author = {KUPERWASSER, EDEN and SAMOTIJ, WOJCIECH and Wigderson, Yuval}, issn = {1469-8064}, journal = {Mathematical Proceedings of the Cambridge Philosophical Society}, number = {3}, pages = {293--320}, publisher = {Cambridge University Press}, title = {{On the Kohayakawa–Kreuter conjecture}}, doi = {10.1017/s0305004125000143}, volume = {178}, year = {2025}, } @article{22165, abstract = {The book graph 𝐵(𝑘) 𝑛 consists of 𝑛 copies of 𝐾𝑘+1 joined along a common 𝐾𝑘. In the prequel to this paper, we studied the diagonal Ramsey number 𝑟⁡(𝐵(𝑘) 𝑛,𝐵(𝑘) 𝑛). Here we consider the natural off-diagonal variant 𝑟⁡(𝐵(𝑘) 𝑐⁢𝑛,𝐵(𝑘) 𝑛) for fixed 𝑐 ∈(0,1]. In this more general setting, we show that an interesting dichotomy emerges: for very small 𝑐, a simple 𝑘-partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being 𝑘-partite, while, for 𝑐 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 𝑐. }, author = {Conlon, David and Fox, Jacob and Wigderson, Yuval}, issn = {1469-2163}, journal = {Combinatorics, Probability and Computing}, keywords = {Ramsey theory, book graphs, Ramsey goodness}, number = {3}, pages = {516--545}, publisher = {Cambridge University Press}, title = {{Off-diagonal book Ramsey numbers}}, doi = {10.1017/s0963548322000360}, volume = {32}, year = {2023}, } @article{22161, abstract = {Recently, Souza introduced blowup Ramsey numbers as a gener- alization of bipartite Ramsey numbers. For graphs G and H, say G r −→ H if every r-edge-coloring of G contains a monochromatic copy of H. Let H[t] denote the t-blowup of H. Then the blowup Ramsey number of G, H, r, and t is defined as the minimum n such that G[n] r −→ H[t]. Souza proved upper and lower bounds on n that are exponential in t, and conjectured that the exponential constant does not depend on G. We prove that the dependence on G in the exponential constant is indeed unnecessary, but conjecture that some dependence on G is unavoidable. An important step in both Souza’s proof and ours is a theorem of Nikiforov, which says that if a graph contains a constant fraction of the possible copies of H, then it contains a blowup of H of logarithmic size. We also provide a new proof of this theorem with a better quantitative dependence.}, author = {Fox, Jacob and Luo, Sammy and Wigderson, Yuval}, issn = {2150-959X}, journal = {Journal of Combinatorics}, number = {1}, pages = {1--15}, publisher = {International Press of Boston}, title = {{Extremal and Ramsey results on graph blowups}}, doi = {10.4310/joc.2021.v12.n1.a1}, volume = {12}, year = {2021}, } @article{22185, abstract = {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