[{"title":"Resolution of the Kohayakawa–Kreuter conjecture","citation":{"short":"M. Christoph, A. Martinsson, R. Steiner, Y. Wigderson, Proceedings of the London Mathematical Society 130 (2025).","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.” <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>.","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>","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.","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>","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>."},"volume":130,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.03045"}],"article_processing_charge":"No","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_published":"2025-01-01T00:00:00Z","day":"01","date_updated":"2026-07-08T10:24:21Z","type":"journal_article","publication_identifier":{"eissn":["1460-244X"],"issn":["0024-6115"]},"year":"2025","ddc":["500"],"quality_controlled":"1","month":"01","publication":"Proceedings of the London Mathematical Society","status":"public","oa":1,"mathsc":["05C70","05D10","05C80"],"publisher":"Wiley","article_type":"original","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."}],"OA_place":"repository","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"_id":"22157","date_created":"2026-06-29T10:50:35Z","scopus_import":"1","external_id":{"arxiv":["2402.03045"]},"oa_version":"Preprint","author":[{"last_name":"Christoph","full_name":"Christoph, Micha","first_name":"Micha"},{"first_name":"Anders","full_name":"Martinsson, Anders","last_name":"Martinsson"},{"first_name":"Raphael","last_name":"Steiner","full_name":"Steiner, Raphael"},{"full_name":"Wigderson, Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval"}],"doi":"10.1112/plms.70013","intvolume":"       130","issue":"1","publication_status":"published","article_number":"e70013","extern":"1","arxiv":1},{"title":"On the Kohayakawa–Kreuter conjecture","citation":{"ama":"KUPERWASSER E, SAMOTIJ W, Wigderson Y. On the Kohayakawa–Kreuter conjecture. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. 2025;178(3):293-320. doi:<a href=\"https://doi.org/10.1017/s0305004125000143\">10.1017/s0305004125000143</a>","ieee":"E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 178, no. 3. Cambridge University Press, pp. 293–320, 2025.","apa":"KUPERWASSER, E., SAMOTIJ, W., &#38; Wigderson, Y. (2025). On the Kohayakawa–Kreuter conjecture. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/s0305004125000143\">https://doi.org/10.1017/s0305004125000143</a>","chicago":"KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter Conjecture.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.1017/s0305004125000143\">https://doi.org/10.1017/s0305004125000143</a>.","mla":"KUPERWASSER, EDEN, et al. “On the Kohayakawa–Kreuter Conjecture.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 178, no. 3, Cambridge University Press, 2025, pp. 293–320, doi:<a href=\"https://doi.org/10.1017/s0305004125000143\">10.1017/s0305004125000143</a>.","ista":"KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.","short":"E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the Cambridge Philosophical Society 178 (2025) 293–320."},"volume":178,"article_processing_charge":"No","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2307.16611","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green","language":[{"iso":"eng"}],"date_published":"2025-04-28T00:00:00Z","date_updated":"2026-07-14T08:38:08Z","day":"28","year":"2025","type":"journal_article","publication_identifier":{"issn":["0305-0041"],"eissn":["1469-8064"]},"quality_controlled":"1","publication":"Mathematical Proceedings of the Cambridge Philosophical Society","month":"04","oa":1,"status":"public","mathsc":["05C80","05C55","05D10"],"publisher":"Cambridge University Press","article_type":"original","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."}],"OA_place":"repository","_id":"22168","page":"293-320","date_created":"2026-06-29T10:55:00Z","scopus_import":"1","external_id":{"arxiv":["2307.16611"]},"oa_version":"Preprint","author":[{"full_name":"KUPERWASSER, EDEN","last_name":"KUPERWASSER","first_name":"EDEN"},{"first_name":"WOJCIECH","full_name":"SAMOTIJ, WOJCIECH","last_name":"SAMOTIJ"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson"}],"doi":"10.1017/s0305004125000143","intvolume":"       178","issue":"3","publication_status":"published","extern":"1","arxiv":1}]