[{"main_file_link":[{"url":"https://doi.org/10.1017/S0963548326100443","open_access":"1"}],"publisher":"Cambridge University Press","mathsc":["05D10","05D40","05C65"],"_id":"22152","type":"journal_article","doi":"10.1017/s0963548326100443","date_created":"2026-06-29T10:47:02Z","author":[{"first_name":"Xiaoyu","last_name":"He","full_name":"He, Xiaoyu"},{"first_name":"Jiaxi","last_name":"Nie","full_name":"Nie, Jiaxi"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson","first_name":"Yuval"},{"first_name":"Hung-Hsun","last_name":"Yu","full_name":"Yu, Hung-Hsun"}],"month":"04","extern":"1","day":"14","OA_place":"publisher","oa_version":"Published Version","external_id":{"arxiv":["2507.05641"]},"abstract":[{"text":"We study off-diagonal Ramsey numbers 𝑟⁡(đ»,đŸ(𝑘)\r\n𝑛) of 𝑘-uniform hypergraphs, where đ» is a fixed linear 𝑘-uniform hypergraph and đŸ(𝑘)\r\n𝑛 is complete on 𝑛 vertices. Recently, Conlon, Fox, Gunby, He, Mubayi, Suk, and VerstraĂ«te disproved the folklore conjecture that 𝑟⁡(đ»,đŸ(3)\r\n𝑛) 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\r\n\r\n𝑟⁡(đ»,đŸ(𝑘)\r\n𝑛)≄twr𝑘−2⁹(2(log⁡𝑛)đ¶).","lang":"eng"}],"publication_status":"epub_ahead","article_type":"original","date_published":"2026-04-14T00:00:00Z","oa":1,"year":"2026","arxiv":1,"OA_type":"hybrid","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"article_processing_charge":"No","date_updated":"2026-07-08T07:24:54Z","publication_identifier":{"eissn":["1469-2163"],"issn":["0963-5483"]},"title":"Off-diagonal Ramsey numbers for linear hypergraphs","ddc":["500"],"scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"citation":{"short":"X. He, J. Nie, Y. Wigderson, H.-H. Yu, Combinatorics, Probability and Computing (2026) 1–14.","chicago":"He, Xiaoyu, Jiaxi Nie, Yuval Wigderson, and Hung-Hsun Yu. “Off-Diagonal Ramsey Numbers for Linear Hypergraphs.” Combinatorics, Probability and Computing. Cambridge University Press, 2026. https://doi.org/10.1017/s0963548326100443.","ista":"He X, Nie J, Wigderson Y, Yu H-H. 2026. Off-diagonal Ramsey numbers for linear hypergraphs. Combinatorics, Probability and Computing., 1–14.","mla":"He, Xiaoyu, et al. “Off-Diagonal Ramsey Numbers for Linear Hypergraphs.” Combinatorics, Probability and Computing, Cambridge University Press, 2026, pp. 1–14, doi:10.1017/s0963548326100443.","apa":"He, X., Nie, J., Wigderson, Y., & Yu, H.-H. (2026). Off-diagonal Ramsey numbers for linear hypergraphs. Combinatorics, Probability and Computing. Cambridge University Press. https://doi.org/10.1017/s0963548326100443","ama":"He X, Nie J, Wigderson Y, Yu H-H. Off-diagonal Ramsey numbers for linear hypergraphs. Combinatorics, Probability and Computing. 2026:1-14. doi:10.1017/s0963548326100443","ieee":"X. He, J. Nie, Y. Wigderson, and H.-H. Yu, “Off-diagonal Ramsey numbers for linear hypergraphs,” Combinatorics, Probability and Computing. Cambridge University Press, pp. 1–14, 2026."},"page":"1-14","publication":"Combinatorics, Probability and Computing","status":"public"},{"issue":"3","status":"public","publication":"Proceedings of the American Mathematical Society","page":"927-942","citation":{"short":"D. Bradač, P. Morawski, B. Sudakov, Y. Wigderson, Proceedings of the American Mathematical Society 154 (2026) 927–942.","ista":"Bradač D, Morawski P, Sudakov B, Wigderson Y. 2026. Ordered Ramsey numbers of graphs with 𝑚 edges. Proceedings of the American Mathematical Society. 154(3), 927–942.","mla":"Bradač, Domagoj, et al. “Ordered Ramsey Numbers of Graphs with 𝑚 Edges.” Proceedings of the American Mathematical Society, vol. 154, no. 3, American Mathematical Society, 2026, pp. 927–42, doi:10.1090/proc/17442.","chicago":"Bradač, Domagoj, Patryk Morawski, Benny Sudakov, and Yuval Wigderson. “Ordered Ramsey Numbers of Graphs with 𝑚 Edges.” Proceedings of the American Mathematical Society. American Mathematical Society, 2026. https://doi.org/10.1090/proc/17442.","ieee":"D. Bradač, P. Morawski, B. Sudakov, and Y. Wigderson, “Ordered Ramsey numbers of graphs with 𝑚 edges,” Proceedings of the American Mathematical Society, vol. 154, no. 3. American Mathematical Society, pp. 927–942, 2026.","ama":"Bradač D, Morawski P, Sudakov B, Wigderson Y. Ordered Ramsey numbers of graphs with 𝑚 edges. Proceedings of the American Mathematical Society. 2026;154(3):927-942. doi:10.1090/proc/17442","apa":"Bradač, D., Morawski, P., Sudakov, B., & Wigderson, Y. (2026). Ordered Ramsey numbers of graphs with 𝑚 edges. Proceedings of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/proc/17442"},"scopus_import":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","OA_type":"green","title":"Ordered Ramsey numbers of graphs with 𝑚 edges","publication_identifier":{"issn":["0002-9939"],"eissn":["1088-6826"]},"date_updated":"2026-07-14T08:34:43Z","article_processing_charge":"No","external_id":{"arxiv":["2412.17599"]},"oa_version":"Preprint","OA_place":"repository","day":"16","month":"01","extern":"1","arxiv":1,"year":"2026","oa":1,"volume":154,"date_published":"2026-01-16T00:00:00Z","publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"Given a vertex-ordered graph G, the ordered Ramsey number\r\nr<(G) is the minimum integer N such that every 2-coloring of the edges of\r\nthe complete ordered graph KN contains a monochromatic ordered copy of G.\r\nMotivated by a similar question posed by Erd˝os and Graham [On partition\r\ntheorems for finite graphs, Infinite and finite sets (Colloq., Keszthely, 1973),\r\nNorth-Holland, Amsterdam-London, pp. 515–527] in the unordered setting,\r\nwe 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) ≀\r\ne109√m(log log m)3/2\r\nfor any such G, which is tight up to the (log log m)3/2\r\nfactor in the exponent. As a corollary, we obtain the corresponding bound for\r\nthe oriented Ramsey number of a directed graph with m edges."}],"_id":"22167","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.17599"}],"publisher":"American Mathematical Society","date_created":"2026-06-29T10:54:32Z","author":[{"full_name":"Bradač, Domagoj","last_name":"Bradač","first_name":"Domagoj"},{"full_name":"Morawski, Patryk","first_name":"Patryk","last_name":"Morawski"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"},{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","last_name":"Wigderson"}],"doi":"10.1090/proc/17442","type":"journal_article","intvolume":" 154"},{"_id":"22183","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2506.15582","open_access":"1"}],"publisher":"Oxford University Press","author":[{"first_name":"Lior","last_name":"Gishboliner","full_name":"Gishboliner, Lior"},{"full_name":"Shapira, Asaf","last_name":"Shapira","first_name":"Asaf"},{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T12:02:25Z","doi":"10.1093/imrn/rnag018","type":"journal_article","intvolume":" 2026","oa_version":"Preprint","external_id":{"arxiv":["2506.15582"]},"day":"01","OA_place":"repository","month":"02","extern":"1","arxiv":1,"volume":2026,"date_published":"2026-02-01T00:00:00Z","oa":1,"year":"2026","abstract":[{"lang":"eng","text":"A partition of a (hyper)graph is Δ-homogeneous if the edge densities between almost all clusters are\r\neither at most Δ or at least 1 − Δ. Suppose a 3-graph has the property that the link of every vertex has\r\nan Δ-homogeneous partition of size poly(1/Δ). Does this guarantee that the 3-graph also has a small\r\nhomogeneous partition? Terry and Wolf proved that such a 3-graph has an Δ-homogeneous partition\r\nof size given by a wowzer-type function. Terry recently improved this to a double exponential bound,\r\nand conjectured that this bound is tight. Our first result in this paper disproves this conjecture by\r\ngiving an improved (single) exponential bound, which is best possible. We further obtain an analogous\r\nresult for k-graphs of all uniformities k 3. The above problem is part of a much broader programme,\r\nwhich seeks to understand the conditions under which a (hyper)graph has small Δ-regular partitions.\r\nWhile this problem is fairly well understood for graphs, the situation is (as always) much more\r\ninvolved already for 3-graphs. For example, it is natural to ask if one can strengthen our first result\r\nby only requiring each link to have Δ-regular partitions of size poly(1/Δ). Our second result shows that\r\nsurprisingly the answer is “no”, namely, a 3-graph might only have regular partitions of tower-type size,\r\neven though the link of every vertex has an Δ-regular partition of polynomial size."}],"publication_status":"published","article_type":"original","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","OA_type":"green","title":"Is it easy to regularize a hypergraph with easy links?","date_updated":"2026-07-14T09:25:22Z","publication_identifier":{"eissn":["1687-0247"],"issn":["1073-7928"]},"article_processing_charge":"No","article_number":"rnag018","issue":"4","status":"public","citation":{"short":"L. Gishboliner, A. Shapira, Y. Wigderson, International Mathematics Research Notices 2026 (2026).","mla":"Gishboliner, Lior, et al. “Is It Easy to Regularize a Hypergraph with Easy Links?” International Mathematics Research Notices, vol. 2026, no. 4, rnag018, Oxford University Press, 2026, doi:10.1093/imrn/rnag018.","ista":"Gishboliner L, Shapira A, Wigderson Y. 2026. Is it easy to regularize a hypergraph with easy links? International Mathematics Research Notices. 2026(4), rnag018.","chicago":"Gishboliner, Lior, Asaf Shapira, and Yuval Wigderson. “Is It Easy to Regularize a Hypergraph with Easy Links?” International Mathematics Research Notices. Oxford University Press, 2026. https://doi.org/10.1093/imrn/rnag018.","ieee":"L. Gishboliner, A. Shapira, and Y. Wigderson, “Is it easy to regularize a hypergraph with easy links?,” International Mathematics Research Notices, vol. 2026, no. 4. Oxford University Press, 2026.","apa":"Gishboliner, L., Shapira, A., & Wigderson, Y. (2026). Is it easy to regularize a hypergraph with easy links? International Mathematics Research Notices. Oxford University Press. https://doi.org/10.1093/imrn/rnag018","ama":"Gishboliner L, Shapira A, Wigderson Y. Is it easy to regularize a hypergraph with easy links? International Mathematics Research Notices. 2026;2026(4). doi:10.1093/imrn/rnag018"},"publication":"International Mathematics Research Notices","scopus_import":"1"},{"OA_type":"green","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2026-07-14T09:53:07Z","publication_identifier":{"issn":["0303-1179","2492-5926"]},"title":"ExposĂ© Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe)","scopus_import":"1","page":"85-138","citation":{"ama":"Wigderson Y. ExposĂ© Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). AstĂ©risque. 2026:85-138. doi:10.24033/ast.1255","apa":"Wigderson, Y. (2026). ExposĂ© Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). AstĂ©risque. Societe Mathematique de France. https://doi.org/10.24033/ast.1255","ieee":"Y. Wigderson, “ExposĂ© Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe),” AstĂ©risque. Societe Mathematique de France, pp. 85–138, 2026.","chicago":"Wigderson, Yuval. “ExposĂ© Bourbaki 1230 : Upper Bounds on Diagonal Ramsey Numbers (after Campos, Griffiths, Morris, and Sahasrabudhe).” AstĂ©risque. Societe Mathematique de France, 2026. https://doi.org/10.24033/ast.1255.","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).” AstĂ©risque, Societe Mathematique de France, 2026, pp. 85–138, doi:10.24033/ast.1255.","short":"Y. Wigderson, AstĂ©risque (2026) 85–138."},"publication":"AstĂ©risque","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2411.09321 "}],"publisher":"Societe Mathematique de France","mathsc":["05D10","05C55"],"_id":"22184","type":"journal_article","doi":"10.24033/ast.1255","author":[{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T12:02:59Z","extern":"1","month":"01","day":"01","OA_place":"repository","oa_version":"Preprint","external_id":{"arxiv":["2411.09321"]},"abstract":[{"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":"eng"},{"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.","lang":"fre"}],"article_type":"original","publication_status":"published","date_published":"2026-01-01T00:00:00Z","year":"2026","oa":1,"arxiv":1},{"abstract":[{"lang":"eng","text":"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."}],"publication_status":"published","article_type":"original","arxiv":1,"date_published":"2025-09-01T00:00:00Z","volume":39,"year":"2025","oa":1,"extern":"1","month":"09","oa_version":"Preprint","external_id":{"arxiv":["2410.08644"]},"day":"01","OA_place":"repository","type":"journal_article","intvolume":" 39","author":[{"full_name":"Gishboliner, Lior","first_name":"Lior","last_name":"Gishboliner"},{"full_name":"Milojević, Aleksa","first_name":"Aleksa","last_name":"Milojević"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T10:49:48Z","doi":"10.1137/24m1714964","mathsc":["05D10"],"_id":"22155","publisher":"Society for Industrial & Applied Mathematics","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2410.08644","open_access":"1"}],"citation":{"ista":"Gishboliner L, Milojević A, Sudakov B, Wigderson Y. 2025. Canonical Ramsey numbers of sparse graphs. SIAM Journal on Discrete Mathematics. 39(3), 1491–1519.","mla":"Gishboliner, Lior, et al. “Canonical Ramsey Numbers of Sparse Graphs.” SIAM Journal on Discrete Mathematics, vol. 39, no. 3, Society for Industrial & Applied Mathematics, 2025, pp. 1491–519, doi:10.1137/24m1714964.","chicago":"Gishboliner, Lior, Aleksa Milojević, Benny Sudakov, and Yuval Wigderson. “Canonical Ramsey Numbers of Sparse Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2025. https://doi.org/10.1137/24m1714964.","short":"L. Gishboliner, A. Milojević, B. Sudakov, Y. Wigderson, SIAM Journal on Discrete Mathematics 39 (2025) 1491–1519.","ieee":"L. Gishboliner, A. Milojević, B. Sudakov, and Y. Wigderson, “Canonical Ramsey numbers of sparse graphs,” SIAM Journal on Discrete Mathematics, vol. 39, no. 3. Society for Industrial & Applied Mathematics, pp. 1491–1519, 2025.","ama":"Gishboliner L, Milojević A, Sudakov B, Wigderson Y. Canonical Ramsey numbers of sparse graphs. SIAM Journal on Discrete Mathematics. 2025;39(3):1491-1519. doi:10.1137/24m1714964","apa":"Gishboliner, L., Milojević, A., Sudakov, B., & Wigderson, Y. (2025). Canonical Ramsey numbers of sparse graphs. SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/24m1714964"},"page":"1491-1519","publication":"SIAM Journal on Discrete Mathematics","scopus_import":"1","status":"public","issue":"3","article_processing_charge":"No","title":"Canonical Ramsey numbers of sparse graphs","date_updated":"2026-07-08T07:38:44Z","publication_identifier":{"issn":["0895-4801"],"eissn":["1095-7146"]},"OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1"},{"publication":"Proceedings of the London Mathematical Society","citation":{"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.","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).","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","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."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"scopus_import":"1","status":"public","issue":"1","ddc":["500"],"article_processing_charge":"No","article_number":"e70013","title":"Resolution of the Kohayakawa–Kreuter conjecture","publication_identifier":{"eissn":["1460-244X"],"issn":["0024-6115"]},"date_updated":"2026-07-08T10:24:21Z","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1","article_type":"original","publication_status":"published","abstract":[{"lang":"eng","text":"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."}],"arxiv":1,"year":"2025","oa":1,"date_published":"2025-01-01T00:00:00Z","volume":130,"extern":"1","month":"01","external_id":{"arxiv":["2402.03045"]},"oa_version":"Preprint","OA_place":"repository","day":"01","intvolume":" 130","type":"journal_article","date_created":"2026-06-29T10:50:35Z","author":[{"last_name":"Christoph","first_name":"Micha","full_name":"Christoph, Micha"},{"first_name":"Anders","last_name":"Martinsson","full_name":"Martinsson, Anders"},{"last_name":"Steiner","first_name":"Raphael","full_name":"Steiner, Raphael"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson"}],"doi":"10.1112/plms.70013","_id":"22157","mathsc":["05C70","05D10","05C80"],"publisher":"Wiley","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2402.03045","open_access":"1"}]},{"_id":"22158","mathsc":["05C35","11B75"],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2301.07693","open_access":"1"}],"publisher":"Cambridge University Press","author":[{"first_name":"Lior","last_name":"Gishboliner","full_name":"Gishboliner, Lior"},{"last_name":"Shapira","first_name":"Asaf","full_name":"Shapira, Asaf"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T10:51:07Z","doi":"10.1017/fms.2024.68","type":"journal_article","intvolume":" 13","external_id":{"arxiv":["2301.07693"]},"oa_version":"Preprint","OA_place":"repository","day":"10","month":"02","extern":"1","arxiv":1,"year":"2025","oa":1,"date_published":"2025-02-10T00:00:00Z","volume":13,"publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"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:\r\n\r\n‱ We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of to the optimal number .\r\n\r\n‱ 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.\r\n\r\nOur proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments."}],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","OA_type":"green","title":"An efficient asymmetric removal lemma and its limitations","publication_identifier":{"issn":["2050-5094"]},"date_updated":"2026-07-08T10:31:22Z","article_processing_charge":"No","article_number":"e38","status":"public","publication":"Forum of Mathematics, Sigma","citation":{"short":"L. Gishboliner, A. Shapira, Y. Wigderson, Forum of Mathematics, Sigma 13 (2025).","chicago":"Gishboliner, Lior, Asaf Shapira, and Yuval Wigderson. “An Efficient Asymmetric Removal Lemma and Its Limitations.” Forum of Mathematics, Sigma. Cambridge University Press, 2025. https://doi.org/10.1017/fms.2024.68.","ista":"Gishboliner L, Shapira A, Wigderson Y. 2025. An efficient asymmetric removal lemma and its limitations. Forum of Mathematics, Sigma. 13, e38.","mla":"Gishboliner, Lior, et al. “An Efficient Asymmetric Removal Lemma and Its Limitations.” Forum of Mathematics, Sigma, vol. 13, e38, Cambridge University Press, 2025, doi:10.1017/fms.2024.68.","ama":"Gishboliner L, Shapira A, Wigderson Y. An efficient asymmetric removal lemma and its limitations. Forum of Mathematics, Sigma. 2025;13. doi:10.1017/fms.2024.68","apa":"Gishboliner, L., Shapira, A., & Wigderson, Y. (2025). An efficient asymmetric removal lemma and its limitations. Forum of Mathematics, Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2024.68","ieee":"L. Gishboliner, A. Shapira, and Y. Wigderson, “An efficient asymmetric removal lemma and its limitations,” Forum of Mathematics, Sigma, vol. 13. Cambridge University Press, 2025."},"scopus_import":"1"},{"publisher":"Elsevier","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2404.01057 ","open_access":"1"}],"_id":"22163","doi":"10.1016/j.disc.2024.114373","author":[{"last_name":"Haviv","first_name":"Ishay","full_name":"Haviv, Ishay"},{"full_name":"Mattheus, Sam","first_name":"Sam","last_name":"Mattheus"},{"first_name":"Aleksa","last_name":"Milojević","full_name":"Milojević, Aleksa"},{"first_name":"Yuval","last_name":"Wigderson","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"date_created":"2026-06-29T10:53:05Z","intvolume":" 348","type":"journal_article","day":"01","OA_place":"repository","oa_version":"Preprint","external_id":{"arxiv":["2404.01057"]},"extern":"1","month":"04","date_published":"2025-04-01T00:00:00Z","volume":348,"oa":1,"year":"2025","arxiv":1,"abstract":[{"lang":"eng","text":"For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal if its\r\nmembers are non-self-orthogonal and every k + 1 vectors of A include an orthogonal pair.\r\nWe prove that for every prime p there exists some ÎŽ = ÎŽ(p)> 0, such that for every field\r\nF of characteristic p and for all integers k ≄ 2 and d ≄ k, there exists a k-nearly orthogonal\r\nset of at least dΎ·k/ logk vectors of Fd. The size of the set is optimal up to the logk term\r\nin the exponent. We further prove two extensions of this result. In the first, we provide a\r\nlarge set A of non-self-orthogonal vectors of Fd such that for every two subsets of A of\r\nsize k+1 each, some vector of one of the subsets is orthogonal to some vector of the other.\r\nIn the second extension, every k + 1 vectors of the produced set A include ℓ + 1 pairwise\r\northogonal vectors for an arbitrary fixed integer 1 ≀ ℓ ≀ k. The proofs involve probabilistic\r\nand spectral arguments and the hypergraph container method"}],"article_type":"original","publication_status":"published","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"OA_type":"green","date_updated":"2026-07-14T08:17:17Z","publication_identifier":{"issn":["0012-365X"]},"title":"Larger nearly orthogonal sets over finite fields","article_number":"114373","article_processing_charge":"No","issue":"4","status":"public","keyword":["Nearly orthogonal sets","Ramsey theory","Finite fields"],"das_tickbox":"1","scopus_import":"1","citation":{"apa":"Haviv, I., Mattheus, S., Milojević, A., & Wigderson, Y. (2025). Larger nearly orthogonal sets over finite fields. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.114373","ama":"Haviv I, Mattheus S, Milojević A, Wigderson Y. Larger nearly orthogonal sets over finite fields. Discrete Mathematics. 2025;348(4). doi:10.1016/j.disc.2024.114373","ieee":"I. Haviv, S. Mattheus, A. Milojević, and Y. Wigderson, “Larger nearly orthogonal sets over finite fields,” Discrete Mathematics, vol. 348, no. 4. Elsevier, 2025.","short":"I. Haviv, S. Mattheus, A. Milojević, Y. Wigderson, Discrete Mathematics 348 (2025).","chicago":"Haviv, Ishay, Sam Mattheus, Aleksa Milojević, and Yuval Wigderson. “Larger Nearly Orthogonal Sets over Finite Fields.” Discrete Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.disc.2024.114373.","mla":"Haviv, Ishay, et al. “Larger Nearly Orthogonal Sets over Finite Fields.” Discrete Mathematics, vol. 348, no. 4, 114373, Elsevier, 2025, doi:10.1016/j.disc.2024.114373.","ista":"Haviv I, Mattheus S, Milojević A, Wigderson Y. 2025. Larger nearly orthogonal sets over finite fields. Discrete Mathematics. 348(4), 114373."},"publication":"Discrete Mathematics"},{"intvolume":" 178","type":"journal_article","date_created":"2026-06-29T10:55:00Z","author":[{"full_name":"KUPERWASSER, EDEN","last_name":"KUPERWASSER","first_name":"EDEN"},{"full_name":"SAMOTIJ, WOJCIECH","first_name":"WOJCIECH","last_name":"SAMOTIJ"},{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","last_name":"Wigderson","first_name":"Yuval"}],"doi":"10.1017/s0305004125000143","mathsc":["05C80","05C55","05D10"],"_id":"22168","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2307.16611"}],"publisher":"Cambridge University Press","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_type":"original","publication_status":"published","arxiv":1,"date_published":"2025-04-28T00:00:00Z","volume":178,"oa":1,"year":"2025","month":"04","extern":"1","oa_version":"Preprint","external_id":{"arxiv":["2307.16611"]},"day":"28","OA_place":"repository","article_processing_charge":"No","title":"On the Kohayakawa–Kreuter conjecture","date_updated":"2026-07-14T08:38:08Z","publication_identifier":{"issn":["0305-0041"],"eissn":["1469-8064"]},"OA_type":"green","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","citation":{"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.","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","short":"E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the Cambridge Philosophical Society 178 (2025) 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.","ista":"KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.","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."},"page":"293-320","publication":"Mathematical Proceedings of the Cambridge Philosophical Society","scopus_import":"1","status":"public","issue":"3"},{"type":"journal_article","intvolume":" 10","date_created":"2026-06-29T10:56:44Z","author":[{"full_name":"GirĂŁo, AntĂłnio","first_name":"AntĂłnio","last_name":"GirĂŁo"},{"full_name":"Hunter, Zach","first_name":"Zach","last_name":"Hunter"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson"}],"doi":"10.19086/aic.2025.10","_id":"22172","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2408.12913"}],"publisher":"Alliance of Diamond Open Access Journals","article_type":"original","publication_status":"published","abstract":[{"text":"A highly influential result of Nikiforov states that if an n-vertex graph G contains\r\nat least Îłnh copies of a fixed h-vertex graph H, then G contains a blowup of H of order\r\nΩγ,H(logn). While the dependence on n is optimal, the correct dependence on Îł is unknown;\r\nall known proofs yield bounds that are polynomial in Îł, but the best known upper bound,\r\ncoming from random graphs, is only logarithmic in Îł. It is a major open problem to narrow\r\nthis gap.\r\nWe prove that if H is triangle-free, then the logarithmic behavior of the upper bound\r\nis the truth. That is, under the assumptions above, G contains a blowup of H of order\r\nΩH(logn/log(1/Îł)). This is the first non-trivial instance where the optimal dependence in\r\nNikiforov’s theorem is known.\r\nAs a consequence, we also prove an upper bound on multicolor Ramsey numbers of\r\nblowups of triangle-free graphs, proving that the dependence on the number of colors is\r\npolynomial once the blowup is sufficiently large. This shows that, from the perspective\r\nof multicolor Ramsey numbers, blowups of fixed triangle-free graphs behave like bipartite\r\ngraphs.","lang":"eng"}],"arxiv":1,"year":"2025","oa":1,"date_published":"2025-12-19T00:00:00Z","volume":10,"extern":"1","month":"12","external_id":{"arxiv":["2408.12913"]},"oa_version":"Preprint","OA_place":"repository","day":"19","article_processing_charge":"No","title":"Blowups of triangle-free graphs","date_updated":"2026-07-14T08:50:55Z","OA_type":"green","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publication":"Advances in Combinatorics","citation":{"short":"A. GirĂŁo, Z. Hunter, Y. Wigderson, Advances in Combinatorics 10 (2025).","chicago":"GirĂŁo, AntĂłnio, Zach Hunter, and Yuval Wigderson. “Blowups of Triangle-Free Graphs.” Advances in Combinatorics. Alliance of Diamond Open Access Journals, 2025. https://doi.org/10.19086/aic.2025.10.","ista":"GirĂŁo A, Hunter Z, Wigderson Y. 2025. Blowups of triangle-free graphs. Advances in Combinatorics. 10.","mla":"GirĂŁo, AntĂłnio, et al. “Blowups of Triangle-Free Graphs.” Advances in Combinatorics, vol. 10, Alliance of Diamond Open Access Journals, 2025, doi:10.19086/aic.2025.10.","apa":"GirĂŁo, A., Hunter, Z., & Wigderson, Y. (2025). Blowups of triangle-free graphs. Advances in Combinatorics. Alliance of Diamond Open Access Journals. https://doi.org/10.19086/aic.2025.10","ama":"GirĂŁo A, Hunter Z, Wigderson Y. Blowups of triangle-free graphs. Advances in Combinatorics. 2025;10. doi:10.19086/aic.2025.10","ieee":"A. GirĂŁo, Z. Hunter, and Y. Wigderson, “Blowups of triangle-free graphs,” Advances in Combinatorics, vol. 10. Alliance of Diamond Open Access Journals, 2025."},"scopus_import":"1","status":"public"},{"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2409.05931 "}],"publisher":"Elsevier","_id":"22181","doi":"10.1016/j.ejc.2025.104175","date_created":"2026-06-29T10:59:47Z","author":[{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"type":"journal_article","intvolume":" 128","day":"01","OA_place":"repository","oa_version":"Preprint","external_id":{"arxiv":["2409.05931"]},"extern":"1","month":"08","volume":128,"date_published":"2025-08-01T00:00:00Z","oa":1,"year":"2025","arxiv":1,"abstract":[{"text":"A graph G is said to be Ramsey size-linear if r(G, H) = OG(e(H))\r\nfor every graph H with no isolated vertices. ErdƑs, Faudree,\r\nRousseau, and Schelp observed that K4 is not Ramsey size-linear,\r\nbut each of its proper subgraphs is, and they asked whether there\r\nexist infinitely many such graphs. In this short note, we answer\r\nthis question in the affirmative","lang":"eng"}],"article_type":"original","publication_status":"published","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green","date_updated":"2026-07-14T09:13:09Z","publication_identifier":{"issn":["0195-6698"]},"title":"Infinitely many minimally non-Ramsey size-linear graphs","article_number":"104175","article_processing_charge":"No","status":"public","scopus_import":"1","citation":{"ieee":"Y. Wigderson, “Infinitely many minimally non-Ramsey size-linear graphs,” European Journal of Combinatorics, vol. 128. Elsevier, 2025.","apa":"Wigderson, Y. (2025). Infinitely many minimally non-Ramsey size-linear graphs. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104175","ama":"Wigderson Y. Infinitely many minimally non-Ramsey size-linear graphs. European Journal of Combinatorics. 2025;128. doi:10.1016/j.ejc.2025.104175","mla":"Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.” European Journal of Combinatorics, vol. 128, 104175, Elsevier, 2025, doi:10.1016/j.ejc.2025.104175.","ista":"Wigderson Y. 2025. Infinitely many minimally non-Ramsey size-linear graphs. European Journal of Combinatorics. 128, 104175.","chicago":"Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.” European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104175.","short":"Y. Wigderson, European Journal of Combinatorics 128 (2025)."},"publication":"European Journal of Combinatorics"},{"author":[{"last_name":"Li","first_name":"Yinan","full_name":"Li, Yinan"},{"last_name":"Qiao","first_name":"Youming","full_name":"Qiao, Youming"},{"first_name":"Avi","last_name":"Wigderson","full_name":"Wigderson, Avi"},{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","last_name":"Wigderson"},{"full_name":"Zhang, Chuanqi","last_name":"Zhang","first_name":"Chuanqi"}],"date_created":"2026-06-29T12:14:06Z","doi":"10.4086/toc.2025.v021a001","intvolume":" 21","type":"journal_article","mathsc":["05C18","68R10"],"_id":"22188","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2212.13154"}],"publisher":"Theory of Computing Exchange","arxiv":1,"volume":21,"date_published":"2025-04-12T00:00:00Z","oa":1,"year":"2025","abstract":[{"lang":"eng","text":"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.\r\n\r\nThere 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.\r\n\r\nMoreover, 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."}],"publication_status":"published","article_type":"original","oa_version":"Preprint","external_id":{"arxiv":["2212.13154"]},"day":"12","OA_place":"repository","month":"04","extern":"1","title":"On linear-algebraic notions of expansion","date_updated":"2026-07-14T09:47:56Z","publication_identifier":{"issn":["1557-2862"]},"article_processing_charge":"No","article_number":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1","OA_type":"green","status":"public","keyword":["linear algebraic expansion","quantum expanders","dimension expanders"],"citation":{"short":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Theory of Computing 21 (2025).","mla":"Li, Yinan, et al. “On Linear-Algebraic Notions of Expansion.” Theory of Computing, vol. 21, 1, Theory of Computing Exchange, 2025, doi:10.4086/toc.2025.v021a001.","ista":"Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2025. On linear-algebraic notions of expansion. Theory of Computing. 21, 1.","chicago":"Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang. “On Linear-Algebraic Notions of Expansion.” Theory of Computing. Theory of Computing Exchange, 2025. https://doi.org/10.4086/toc.2025.v021a001.","ieee":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “On linear-algebraic notions of expansion,” Theory of Computing, vol. 21. Theory of Computing Exchange, 2025.","apa":"Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., & Zhang, C. (2025). On linear-algebraic notions of expansion. Theory of Computing. Theory of Computing Exchange. https://doi.org/10.4086/toc.2025.v021a001","ama":"Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. On linear-algebraic notions of expansion. Theory of Computing. 2025;21. doi:10.4086/toc.2025.v021a001"},"publication":"Theory of Computing","scopus_import":"1"},{"publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"date_updated":"2026-07-08T07:34:36Z","acknowledgement":"Open access funding provided by Eidgenossische Technische Hochschule Zurich.","title":"The inertia bound is far from tight","article_processing_charge":"Yes (via OA deal)","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","status":"public","scopus_import":"1","publication":"Bulletin of the London Mathematical Society","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"page":"3196-3208","citation":{"ama":"Kwan M, Wigderson Y. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 2024;56(10):3196-3208. doi:10.1112/blms.13127","apa":"Kwan, M., & Wigderson, Y. (2024). The inertia bound is far from tight. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.13127","ieee":"M. Kwan and Y. Wigderson, “The inertia bound is far from tight,” Bulletin of the London Mathematical Society, vol. 56, no. 10. Wiley, pp. 3196–3208, 2024.","short":"M. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024) 3196–3208.","chicago":"Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” Bulletin of the London Mathematical Society. Wiley, 2024. https://doi.org/10.1112/blms.13127.","ista":"Kwan M, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208.","mla":"Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” Bulletin of the London Mathematical Society, vol. 56, no. 10, Wiley, 2024, pp. 3196–208, doi:10.1112/blms.13127."},"issue":"10","ddc":["500"],"doi":"10.1112/blms.13127","date_created":"2026-06-29T10:49:18Z","author":[{"first_name":"Matthew","last_name":"Kwan","full_name":"Kwan, Matthew"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"type":"journal_article","intvolume":" 56","main_file_link":[{"url":"https://doi.org/10.1112/blms.13127","open_access":"1"}],"publisher":"Wiley","_id":"22154","oa":1,"year":"2024","volume":56,"date_published":"2024-10-01T00:00:00Z","arxiv":1,"publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"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."}],"OA_place":"publisher","day":"01","external_id":{"arxiv":["2312.04925"]},"oa_version":"Published Version","extern":"1","month":"10"},{"publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"date_updated":"2026-07-14T09:08:32Z","title":"Ramsey numbers of sparse digraphs","article_processing_charge":"No","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"OA_type":"green","status":"public","scopus_import":"1","publication":"Israel Journal of Mathematics","page":"1-48","citation":{"chicago":"Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey Numbers of Sparse Digraphs.” Israel Journal of Mathematics. Springer Nature, 2024. https://doi.org/10.1007/s11856-024-2624-y.","mla":"Fox, Jacob, et al. “Ramsey Numbers of Sparse Digraphs.” Israel Journal of Mathematics, vol. 263, no. 1, Springer Nature, 2024, pp. 1–48, doi:10.1007/s11856-024-2624-y.","ista":"Fox J, He X, Wigderson Y. 2024. Ramsey numbers of sparse digraphs. Israel Journal of Mathematics. 263(1), 1–48.","short":"J. Fox, X. He, Y. Wigderson, Israel Journal of Mathematics 263 (2024) 1–48.","ama":"Fox J, He X, Wigderson Y. Ramsey numbers of sparse digraphs. Israel Journal of Mathematics. 2024;263(1):1-48. doi:10.1007/s11856-024-2624-y","apa":"Fox, J., He, X., & Wigderson, Y. (2024). Ramsey numbers of sparse digraphs. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-024-2624-y","ieee":"J. Fox, X. He, and Y. Wigderson, “Ramsey numbers of sparse digraphs,” Israel Journal of Mathematics, vol. 263, no. 1. Springer Nature, pp. 1–48, 2024."},"issue":"1","doi":"10.1007/s11856-024-2624-y","date_created":"2026-06-29T10:59:02Z","author":[{"last_name":"Fox","first_name":"Jacob","full_name":"Fox, Jacob"},{"first_name":"Xiaoyu","last_name":"He","full_name":"He, Xiaoyu"},{"full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","last_name":"Wigderson"}],"intvolume":" 263","type":"journal_article","publisher":"Springer Nature","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2105.02383"}],"_id":"22179","oa":1,"year":"2024","date_published":"2024-10-01T00:00:00Z","volume":263,"arxiv":1,"publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"Burr and Erd˝os in 1975 conjectured, and ChvÂŽatal, Ršodl, SzemerÂŽedi and\r\nTrotter later proved, that the Ramsey number of any bounded degree\r\ngraph is linear in the number of vertices. In this paper, we disprove\r\nthe natural directed analogue of the Burr–Erd˝os conjecture, answering a\r\nquestion of BuciÂŽc, Letzter, and Sudakov. If H is an acyclic digraph, the\r\noriented Ramsey number of H, denoted −→r1(H), is the least N such that\r\nevery tournament on N vertices contains a copy of H. We show that for\r\nany Δ ≄ 2 and any sufficiently large n, there exists an acyclic digraph H\r\nwith n vertices and maximum degree Δ such that\r\n−→r1(H) ≄ nΩ(Δ2/3/ log5/3 Δ).\r\nThis proves that −→r1(H) is not always linear in the number of vertices for\r\nbounded-degree H. On the other hand, we show that −→r1(H) is nearly linear\r\nin the number of vertices for typical bounded-degree acyclic digraphs H,\r\nand obtain linear or nearly linear bounds for several natural families of\r\nbounded-degree acyclic digraphs.\r\nFor multiple colors, we prove a quasi-polynomial upper bound −→rk(H)=\r\n2(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\r\nvertices contains a monochromatic copy of H. For k ≄ 2 and n ≄ 4, we\r\nexhibit an acyclic digraph H with n vertices and maximum degree 3 such\r\nthat −→rk(H) ≄ nΩ(log n/ log log n), showing that these Ramsey numbers can\r\ngrow faster than any polynomial in the number of vertices."}],"OA_place":"repository","day":"01","external_id":{"arxiv":["2105.02383"]},"oa_version":"Preprint","month":"10","extern":"1"},{"article_type":"original","publication_status":"published","abstract":[{"lang":"eng","text":"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 ."}],"oa":1,"year":"2024","date_published":"2024-07-01T00:00:00Z","volume":106,"extern":"1","month":"07","OA_place":"repository","day":"01","external_id":{"unknown":["2208.11181"]},"oa_version":"Preprint","intvolume":" 106","type":"journal_article","doi":"10.1002/jgt.23093","author":[{"first_name":"Yuval","last_name":"Wigderson","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"date_created":"2026-06-29T10:59:24Z","publisher":"Wiley","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2208.11181"}],"_id":"22180","scopus_import":"1","publication":"Journal of Graph Theory","page":"663-675","citation":{"short":"Y. Wigderson, Journal of Graph Theory 106 (2024) 663–675.","chicago":"Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” Journal of Graph Theory. Wiley, 2024. https://doi.org/10.1002/jgt.23093.","ista":"Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 106(3), 663–675.","mla":"Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” Journal of Graph Theory, vol. 106, no. 3, Wiley, 2024, pp. 663–75, doi:10.1002/jgt.23093.","apa":"Wigderson, Y. (2024). Ramsey numbers upon vertex deletion. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.23093","ama":"Wigderson Y. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 2024;106(3):663-675. doi:10.1002/jgt.23093","ieee":"Y. Wigderson, “Ramsey numbers upon vertex deletion,” Journal of Graph Theory, vol. 106, no. 3. Wiley, pp. 663–675, 2024."},"status":"public","issue":"3","article_processing_charge":"No","publication_identifier":{"issn":["0364-9024"],"eissn":["1097-0118"]},"date_updated":"2026-07-14T09:10:28Z","title":"Ramsey numbers upon vertex deletion","OA_type":"green","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}]},{"date_published":"2023-09-01T00:00:00Z","volume":256,"oa":1,"year":"2023","arxiv":1,"abstract":[{"text":"Given a bipartite graph G, the graphical matrix space SG consists of\r\nmatrices whose non-zero entries can only be at those positions corresponding to edges in G. Tutte (J. London Math. Soc., 1947), Edmonds\r\n(J. Res. Nat. Bur. Standards Sect. B, 1967) and LovÂŽasz (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices\r\nin SG. DieudonnÂŽe (Arch. Math., 1948) proved a tight upper bound on\r\nthe dimensions of those matrix spaces containing only singular matrices.\r\nThe starting point of this paper is a simultaneous generalization of these\r\ntwo classical results: we show that the largest dimension over subspaces\r\nof SG containing only singular matrices is equal to the maximum size over\r\nsubgraphs of G without perfect matchings, based on Meshulam’s proof of\r\nDieudonnÂŽe’s result (Quart. J. Math., 1985).\r\nStarting from this result, we go on to establish more connections\r\nbetween properties of graphs and matrix spaces. For example, we\r\nestablish connections between acyclicity and nilpotency, between strong\r\nconnectivity and irreducibility, and between isomorphism and\r\nconjugacy/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\r\n(for induced subgraphs and restrictions). Some correspondences lead to\r\nintriguing generalizations of classical results, such as DieudonnÂŽe’s result\r\nmentioned above, and a celebrated theorem of Gerstenhaber regarding the\r\nlargest dimension of nil matrix spaces (Amer. J. Math., 1958).\r\nFinally, we show some implications of our results to quantum information and present open problems in computational complexity motivated\r\nby these results.","lang":"eng"}],"publication_status":"published","article_type":"original","day":"01","OA_place":"repository","oa_version":"Preprint","external_id":{"arxiv":["2206.04815"]},"month":"09","extern":"1","doi":"10.1007/s11856-023-2515-7","date_created":"2026-06-29T10:52:37Z","author":[{"full_name":"Li, Yinan","last_name":"Li","first_name":"Yinan"},{"full_name":"Qiao, Youming","last_name":"Qiao","first_name":"Youming"},{"full_name":"Wigderson, Avi","last_name":"Wigderson","first_name":"Avi"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"},{"full_name":"Zhang, Chuanqi","first_name":"Chuanqi","last_name":"Zhang"}],"intvolume":" 256","type":"journal_article","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2206.04815","open_access":"1"}],"publisher":"Springer Nature","_id":"22162","status":"public","scopus_import":"1","page":"513-580","citation":{"ama":"Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. Connections between graphs and matrix spaces. Israel Journal of Mathematics. 2023;256(2):513-580. doi:10.1007/s11856-023-2515-7","apa":"Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., & Zhang, C. (2023). Connections between graphs and matrix spaces. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2515-7","ieee":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between graphs and matrix spaces,” Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 513–580, 2023.","chicago":"Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang. “Connections between Graphs and Matrix Spaces.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2515-7.","ista":"Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2023. Connections between graphs and matrix spaces. Israel Journal of Mathematics. 256(2), 513–580.","mla":"Li, Yinan, et al. “Connections between Graphs and Matrix Spaces.” Israel Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80, doi:10.1007/s11856-023-2515-7.","short":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Israel Journal of Mathematics 256 (2023) 513–580."},"publication":"Israel Journal of Mathematics","issue":"2","date_updated":"2026-07-08T10:44:50Z","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"title":"Connections between graphs and matrix spaces","article_processing_charge":"No","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green"},{"doi":"10.1007/s00493-023-00034-7","date_created":"2026-06-29T10:51:32Z","author":[{"full_name":"Conlon, David","first_name":"David","last_name":"Conlon"},{"full_name":"Fox, Jacob","first_name":"Jacob","last_name":"Fox"},{"first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval"}],"type":"journal_article","intvolume":" 43","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.05420","open_access":"1"}],"publisher":"Springer Nature","_id":"22159","oa":1,"year":"2023","date_published":"2023-08-01T00:00:00Z","volume":43,"arxiv":1,"publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"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)."}],"OA_place":"repository","day":"01","external_id":{"arxiv":["2111.05420"]},"oa_version":"Preprint","extern":"1","month":"08","publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"date_updated":"2026-07-08T10:34:40Z","title":"Three early problems on size Ramsey numbers","article_processing_charge":"No","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"OA_type":"green","status":"public","scopus_import":"1","publication":"Combinatorica","page":"743-768","citation":{"short":"D. Conlon, J. Fox, Y. Wigderson, Combinatorica 43 (2023) 743–768.","ista":"Conlon D, Fox J, Wigderson Y. 2023. Three early problems on size Ramsey numbers. Combinatorica. 43(4), 743–768.","mla":"Conlon, David, et al. “Three Early Problems on Size Ramsey Numbers.” Combinatorica, vol. 43, no. 4, Springer Nature, 2023, pp. 743–68, doi:10.1007/s00493-023-00034-7.","chicago":"Conlon, David, Jacob Fox, and Yuval Wigderson. “Three Early Problems on Size Ramsey Numbers.” Combinatorica. Springer Nature, 2023. https://doi.org/10.1007/s00493-023-00034-7.","ieee":"D. Conlon, J. Fox, and Y. Wigderson, “Three early problems on size Ramsey numbers,” Combinatorica, vol. 43, no. 4. Springer Nature, pp. 743–768, 2023.","ama":"Conlon D, Fox J, Wigderson Y. Three early problems on size Ramsey numbers. Combinatorica. 2023;43(4):743-768. doi:10.1007/s00493-023-00034-7","apa":"Conlon, D., Fox, J., & Wigderson, Y. (2023). Three early problems on size Ramsey numbers. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-023-00034-7"},"issue":"4"},{"publication_status":"published","article_type":"original","abstract":[{"text":"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.","lang":"eng"}],"year":"2023","oa":1,"date_published":"2023-04-01T00:00:00Z","volume":102,"arxiv":1,"extern":"1","month":"04","OA_place":"repository","day":"01","external_id":{"arxiv":["2105.09194"]},"oa_version":"Preprint","intvolume":" 102","type":"journal_article","doi":"10.1002/jgt.22891","author":[{"last_name":"Fox","first_name":"Jacob","full_name":"Fox, Jacob"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"date_created":"2026-06-29T10:53:26Z","publisher":"Wiley","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2105.09194"}],"_id":"22164","scopus_import":"1","publication":"Journal of Graph Theory","citation":{"ieee":"J. Fox and Y. Wigderson, “Minimum degree and the graph removal lemma,” Journal of Graph Theory, vol. 102, no. 4. Wiley, pp. 648–665, 2023.","ama":"Fox J, Wigderson Y. Minimum degree and the graph removal lemma. Journal of Graph Theory. 2023;102(4):648-665. doi:10.1002/jgt.22891","apa":"Fox, J., & Wigderson, Y. (2023). Minimum degree and the graph removal lemma. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22891","short":"J. Fox, Y. Wigderson, Journal of Graph Theory 102 (2023) 648–665.","ista":"Fox J, Wigderson Y. 2023. Minimum degree and the graph removal lemma. Journal of Graph Theory. 102(4), 648–665.","mla":"Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal Lemma.” Journal of Graph Theory, vol. 102, no. 4, Wiley, 2023, pp. 648–65, doi:10.1002/jgt.22891.","chicago":"Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal Lemma.” Journal of Graph Theory. Wiley, 2023. https://doi.org/10.1002/jgt.22891."},"page":"648-665","keyword":["chromatic threshold","graph removal lemma","homomorphism threshold","minimum degree conditions"],"status":"public","issue":"4","article_processing_charge":"No","publication_identifier":{"eissn":["1097-0118"],"issn":["0364-9024"]},"date_updated":"2026-07-14T08:24:20Z","title":"Minimum degree and the graph removal lemma","OA_type":"green","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}]},{"mathsc":["05C55","05D10"],"_id":"22165","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2110.14483","open_access":"1"}],"publisher":"Cambridge University Press","type":"journal_article","intvolume":" 32","author":[{"last_name":"Conlon","first_name":"David","full_name":"Conlon, David"},{"last_name":"Fox","first_name":"Jacob","full_name":"Fox, Jacob"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T10:53:47Z","doi":"10.1017/s0963548322000360","extern":"1","month":"05","oa_version":"Preprint","external_id":{"arxiv":["2110.14483"]},"day":"01","OA_place":"repository","abstract":[{"text":"The book graph đ”(𝑘)\r\n𝑛 consists of 𝑛 copies of đŸđ‘˜+1 joined along a common đŸđ‘˜. In the prequel to this paper, we studied the diagonal Ramsey number 𝑟⁡(đ”(𝑘)\r\n𝑛,đ”(𝑘)\r\n𝑛). Here we consider the natural off-diagonal variant 𝑟⁡(đ”(𝑘)\r\n𝑐ⁱ𝑛,đ”(𝑘)\r\n𝑛) 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 𝑐.\r\n\r\n","lang":"eng"}],"article_type":"original","publication_status":"published","arxiv":1,"date_published":"2023-05-01T00:00:00Z","volume":32,"year":"2023","oa":1,"OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","title":"Off-diagonal book Ramsey numbers","date_updated":"2026-07-14T08:27:40Z","publication_identifier":{"eissn":["1469-2163"],"issn":["0963-5483"]},"issue":"3","citation":{"ieee":"D. Conlon, J. Fox, and Y. Wigderson, “Off-diagonal book Ramsey numbers,” Combinatorics, Probability and Computing, vol. 32, no. 3. Cambridge University Press, pp. 516–545, 2023.","apa":"Conlon, D., Fox, J., & Wigderson, Y. (2023). Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. Cambridge University Press. https://doi.org/10.1017/s0963548322000360","ama":"Conlon D, Fox J, Wigderson Y. Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. 2023;32(3):516-545. doi:10.1017/s0963548322000360","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.” Combinatorics, Probability and Computing, vol. 32, no. 3, Cambridge University Press, 2023, pp. 516–45, doi:10.1017/s0963548322000360.","chicago":"Conlon, David, Jacob Fox, and Yuval Wigderson. “Off-Diagonal Book Ramsey Numbers.” Combinatorics, Probability and Computing. Cambridge University Press, 2023. https://doi.org/10.1017/s0963548322000360.","short":"D. Conlon, J. Fox, Y. Wigderson, Combinatorics, Probability and Computing 32 (2023) 516–545."},"page":"516-545","publication":"Combinatorics, Probability and Computing","scopus_import":"1","status":"public","keyword":["Ramsey theory","book graphs","Ramsey goodness"]},{"type":"journal_article","doi":"10.19086/aic.2023.2","author":[{"last_name":"Fox","first_name":"Jacob","full_name":"Fox, Jacob"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson","first_name":"Yuval"}],"date_created":"2026-06-29T10:55:46Z","publisher":"Alliance of Diamond Open Access Journals","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2207.07775","open_access":"1"}],"_id":"22170","publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"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.\r\nWe 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.\r\nWe 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."}],"year":"2023","oa":1,"date_published":"2023-01-01T00:00:00Z","arxiv":1,"month":"01","extern":"1","OA_place":"repository","day":"01","external_id":{"arxiv":["2207.07775"]},"oa_version":"Preprint","article_processing_charge":"No","publication_identifier":{"eissn":["2517-5599"]},"date_updated":"2026-07-14T08:45:53Z","title":"Ramsey multiplicity and the TurĂĄn coloring","OA_type":"green","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","publication":"Advances in Combinatorics","citation":{"ama":"Fox J, Wigderson Y. Ramsey multiplicity and the TurĂĄn coloring. Advances in Combinatorics. 2023. doi:10.19086/aic.2023.2","apa":"Fox, J., & Wigderson, Y. (2023). Ramsey multiplicity and the TurĂĄn coloring. Advances in Combinatorics. Alliance of Diamond Open Access Journals. https://doi.org/10.19086/aic.2023.2","ieee":"J. Fox and Y. Wigderson, “Ramsey multiplicity and the TurĂĄn coloring,” Advances in Combinatorics. Alliance of Diamond Open Access Journals, 2023.","short":"J. Fox, Y. Wigderson, Advances in Combinatorics (2023).","chicago":"Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the TurĂĄn Coloring.” Advances in Combinatorics. Alliance of Diamond Open Access Journals, 2023. https://doi.org/10.19086/aic.2023.2.","mla":"Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the TurĂĄn Coloring.” Advances in Combinatorics, Alliance of Diamond Open Access Journals, 2023, doi:10.19086/aic.2023.2.","ista":"Fox J, Wigderson Y. 2023. Ramsey multiplicity and the TurĂĄn coloring. Advances in Combinatorics."},"status":"public"}]