[{"month":"04","main_file_link":[{"url":"https://doi.org/10.1017/S0963548326100443","open_access":"1"}],"publication_identifier":{"eissn":["1469-2163"],"issn":["0963-5483"]},"publisher":"Cambridge University Press","publication":"Combinatorics, Probability and Computing","OA_place":"publisher","status":"public","arxiv":1,"article_processing_charge":"No","title":"Off-diagonal Ramsey numbers for linear hypergraphs","page":"1-14","year":"2026","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_published":"2026-04-14T00:00:00Z","ddc":["500"],"external_id":{"arxiv":["2507.05641"]},"author":[{"first_name":"Xiaoyu","full_name":"He, Xiaoyu","last_name":"He"},{"last_name":"Nie","first_name":"Jiaxi","full_name":"Nie, Jiaxi"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"},{"first_name":"Hung-Hsun","full_name":"Yu, Hung-Hsun","last_name":"Yu"}],"_id":"22152","date_updated":"2026-07-08T07:24:54Z","quality_controlled":"1","citation":{"chicago":"He, Xiaoyu, Jiaxi Nie, Yuval Wigderson, and Hung-Hsun Yu. “Off-Diagonal Ramsey Numbers for Linear Hypergraphs.” <i>Combinatorics, Probability and Computing</i>. Cambridge University Press, 2026. <a href=\"https://doi.org/10.1017/s0963548326100443\">https://doi.org/10.1017/s0963548326100443</a>.","short":"X. He, J. Nie, Y. Wigderson, H.-H. Yu, Combinatorics, Probability and Computing (2026) 1–14.","mla":"He, Xiaoyu, et al. “Off-Diagonal Ramsey Numbers for Linear Hypergraphs.” <i>Combinatorics, Probability and Computing</i>, Cambridge University Press, 2026, pp. 1–14, doi:<a href=\"https://doi.org/10.1017/s0963548326100443\">10.1017/s0963548326100443</a>.","ieee":"X. He, J. Nie, Y. Wigderson, and H.-H. Yu, “Off-diagonal Ramsey numbers for linear hypergraphs,” <i>Combinatorics, Probability and Computing</i>. Cambridge University Press, pp. 1–14, 2026.","apa":"He, X., Nie, J., Wigderson, Y., &#38; Yu, H.-H. (2026). Off-diagonal Ramsey numbers for linear hypergraphs. <i>Combinatorics, Probability and Computing</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/s0963548326100443\">https://doi.org/10.1017/s0963548326100443</a>","ama":"He X, Nie J, Wigderson Y, Yu H-H. Off-diagonal Ramsey numbers for linear hypergraphs. <i>Combinatorics, Probability and Computing</i>. 2026:1-14. doi:<a href=\"https://doi.org/10.1017/s0963548326100443\">10.1017/s0963548326100443</a>","ista":"He X, Nie J, Wigderson Y, Yu H-H. 2026. Off-diagonal Ramsey numbers for linear hypergraphs. Combinatorics, Probability and Computing., 1–14."},"extern":"1","abstract":[{"lang":"eng","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⁡𝑛)𝐶)."}],"oa":1,"language":[{"iso":"eng"}],"OA_type":"hybrid","scopus_import":"1","day":"14","mathsc":["05D10","05D40","05C65"],"article_type":"original","doi":"10.1017/s0963548326100443","date_created":"2026-06-29T10:47:02Z","publication_status":"epub_ahead","type":"journal_article","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"}},{"publication_status":"published","date_created":"2026-06-29T10:49:48Z","type":"journal_article","doi":"10.1137/24m1714964","article_type":"original","day":"01","mathsc":["05D10"],"OA_type":"green","scopus_import":"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."}],"oa":1,"language":[{"iso":"eng"}],"citation":{"ama":"Gishboliner L, Milojević A, Sudakov B, Wigderson Y. Canonical Ramsey numbers of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2025;39(3):1491-1519. doi:<a href=\"https://doi.org/10.1137/24m1714964\">10.1137/24m1714964</a>","apa":"Gishboliner, L., Milojević, A., Sudakov, B., &#38; Wigderson, Y. (2025). Canonical Ramsey numbers of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/24m1714964\">https://doi.org/10.1137/24m1714964</a>","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.","short":"L. Gishboliner, A. Milojević, B. Sudakov, Y. Wigderson, SIAM Journal on Discrete Mathematics 39 (2025) 1491–1519.","chicago":"Gishboliner, Lior, Aleksa Milojević, Benny Sudakov, and Yuval Wigderson. “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics, 2025. <a href=\"https://doi.org/10.1137/24m1714964\">https://doi.org/10.1137/24m1714964</a>.","ieee":"L. Gishboliner, A. Milojević, B. Sudakov, and Y. Wigderson, “Canonical Ramsey numbers of sparse graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 39, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 1491–1519, 2025.","mla":"Gishboliner, Lior, et al. “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 39, no. 3, Society for Industrial &#38; Applied Mathematics, 2025, pp. 1491–519, doi:<a href=\"https://doi.org/10.1137/24m1714964\">10.1137/24m1714964</a>."},"quality_controlled":"1","date_updated":"2026-07-08T07:38:44Z","extern":"1","issue":"3","_id":"22155","author":[{"last_name":"Gishboliner","full_name":"Gishboliner, Lior","first_name":"Lior"},{"last_name":"Milojević","first_name":"Aleksa","full_name":"Milojević, Aleksa"},{"last_name":"Sudakov","full_name":"Sudakov, Benny","first_name":"Benny"},{"full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"external_id":{"arxiv":["2410.08644"]},"year":"2025","page":"1491-1519","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":39,"date_published":"2025-09-01T00:00:00Z","oa_version":"Preprint","article_processing_charge":"No","title":"Canonical Ramsey numbers of sparse graphs","status":"public","arxiv":1,"publisher":"Society for Industrial & Applied Mathematics","publication":"SIAM Journal on Discrete Mathematics","OA_place":"repository","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2410.08644"}],"publication_identifier":{"eissn":["1095-7146"],"issn":["0895-4801"]},"month":"09","intvolume":"        39"},{"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.03045"}],"publication_identifier":{"issn":["0024-6115"],"eissn":["1460-244X"]},"month":"01","intvolume":"       130","status":"public","arxiv":1,"publisher":"Wiley","publication":"Proceedings of the London Mathematical Society","OA_place":"repository","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","volume":130,"date_published":"2025-01-01T00:00:00Z","article_processing_charge":"No","title":"Resolution of the Kohayakawa–Kreuter conjecture","author":[{"last_name":"Christoph","first_name":"Micha","full_name":"Christoph, Micha"},{"last_name":"Martinsson","first_name":"Anders","full_name":"Martinsson, Anders"},{"first_name":"Raphael","full_name":"Steiner, Raphael","last_name":"Steiner"},{"full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"ddc":["500"],"article_number":"e70013","external_id":{"arxiv":["2402.03045"]},"citation":{"ieee":"M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson, “Resolution of the Kohayakawa–Kreuter conjecture,” <i>Proceedings of the London Mathematical Society</i>, vol. 130, no. 1. Wiley, 2025.","mla":"Christoph, Micha, et al. “Resolution of the Kohayakawa–Kreuter Conjecture.” <i>Proceedings of the London Mathematical Society</i>, vol. 130, no. 1, e70013, Wiley, 2025, doi:<a href=\"https://doi.org/10.1112/plms.70013\">10.1112/plms.70013</a>.","short":"M. Christoph, A. Martinsson, R. Steiner, Y. Wigderson, Proceedings of the London Mathematical Society 130 (2025).","chicago":"Christoph, Micha, Anders Martinsson, Raphael Steiner, and Yuval Wigderson. “Resolution of the Kohayakawa–Kreuter Conjecture.” <i>Proceedings of the London Mathematical Society</i>. Wiley, 2025. <a href=\"https://doi.org/10.1112/plms.70013\">https://doi.org/10.1112/plms.70013</a>.","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.","ama":"Christoph M, Martinsson A, Steiner R, Wigderson Y. Resolution of the Kohayakawa–Kreuter conjecture. <i>Proceedings of the London Mathematical Society</i>. 2025;130(1). doi:<a href=\"https://doi.org/10.1112/plms.70013\">10.1112/plms.70013</a>","apa":"Christoph, M., Martinsson, A., Steiner, R., &#38; Wigderson, Y. (2025). Resolution of the Kohayakawa–Kreuter conjecture. <i>Proceedings of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/plms.70013\">https://doi.org/10.1112/plms.70013</a>"},"date_updated":"2026-07-08T10:24:21Z","quality_controlled":"1","extern":"1","issue":"1","_id":"22157","OA_type":"green","scopus_import":"1","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."}],"language":[{"iso":"eng"}],"oa":1,"article_type":"original","day":"01","mathsc":["05C70","05D10","05C80"],"publication_status":"published","date_created":"2026-06-29T10:50:35Z","type":"journal_article","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"doi":"10.1112/plms.70013"},{"language":[{"iso":"eng"}],"oa":1,"abstract":[{"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.","lang":"eng"}],"scopus_import":"1","OA_type":"green","_id":"22158","extern":"1","citation":{"ama":"Gishboliner L, Shapira A, Wigderson Y. An efficient asymmetric removal lemma and its limitations. <i>Forum of Mathematics, Sigma</i>. 2025;13. doi:<a href=\"https://doi.org/10.1017/fms.2024.68\">10.1017/fms.2024.68</a>","apa":"Gishboliner, L., Shapira, A., &#38; Wigderson, Y. (2025). An efficient asymmetric removal lemma and its limitations. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2024.68\">https://doi.org/10.1017/fms.2024.68</a>","ista":"Gishboliner L, Shapira A, Wigderson Y. 2025. An efficient asymmetric removal lemma and its limitations. Forum of Mathematics, Sigma. 13, e38.","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.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.1017/fms.2024.68\">https://doi.org/10.1017/fms.2024.68</a>.","ieee":"L. Gishboliner, A. Shapira, and Y. Wigderson, “An efficient asymmetric removal lemma and its limitations,” <i>Forum of Mathematics, Sigma</i>, vol. 13. Cambridge University Press, 2025.","mla":"Gishboliner, Lior, et al. “An Efficient Asymmetric Removal Lemma and Its Limitations.” <i>Forum of Mathematics, Sigma</i>, vol. 13, e38, Cambridge University Press, 2025, doi:<a href=\"https://doi.org/10.1017/fms.2024.68\">10.1017/fms.2024.68</a>."},"date_updated":"2026-07-08T10:31:22Z","quality_controlled":"1","doi":"10.1017/fms.2024.68","type":"journal_article","publication_status":"published","date_created":"2026-06-29T10:51:07Z","mathsc":["05C35","11B75"],"day":"10","article_type":"original","publisher":"Cambridge University Press","OA_place":"repository","publication":"Forum of Mathematics, Sigma","status":"public","arxiv":1,"month":"02","intvolume":"        13","publication_identifier":{"issn":["2050-5094"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2301.07693","open_access":"1"}],"external_id":{"arxiv":["2301.07693"]},"article_number":"e38","author":[{"first_name":"Lior","full_name":"Gishboliner, Lior","last_name":"Gishboliner"},{"first_name":"Asaf","full_name":"Shapira, Asaf","last_name":"Shapira"},{"full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"article_processing_charge":"No","title":"An efficient asymmetric removal lemma and its limitations","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","date_published":"2025-02-10T00:00:00Z","oa_version":"Preprint","volume":13},{"intvolume":"        56","month":"10","publication_identifier":{"eissn":["1469-2120"],"issn":["0024-6093"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1112/blms.13127"}],"OA_place":"publisher","publication":"Bulletin of the London Mathematical Society","publisher":"Wiley","arxiv":1,"status":"public","title":"The inertia bound is far from tight","article_processing_charge":"Yes (via OA deal)","date_published":"2024-10-01T00:00:00Z","oa_version":"Published Version","volume":56,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"3196-3208","year":"2024","external_id":{"arxiv":["2312.04925"]},"ddc":["500"],"author":[{"last_name":"Kwan","full_name":"Kwan, Matthew","first_name":"Matthew"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"acknowledgement":"Open access funding provided by Eidgenossische Technische Hochschule Zurich.","issue":"10","_id":"22154","extern":"1","date_updated":"2026-07-08T07:34:36Z","quality_controlled":"1","citation":{"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.” <i>Bulletin of the London Mathematical Society</i>. Wiley, 2024. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>.","ieee":"M. Kwan and Y. Wigderson, “The inertia bound is far from tight,” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10. Wiley, pp. 3196–3208, 2024.","mla":"Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, Wiley, 2024, pp. 3196–208, doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>.","ama":"Kwan M, Wigderson Y. The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. 2024;56(10):3196-3208. doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>","apa":"Kwan, M., &#38; Wigderson, Y. (2024). The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>","ista":"Kwan M, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208."},"oa":1,"language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"scopus_import":"1","OA_type":"hybrid","day":"01","article_type":"original","doi":"10.1112/blms.13127","type":"journal_article","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"publication_status":"published","date_created":"2026-06-29T10:49:18Z"},{"article_type":"original","day":"01","date_created":"2026-06-29T10:52:37Z","publication_status":"published","type":"journal_article","doi":"10.1007/s11856-023-2515-7","quality_controlled":"1","citation":{"apa":"Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2023). Connections between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-023-2515-7\">https://doi.org/10.1007/s11856-023-2515-7</a>","ama":"Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. Connections between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. 2023;256(2):513-580. doi:<a href=\"https://doi.org/10.1007/s11856-023-2515-7\">10.1007/s11856-023-2515-7</a>","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.","chicago":"Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang. “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s11856-023-2515-7\">https://doi.org/10.1007/s11856-023-2515-7</a>.","short":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Israel Journal of Mathematics 256 (2023) 513–580.","mla":"Li, Yinan, et al. “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80, doi:<a href=\"https://doi.org/10.1007/s11856-023-2515-7\">10.1007/s11856-023-2515-7</a>.","ieee":"Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between graphs and matrix spaces,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 513–580, 2023."},"date_updated":"2026-07-08T10:44:50Z","extern":"1","_id":"22162","issue":"2","OA_type":"green","scopus_import":"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"}],"language":[{"iso":"eng"}],"oa":1,"volume":256,"oa_version":"Preprint","date_published":"2023-09-01T00:00:00Z","page":"513-580","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Connections between graphs and matrix spaces","article_processing_charge":"No","author":[{"last_name":"Li","full_name":"Li, Yinan","first_name":"Yinan"},{"full_name":"Qiao, Youming","first_name":"Youming","last_name":"Qiao"},{"first_name":"Avi","full_name":"Wigderson, Avi","last_name":"Wigderson"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson"},{"first_name":"Chuanqi","full_name":"Zhang, Chuanqi","last_name":"Zhang"}],"external_id":{"arxiv":["2206.04815"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2206.04815","open_access":"1"}],"publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"intvolume":"       256","month":"09","arxiv":1,"status":"public","publication":"Israel Journal of Mathematics","OA_place":"repository","publisher":"Springer Nature"},{"month":"08","intvolume":"        43","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.05420","open_access":"1"}],"publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"publisher":"Springer Nature","publication":"Combinatorica","OA_place":"repository","status":"public","arxiv":1,"article_processing_charge":"No","title":"Three early problems on size Ramsey numbers","page":"743-768","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","volume":43,"date_published":"2023-08-01T00:00:00Z","external_id":{"arxiv":["2111.05420"]},"author":[{"first_name":"David","full_name":"Conlon, David","last_name":"Conlon"},{"first_name":"Jacob","full_name":"Fox, Jacob","last_name":"Fox"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"issue":"4","_id":"22159","date_updated":"2026-07-08T10:34:40Z","citation":{"ama":"Conlon D, Fox J, Wigderson Y. Three early problems on size Ramsey numbers. <i>Combinatorica</i>. 2023;43(4):743-768. doi:<a href=\"https://doi.org/10.1007/s00493-023-00034-7\">10.1007/s00493-023-00034-7</a>","apa":"Conlon, D., Fox, J., &#38; Wigderson, Y. (2023). Three early problems on size Ramsey numbers. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-023-00034-7\">https://doi.org/10.1007/s00493-023-00034-7</a>","ista":"Conlon D, Fox J, Wigderson Y. 2023. Three early problems on size Ramsey numbers. Combinatorica. 43(4), 743–768.","short":"D. Conlon, J. Fox, Y. Wigderson, Combinatorica 43 (2023) 743–768.","chicago":"Conlon, David, Jacob Fox, and Yuval Wigderson. “Three Early Problems on Size Ramsey Numbers.” <i>Combinatorica</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00493-023-00034-7\">https://doi.org/10.1007/s00493-023-00034-7</a>.","ieee":"D. Conlon, J. Fox, and Y. Wigderson, “Three early problems on size Ramsey numbers,” <i>Combinatorica</i>, vol. 43, no. 4. Springer Nature, pp. 743–768, 2023.","mla":"Conlon, David, et al. “Three Early Problems on Size Ramsey Numbers.” <i>Combinatorica</i>, vol. 43, no. 4, Springer Nature, 2023, pp. 743–68, doi:<a href=\"https://doi.org/10.1007/s00493-023-00034-7\">10.1007/s00493-023-00034-7</a>."},"quality_controlled":"1","extern":"1","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":1,"language":[{"iso":"eng"}],"OA_type":"green","scopus_import":"1","day":"01","article_type":"original","doi":"10.1007/s00493-023-00034-7","publication_status":"published","date_created":"2026-06-29T10:51:32Z","type":"journal_article"},{"month":"10","intvolume":"       106","publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2010.00077"}],"publisher":"Wiley","OA_place":"repository","publication":"Journal of the London Mathematical Society","status":"public","arxiv":1,"article_processing_charge":"No","title":"Polynomials that vanish to high order on most of the hypercube","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2022","page":"2379-2402","date_published":"2022-10-01T00:00:00Z","volume":106,"oa_version":"Preprint","external_id":{"arxiv":["2010.00077"]},"author":[{"first_name":"Lisa","full_name":"Sauermann, Lisa","last_name":"Sauermann"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"_id":"22160","issue":"3","extern":"1","quality_controlled":"1","citation":{"ama":"Sauermann L, Wigderson Y. Polynomials that vanish to high order on most of the hypercube. <i>Journal of the London Mathematical Society</i>. 2022;106(3):2379-2402. doi:<a href=\"https://doi.org/10.1112/jlms.12637\">10.1112/jlms.12637</a>","apa":"Sauermann, L., &#38; Wigderson, Y. (2022). Polynomials that vanish to high order on most of the hypercube. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.12637\">https://doi.org/10.1112/jlms.12637</a>","ista":"Sauermann L, Wigderson Y. 2022. Polynomials that vanish to high order on most of the hypercube. Journal of the London Mathematical Society. 106(3), 2379–2402.","short":"L. Sauermann, Y. Wigderson, Journal of the London Mathematical Society 106 (2022) 2379–2402.","chicago":"Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High Order on Most of the Hypercube.” <i>Journal of the London Mathematical Society</i>. Wiley, 2022. <a href=\"https://doi.org/10.1112/jlms.12637\">https://doi.org/10.1112/jlms.12637</a>.","ieee":"L. Sauermann and Y. Wigderson, “Polynomials that vanish to high order on most of the hypercube,” <i>Journal of the London Mathematical Society</i>, vol. 106, no. 3. Wiley, pp. 2379–2402, 2022.","mla":"Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High Order on Most of the Hypercube.” <i>Journal of the London Mathematical Society</i>, vol. 106, no. 3, Wiley, 2022, pp. 2379–402, doi:<a href=\"https://doi.org/10.1112/jlms.12637\">10.1112/jlms.12637</a>."},"date_updated":"2026-07-08T10:37:38Z","oa":1,"language":[{"iso":"eng"}],"abstract":[{"text":"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.","lang":"eng"}],"scopus_import":"1","OA_type":"green","day":"01","article_type":"original","doi":"10.1112/jlms.12637","type":"journal_article","publication_status":"published","date_created":"2026-06-29T10:51:52Z"},{"type":"journal_article","date_created":"2026-06-29T10:50:09Z","publication_status":"published","doi":"10.1016/j.jctb.2020.03.003","article_type":"original","day":"01","scopus_import":"1","OA_type":"green","language":[{"iso":"eng"}],"oa":1,"abstract":[{"text":"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.","lang":"eng"}],"extern":"1","quality_controlled":"1","citation":{"ista":"He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. 146, 485–494.","ama":"He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. <i>Journal of Combinatorial Theory, Series B</i>. 2021;146:485-494. doi:<a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">10.1016/j.jctb.2020.03.003</a>","apa":"He, X., &#38; Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically false. <i>Journal of Combinatorial Theory, Series B</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">https://doi.org/10.1016/j.jctb.2020.03.003</a>","ieee":"X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,” <i>Journal of Combinatorial Theory, Series B</i>, vol. 146. Elsevier, pp. 485–494, 2021.","mla":"He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” <i>Journal of Combinatorial Theory, Series B</i>, vol. 146, Elsevier, 2021, pp. 485–94, doi:<a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">10.1016/j.jctb.2020.03.003</a>.","short":"X. He, Y. Wigderson, Journal of Combinatorial Theory, Series B 146 (2021) 485–494.","chicago":"He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” <i>Journal of Combinatorial Theory, Series B</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">https://doi.org/10.1016/j.jctb.2020.03.003</a>."},"date_updated":"2026-07-08T07:43:57Z","_id":"22156","author":[{"first_name":"Xiaoyu","full_name":"He, Xiaoyu","last_name":"He"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"external_id":{"arxiv":["1906.06783"]},"volume":146,"oa_version":"Preprint","date_published":"2021-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"485-494","year":"2021","title":"Hedetniemi's conjecture is asymptotically false","article_processing_charge":"No","arxiv":1,"status":"public","OA_place":"repository","publication":"Journal of Combinatorial Theory, Series B","publisher":"Elsevier","publication_identifier":{"issn":["0095-8956"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1906.06783"}],"intvolume":"       146","keyword":["Graph coloring","Hedetniemi's conjecture"],"month":"01"},{"scopus_import":"1","OA_type":"green","oa":1,"language":[{"iso":"eng"}],"abstract":[{"text":"Recently, Souza introduced blowup Ramsey numbers as a gener-\r\nalization of bipartite Ramsey numbers. For graphs G and H, say\r\nG r\r\n−→ H if every r-edge-coloring of G contains a monochromatic\r\ncopy of H. Let H[t] denote the t-blowup of H. Then the blowup\r\nRamsey number of G, H, r, and t is defined as the minimum n\r\nsuch that G[n] r\r\n−→ H[t]. Souza proved upper and lower bounds on\r\nn that are exponential in t, and conjectured that the exponential\r\nconstant does not depend on G. We prove that the dependence on\r\nG in the exponential constant is indeed unnecessary, but conjecture\r\nthat some dependence on G is unavoidable.\r\nAn important step in both Souza’s proof and ours is a theorem of\r\nNikiforov, which says that if a graph contains a constant fraction\r\nof the possible copies of H, then it contains a blowup of H of\r\nlogarithmic size. We also provide a new proof of this theorem with\r\na better quantitative dependence.","lang":"eng"}],"extern":"1","date_updated":"2026-07-08T10:41:31Z","citation":{"mla":"Fox, Jacob, et al. “Extremal and Ramsey Results on Graph Blowups.” <i>Journal of Combinatorics</i>, vol. 12, no. 1, International Press of Boston, 2021, pp. 1–15, doi:<a href=\"https://doi.org/10.4310/joc.2021.v12.n1.a1\">10.4310/joc.2021.v12.n1.a1</a>.","ieee":"J. Fox, S. Luo, and Y. Wigderson, “Extremal and Ramsey results on graph blowups,” <i>Journal of Combinatorics</i>, vol. 12, no. 1. International Press of Boston, pp. 1–15, 2021.","chicago":"Fox, Jacob, Sammy Luo, and Yuval Wigderson. “Extremal and Ramsey Results on Graph Blowups.” <i>Journal of Combinatorics</i>. International Press of Boston, 2021. <a href=\"https://doi.org/10.4310/joc.2021.v12.n1.a1\">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>.","short":"J. Fox, S. Luo, Y. Wigderson, Journal of Combinatorics 12 (2021) 1–15.","ista":"Fox J, Luo S, Wigderson Y. 2021. Extremal and Ramsey results on graph blowups. Journal of Combinatorics. 12(1), 1–15.","apa":"Fox, J., Luo, S., &#38; Wigderson, Y. (2021). Extremal and Ramsey results on graph blowups. <i>Journal of Combinatorics</i>. International Press of Boston. <a href=\"https://doi.org/10.4310/joc.2021.v12.n1.a1\">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>","ama":"Fox J, Luo S, Wigderson Y. Extremal and Ramsey results on graph blowups. <i>Journal of Combinatorics</i>. 2021;12(1):1-15. doi:<a href=\"https://doi.org/10.4310/joc.2021.v12.n1.a1\">10.4310/joc.2021.v12.n1.a1</a>"},"quality_controlled":"1","issue":"1","_id":"22161","type":"journal_article","publication_status":"published","date_created":"2026-06-29T10:52:13Z","doi":"10.4310/joc.2021.v12.n1.a1","article_type":"original","mathsc":["05C35","05C55"],"day":"01","arxiv":1,"status":"public","OA_place":"repository","publication":"Journal of Combinatorics","publisher":"International Press of Boston","publication_identifier":{"issn":["2156-3527"],"eissn":["2150-959X"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1912.08328","open_access":"1"}],"intvolume":"        12","month":"01","author":[{"first_name":"Jacob","full_name":"Fox, Jacob","last_name":"Fox"},{"full_name":"Luo, Sammy","first_name":"Sammy","last_name":"Luo"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"external_id":{"arxiv":["1912.08328"]},"oa_version":"Preprint","date_published":"2021-01-01T00:00:00Z","volume":12,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","page":"1-15","title":"Extremal and Ramsey results on graph blowups","article_processing_charge":"No"},{"author":[{"last_name":"He","full_name":"He, Xiaoyu","first_name":"Xiaoyu"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"article_number":"P1.32","external_id":{"arxiv":["1910.06287"]},"date_published":"2020-02-07T00:00:00Z","volume":27,"oa_version":"Preprint","year":"2020","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Multicolor Ramsey numbers via pseudorandom graphs","article_processing_charge":"No","arxiv":1,"status":"public","publication":"The Electronic Journal of Combinatorics","OA_place":"repository","publisher":"The Electronic Journal of Combinatorics","publication_identifier":{"issn":["1077-8926"]},"intvolume":"        27","month":"02","date_created":"2026-06-29T10:47:47Z","publication_status":"published","type":"journal_article","doi":"10.37236/9071","article_type":"original","day":"07","OA_type":"green","scopus_import":"1","abstract":[{"lang":"eng","text":"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\r\nΩ(tS+1log2St)≤r(s1,…,sk,t)≤O(tS+1logSt),\r\nas 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."}],"language":[{"iso":"eng"}],"date_updated":"2026-07-08T07:27:57Z","citation":{"apa":"He, X., &#38; Wigderson, Y. (2020). Multicolor Ramsey numbers via pseudorandom graphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/9071\">https://doi.org/10.37236/9071</a>","ama":"He X, Wigderson Y. Multicolor Ramsey numbers via pseudorandom graphs. <i>The Electronic Journal of Combinatorics</i>. 2020;27(1). doi:<a href=\"https://doi.org/10.37236/9071\">10.37236/9071</a>","ista":"He X, Wigderson Y. 2020. Multicolor Ramsey numbers via pseudorandom graphs. The Electronic Journal of Combinatorics. 27(1), P1.32.","chicago":"He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom Graphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics, 2020. <a href=\"https://doi.org/10.37236/9071\">https://doi.org/10.37236/9071</a>.","short":"X. He, Y. Wigderson, The Electronic Journal of Combinatorics 27 (2020).","mla":"He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom Graphs.” <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1, P1.32, The Electronic Journal of Combinatorics, 2020, doi:<a href=\"https://doi.org/10.37236/9071\">10.37236/9071</a>.","ieee":"X. He and Y. Wigderson, “Multicolor Ramsey numbers via pseudorandom graphs,” <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1. The Electronic Journal of Combinatorics, 2020."},"quality_controlled":"1","extern":"1","_id":"22153","issue":"1"}]