@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{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{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{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{22160, abstract = {Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed and large with respect to , what is the minimum possible degree of a polynomial with such that has zeroes of multiplicity at least at all points in ? For , a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals . In this paper, we solve the problem for all , proving that the answer is . As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in such that each point in is covered by at least hyperplanes, but the point is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.}, author = {Sauermann, Lisa and Wigderson, Yuval}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {3}, pages = {2379--2402}, publisher = {Wiley}, title = {{Polynomials that vanish to high order on most of the hypercube}}, doi = {10.1112/jlms.12637}, volume = {106}, year = {2022}, } @article{22156, abstract = {Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant δ>0 such that for all c sufficiently large, there exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.}, author = {He, Xiaoyu and Wigderson, Yuval}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory, Series B}, keywords = {Graph coloring, Hedetniemi's conjecture}, pages = {485--494}, publisher = {Elsevier}, title = {{Hedetniemi's conjecture is asymptotically false}}, doi = {10.1016/j.jctb.2020.03.003}, volume = {146}, year = {2021}, } @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{22153, abstract = {A weakly optimal Ks-free (n,d,λ)-graph is a d-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 Ω(tS+1log2St)≤r(s1,…,sk,t)≤O(tS+1logSt), as t→∞, where S=∑ki=1(si−2). This generalizes previous results of Mubayi and Verstraëte, who proved the case k=1, and Alon and Rödl, who proved the case s1=⋯=sk=3. Both previous results used the existence of optimal rather than weakly optimal Ksi-free graphs.}, author = {He, Xiaoyu and Wigderson, Yuval}, issn = {1077-8926}, journal = {The Electronic Journal of Combinatorics}, number = {1}, publisher = {The Electronic Journal of Combinatorics}, title = {{Multicolor Ramsey numbers via pseudorandom graphs}}, doi = {10.37236/9071}, volume = {27}, year = {2020}, }