@article{22152, abstract = {We study off-diagonal Ramsey numbers 𝑟⁡(𝐻,𝐾(𝑘) 𝑛) of 𝑘-uniform hypergraphs, where 𝐻 is a fixed linear 𝑘-uniform hypergraph and 𝐾(𝑘) 𝑛 is complete on 𝑛 vertices. Recently, Conlon, Fox, Gunby, He, Mubayi, Suk, and Verstraëte disproved the folklore conjecture that 𝑟⁡(𝐻,𝐾(3) 𝑛) always grows polynomially in 𝑛. In this paper, we show that much larger growth rates are possible in higher uniformity. In uniformity 𝑘 ≥4, we prove that for any constant 𝐶 >0, there exists a linear 𝑘-uniform hypergraph 𝐻 for which 𝑟⁡(𝐻,𝐾(𝑘) 𝑛)≥twr𝑘−2⁢(2(log⁡𝑛)𝐶).}, author = {He, Xiaoyu and Nie, Jiaxi and Wigderson, Yuval and Yu, Hung-Hsun}, issn = {1469-2163}, journal = {Combinatorics, Probability and Computing}, pages = {1--14}, publisher = {Cambridge University Press}, title = {{Off-diagonal Ramsey numbers for linear hypergraphs}}, doi = {10.1017/s0963548326100443}, year = {2026}, } @article{22167, abstract = {Given a vertex-ordered graph G, the ordered Ramsey number r<(G) is the minimum integer N such that every 2-coloring of the edges of the complete ordered graph KN contains a monochromatic ordered copy of G. Motivated by a similar question posed by Erd˝os and Graham [On partition theorems for finite graphs, Infinite and finite sets (Colloq., Keszthely, 1973), North-Holland, Amsterdam-London, pp. 515–527] in the unordered setting, we study the problem of bounding the ordered Ramsey number of any ordered graph G with m edges and no isolated vertices. We prove that r<(G) ≤ e109√m(log log m)3/2 for any such G, which is tight up to the (log log m)3/2 factor in the exponent. As a corollary, we obtain the corresponding bound for the oriented Ramsey number of a directed graph with m edges.}, author = {Bradač, Domagoj and Morawski, Patryk and Sudakov, Benny and Wigderson, Yuval}, issn = {1088-6826}, journal = {Proceedings of the American Mathematical Society}, number = {3}, pages = {927--942}, publisher = {American Mathematical Society}, title = {{Ordered Ramsey numbers of graphs with 𝑚 edges}}, doi = {10.1090/proc/17442}, volume = {154}, year = {2026}, } @article{22183, abstract = {A partition of a (hyper)graph is ε-homogeneous if the edge densities between almost all clusters are either at most ε or at least 1 − ε. Suppose a 3-graph has the property that the link of every vertex has an ε-homogeneous partition of size poly(1/ε). Does this guarantee that the 3-graph also has a small homogeneous partition? Terry and Wolf proved that such a 3-graph has an ε-homogeneous partition of size given by a wowzer-type function. Terry recently improved this to a double exponential bound, and conjectured that this bound is tight. Our first result in this paper disproves this conjecture by giving an improved (single) exponential bound, which is best possible. We further obtain an analogous result for k-graphs of all uniformities k 3. The above problem is part of a much broader programme, which seeks to understand the conditions under which a (hyper)graph has small ε-regular partitions. While this problem is fairly well understood for graphs, the situation is (as always) much more involved already for 3-graphs. For example, it is natural to ask if one can strengthen our first result by only requiring each link to have ε-regular partitions of size poly(1/ε). Our second result shows that surprisingly the answer is “no”, namely, a 3-graph might only have regular partitions of tower-type size, even though the link of every vertex has an ε-regular partition of polynomial size.}, author = {Gishboliner, Lior and Shapira, Asaf and Wigderson, Yuval}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {4}, publisher = {Oxford University Press}, title = {{Is it easy to regularize a hypergraph with easy links?}}, doi = {10.1093/imrn/rnag018}, volume = {2026}, year = {2026}, } @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{22155, abstract = {The canonical Ramsey theorem of Erdős and Rado implies that for any graph 𝐻, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph 𝐾𝑁 contains a monochromatic, lexicographic, or rainbow copy of 𝐻. The least such 𝑁 is called the Erdős–Rado number of 𝐻, denoted by 𝐸⁢𝑅⁡(𝐻). Erdős–Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős–Rado numbers of sparse graphs. For example, we prove that if 𝐻 has bounded degree, then 𝐸⁢𝑅⁡(𝐻) is polynomial in |𝑉⁡(𝐻)| if 𝐻 is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree S and given path 𝑃𝑡, we study the minimum 𝑁 such that every edge-coloring of 𝐾𝑁 contains a monochromatic copy of S or a rainbow copy of 𝑃𝑡. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type.}, author = {Gishboliner, Lior and Milojević, Aleksa and Sudakov, Benny and Wigderson, Yuval}, issn = {1095-7146}, journal = {SIAM Journal on Discrete Mathematics}, number = {3}, pages = {1491--1519}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Canonical Ramsey numbers of sparse graphs}}, doi = {10.1137/24m1714964}, volume = {39}, year = {2025}, } @article{22157, abstract = {A graph 𝐺 is said to be Ramsey for a tuple of graphs(𝐻 1 , … , 𝐻𝑟 ) if every 𝑟-coloring of the edges of 𝐺 con-tains a monochromatic copy of 𝐻𝑖 in color 𝑖, for some 𝑖.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 𝐺𝑛,𝑝 becomes asymptotically almost surely Ram-sey for a fixed tuple (𝐻 1 , … , 𝐻𝑟 ), 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.}, author = {Christoph, Micha and Martinsson, Anders and Steiner, Raphael and Wigderson, Yuval}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {1}, publisher = {Wiley}, title = {{Resolution of the Kohayakawa–Kreuter conjecture}}, doi = {10.1112/plms.70013}, volume = {130}, year = {2025}, } @article{22158, abstract = {The triangle removal states that if G contains edge-disjoint triangles, then G contains triangles. Unfortunately, there are no sensible bounds on the order of growth of , and at any rate, it is known that is not polynomial in . Csaba recently obtained an asymmetric variant of the triangle removal, stating that if G contains edge-disjoint triangles, then G contains copies of . To this end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following results: • We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of to the optimal number . • We say that H is -abundant if every graph containing edge-disjoint triangles has copies of H. It is easy to see that a -abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are -abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative. Our proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments.}, author = {Gishboliner, Lior and Shapira, Asaf and Wigderson, Yuval}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{An efficient asymmetric removal lemma and its limitations}}, doi = {10.1017/fms.2024.68}, volume = {13}, year = {2025}, } @article{22163, abstract = {For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal if its members are non-self-orthogonal and every k + 1 vectors of A include an orthogonal pair. We prove that for every prime p there exists some δ = δ(p)> 0, such that for every field F of characteristic p and for all integers k ≥ 2 and d ≥ k, there exists a k-nearly orthogonal set of at least dδ·k/ logk vectors of Fd. The size of the set is optimal up to the logk term in the exponent. We further prove two extensions of this result. In the first, we provide a large set A of non-self-orthogonal vectors of Fd such that for every two subsets of A of size k+1 each, some vector of one of the subsets is orthogonal to some vector of the other. In the second extension, every k + 1 vectors of the produced set A include ℓ + 1 pairwise orthogonal vectors for an arbitrary fixed integer 1 ≤ ℓ ≤ k. The proofs involve probabilistic and spectral arguments and the hypergraph container method}, author = {Haviv, Ishay and Mattheus, Sam and Milojević, Aleksa and Wigderson, Yuval}, issn = {0012-365X}, journal = {Discrete Mathematics}, keywords = {Nearly orthogonal sets, Ramsey theory, Finite fields}, number = {4}, publisher = {Elsevier}, title = {{Larger nearly orthogonal sets over finite fields}}, doi = {10.1016/j.disc.2024.114373}, volume = {348}, year = {2025}, } @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{22172, abstract = {A highly influential result of Nikiforov states that if an n-vertex graph G contains at least γnh copies of a fixed h-vertex graph H, then G contains a blowup of H of order Ωγ,H(logn). While the dependence on n is optimal, the correct dependence on γ is unknown; all known proofs yield bounds that are polynomial in γ, but the best known upper bound, coming from random graphs, is only logarithmic in γ. It is a major open problem to narrow this gap. We prove that if H is triangle-free, then the logarithmic behavior of the upper bound is the truth. That is, under the assumptions above, G contains a blowup of H of order ΩH(logn/log(1/γ)). This is the first non-trivial instance where the optimal dependence in Nikiforov’s theorem is known. As a consequence, we also prove an upper bound on multicolor Ramsey numbers of blowups of triangle-free graphs, proving that the dependence on the number of colors is polynomial once the blowup is sufficiently large. This shows that, from the perspective of multicolor Ramsey numbers, blowups of fixed triangle-free graphs behave like bipartite graphs.}, author = {Girão, António and Hunter, Zach and Wigderson, Yuval}, journal = {Advances in Combinatorics}, publisher = {Alliance of Diamond Open Access Journals}, title = {{Blowups of triangle-free graphs}}, doi = {10.19086/aic.2025.10}, volume = {10}, year = {2025}, } @article{22181, abstract = {A graph G is said to be Ramsey size-linear if r(G, H) = OG(e(H)) for every graph H with no isolated vertices. Erdős, Faudree, Rousseau, and Schelp observed that K4 is not Ramsey size-linear, but each of its proper subgraphs is, and they asked whether there exist infinitely many such graphs. In this short note, we answer this question in the affirmative}, author = {Wigderson, Yuval}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Infinitely many minimally non-Ramsey size-linear graphs}}, doi = {10.1016/j.ejc.2025.104175}, volume = {128}, year = {2025}, } @article{22188, abstract = {A fundamental fact about bounded-degree graph expanders is that three notions of expansion—vertex expansion, edge expansion, and spectral expansion—are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion. There are two well-studied notions of linear-algebraic expansion, namely, dimension expansion (defined in analogy to vertex expansion of graphs) and quantum expansion (defined in analogy to spectral expansion of graphs). Lubotzky and Zelmanov proved that the latter implies the former. We prove that the converse is false: There are dimension expanders which are not quantum expanders. This also answers in the negative questions of Lubotzky--Zelmanov and Dvir--Shpilka on the relation between dimension expansion and Kazhdan's property T. Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of edge expansion of graphs. The first of these is quantum edge expansion, which was introduced by Hastings, and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky--Zelmanov result that quantum expanders are dimension expanders.}, author = {Li, Yinan and Qiao, Youming and Wigderson, Avi and Wigderson, Yuval and Zhang, Chuanqi}, issn = {1557-2862}, journal = {Theory of Computing}, keywords = {linear algebraic expansion, quantum expanders, dimension expanders}, publisher = {Theory of Computing Exchange}, title = {{On linear-algebraic notions of expansion}}, doi = {10.4086/toc.2025.v021a001}, volume = {21}, year = {2025}, } @article{22154, abstract = {The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number a(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible. While there is a well‐established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n‐vertex graph for which even the unweighted ratio bound can prove a(G)<4n^3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan–Elphick–Abiad.}, author = {Kwan, Matthew and Wigderson, Yuval}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {10}, pages = {3196--3208}, publisher = {Wiley}, title = {{The inertia bound is far from tight}}, doi = {10.1112/blms.13127}, volume = {56}, year = {2024}, } @article{22179, abstract = {Burr and Erd˝os in 1975 conjectured, and Chv´atal, R¨odl, Szemer´edi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. In this paper, we disprove the natural directed analogue of the Burr–Erd˝os conjecture, answering a question of Buci´c, Letzter, and Sudakov. If H is an acyclic digraph, the oriented Ramsey number of H, denoted −→r1(H), is the least N such that every tournament on N vertices contains a copy of H. We show that for any Δ ≥ 2 and any sufficiently large n, there exists an acyclic digraph H with n vertices and maximum degree Δ such that −→r1(H) ≥ nΩ(Δ2/3/ log5/3 Δ). This proves that −→r1(H) is not always linear in the number of vertices for bounded-degree H. On the other hand, we show that −→r1(H) is nearly linear in the number of vertices for typical bounded-degree acyclic digraphs H, and obtain linear or nearly linear bounds for several natural families of bounded-degree acyclic digraphs. For multiple colors, we prove a quasi-polynomial upper bound −→rk(H)= 2(log n)Ok(1) for all bounded-degree acyclic digraphs H on n vertices, where −→rk(H) is the least N such that every k-edge-colored tournament on N vertices contains a monochromatic copy of H. For k ≥ 2 and n ≥ 4, we exhibit an acyclic digraph H with n vertices and maximum degree 3 such that −→rk(H) ≥ nΩ(log n/ log log n), showing that these Ramsey numbers can grow faster than any polynomial in the number of vertices.}, author = {Fox, Jacob and He, Xiaoyu and Wigderson, Yuval}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {1}, pages = {1--48}, publisher = {Springer Nature}, title = {{Ramsey numbers of sparse digraphs}}, doi = {10.1007/s11856-024-2624-y}, volume = {263}, year = {2024}, } @article{22180, abstract = {Given a graph , its Ramsey number is the minimum so that every two‐coloring of contains a monochromatic copy of . It was conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex from , the Ramsey number can change by at most a constant factor. We disprove this conjecture, exhibiting an infinite family of graphs such that deleting a single vertex from each decreases the Ramsey number by a super‐constant factor. One consequence of this result is the following. There exists a family of graphs so that in any Ramsey coloring for (i.e., a coloring of a clique on vertices with no monochromatic copy of ), one of the color classes has density .}, author = {Wigderson, Yuval}, issn = {1097-0118}, journal = {Journal of Graph Theory}, number = {3}, pages = {663--675}, publisher = {Wiley}, title = {{Ramsey numbers upon vertex deletion}}, doi = {10.1002/jgt.23093}, volume = {106}, year = {2024}, } @article{22162, abstract = {Given a bipartite graph G, the graphical matrix space SG consists of matrices whose non-zero entries can only be at those positions corresponding to edges in G. Tutte (J. London Math. Soc., 1947), Edmonds (J. Res. Nat. Bur. Standards Sect. B, 1967) and Lov´asz (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices in SG. Dieudonn´e (Arch. Math., 1948) proved a tight upper bound on the dimensions of those matrix spaces containing only singular matrices. The starting point of this paper is a simultaneous generalization of these two classical results: we show that the largest dimension over subspaces of SG containing only singular matrices is equal to the maximum size over subgraphs of G without perfect matchings, based on Meshulam’s proof of Dieudonn´e’s result (Quart. J. Math., 1985). Starting from this result, we go on to establish more connections between properties of graphs and matrix spaces. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. For each connection, we study three types of correspondences, namely the basic correspondence, the inherited correspondence (for subgraphs and subspaces), and the induced correspondence (for induced subgraphs and restrictions). Some correspondences lead to intriguing generalizations of classical results, such as Dieudonn´e’s result mentioned above, and a celebrated theorem of Gerstenhaber regarding the largest dimension of nil matrix spaces (Amer. J. Math., 1958). Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.}, author = {Li, Yinan and Qiao, Youming and Wigderson, Avi and Wigderson, Yuval and Zhang, Chuanqi}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {513--580}, publisher = {Springer Nature}, title = {{Connections between graphs and matrix spaces}}, doi = {10.1007/s11856-023-2515-7}, volume = {256}, year = {2023}, } @article{22159, abstract = {The size Ramsey number of a graph H is defined as the minimum number of edges in a graph G such that there is a monochromatic copy of H in every two-coloring of E(G). The size Ramsey number was introduced by Erdős, Faudree, Rousseau, and Schelp in 1978 and they ended their foundational paper by asking whether one can determine up to a constant factor the size Ramsey numbers of three families of graphs: complete bipartite graphs, book graphs (obtained by adding many common neighbors to the vertices of a clique), and starburst graphs (obtained by adding many pendant edges to each vertex of a clique). In this paper, we completely resolve the latter two questions and make substantial progress on the first by determining the size Ramsey number of Ks,t up to a constant factor for all t=Ω(s log s).}, author = {Conlon, David and Fox, Jacob and Wigderson, Yuval}, issn = {1439-6912}, journal = {Combinatorica}, number = {4}, pages = {743--768}, publisher = {Springer Nature}, title = {{Three early problems on size Ramsey numbers}}, doi = {10.1007/s00493-023-00034-7}, volume = {43}, year = {2023}, } @article{22164, abstract = {The clique removal lemma says that for every ≥r 3 andε > 0, there exists some δ > 0 so that every n‐vertex graph G with fewer than δnr copies of K r can be made K r ‐free by removing at most εn2 edges. The dependence of δ on ε in this result is notoriously difficult to determine: it is known that δ−1 must be at least super‐polynomial in ε−1, and that it is at most of tower type in εlog −1. We prove that if one imposes an appropriate minimum degree condition on G, then one can actually take δ to be a linear function of ε in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super‐polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.}, author = {Fox, Jacob and Wigderson, Yuval}, issn = {1097-0118}, journal = {Journal of Graph Theory}, keywords = {chromatic threshold, graph removal lemma, homomorphism threshold, minimum degree conditions}, number = {4}, pages = {648--665}, publisher = {Wiley}, title = {{Minimum degree and the graph removal lemma}}, doi = {10.1002/jgt.22891}, volume = {102}, year = {2023}, } @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{22170, abstract = {Extending an earlier conjecture of Erdős, Burr and Rosta conjectured that among all two-colorings of the edges of a complete graph, the uniformly random coloring asymptotically minimizes the number of monochromatic copies of any fixed graph H. This conjecture was disproved independently by Sidorenko and Thomason. The first author later found quantitatively stronger counterexamples, using the Turán coloring, in which one of the two colors spans a balanced complete multipartite graph. We prove that the Turán coloring is extremal for an infinite family of graphs, and that it is the unique extremal coloring. This yields the first determination of the Ramsey multiplicity constant of a graph for which the Burr--Rosta conjecture fails. We also prove an analogous three-color result. In this case, our result is conditional on a certain natural conjecture on the behavior of two-color Ramsey numbers.}, author = {Fox, Jacob and Wigderson, Yuval}, issn = {2517-5599}, journal = {Advances in Combinatorics}, publisher = {Alliance of Diamond Open Access Journals}, title = {{Ramsey multiplicity and the Turán coloring}}, doi = {10.19086/aic.2023.2}, year = {2023}, }