[{"_id":"22157","publisher":"Wiley","article_type":"original","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.03045"}],"title":"Resolution of the Kohayakawa–Kreuter conjecture","mathsc":["05C70","05D10","05C80"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"volume":130,"month":"01","OA_place":"repository","date_published":"2025-01-01T00:00:00Z","oa":1,"citation":{"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>","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>","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.","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."},"intvolume":"       130","publication":"Proceedings of the London Mathematical Society","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"author":[{"full_name":"Christoph, Micha","first_name":"Micha","last_name":"Christoph"},{"last_name":"Martinsson","first_name":"Anders","full_name":"Martinsson, Anders"},{"first_name":"Raphael","full_name":"Steiner, Raphael","last_name":"Steiner"},{"last_name":"Wigderson","full_name":"Wigderson, Yuval","first_name":"Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"external_id":{"arxiv":["2402.03045"]},"article_number":"e70013","publication_identifier":{"eissn":["1460-244X"],"issn":["0024-6115"]},"oa_version":"Preprint","publication_status":"published","date_created":"2026-06-29T10:50:35Z","doi":"10.1112/plms.70013","article_processing_charge":"No","fulldoi":"https://doi.org/10.1112/plms.70013","day":"01","date_updated":"2026-07-08T10:24:21Z","scopus_import":"1","ddc":["500"],"license":"https://creativecommons.org/licenses/by/4.0/","type":"journal_article","status":"public","issue":"1","arxiv":1,"year":"2025","OA_type":"green","quality_controlled":"1"},{"publisher":"EMS Press","_id":"18951","supplementarymaterial":"unclear","title":"Local dimer dynamics in higher dimensions","mathsc":["05B50","05C70","82C20"],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2304.10930"}],"article_type":"original","OA_place":"repository","das_tickbox":"1","date_published":"2024-08-26T00:00:00Z","oa":1,"month":"08","citation":{"mla":"Hartarsky, Ivailo, et al. “Local Dimer Dynamics in Higher Dimensions.” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>, EMS Press, 2024, doi:<a href=\"https://doi.org/10.4171/aihpd/200\">10.4171/aihpd/200</a>.","apa":"Hartarsky, I., Lichev, L., &#38; Toninelli, F. L. (2024). Local dimer dynamics in higher dimensions. <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>. EMS Press. <a href=\"https://doi.org/10.4171/aihpd/200\">https://doi.org/10.4171/aihpd/200</a>","chicago":"Hartarsky, Ivailo, Lyuben Lichev, and Fabio Lucio Toninelli. “Local Dimer Dynamics in Higher Dimensions.” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>. EMS Press, 2024. <a href=\"https://doi.org/10.4171/aihpd/200\">https://doi.org/10.4171/aihpd/200</a>.","ista":"Hartarsky I, Lichev L, Toninelli FL. 2024. Local dimer dynamics in higher dimensions. Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions.","ieee":"I. Hartarsky, L. Lichev, and F. L. Toninelli, “Local dimer dynamics in higher dimensions,” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions</i>. EMS Press, 2024.","short":"I. Hartarsky, L. Lichev, F.L. Toninelli, Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions (2024).","ama":"Hartarsky I, Lichev L, Toninelli FL. Local dimer dynamics in higher dimensions. <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions</i>. 2024. doi:<a href=\"https://doi.org/10.4171/aihpd/200\">10.4171/aihpd/200</a>"},"publication":"Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions","language":[{"iso":"eng"}],"DOAJ_listed":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] \r\nd . These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on [n] d  features order n d−2  alternating cycles of length at most 4d−2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension d is ergodic when switching alternating cycles of length at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and Rémila, which also uses 8-cycles. None of our proofs make reference to height functions.","lang":"eng"}],"author":[{"full_name":"Hartarsky, Ivailo","first_name":"Ivailo","last_name":"Hartarsky"},{"last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","first_name":"Lyuben","full_name":"Lichev, Lyuben"},{"first_name":"Fabio Lucio","full_name":"Toninelli, Fabio Lucio","last_name":"Toninelli"}],"external_id":{"arxiv":["2304.10930"]},"article_processing_charge":"Yes","date_created":"2025-01-29T10:57:09Z","doi":"10.4171/aihpd/200","publication_status":"epub_ahead","publication_identifier":{"issn":["2308-5827"],"eissn":["2308-5835"]},"oa_version":"Preprint","fulldoi":"https://doi.org/10.4171/aihpd/200","date_updated":"2026-10-16T10:14:21Z","day":"26","scopus_import":"1","status":"public","type":"journal_article","arxiv":1,"department":[{"_id":"MaKw"}],"year":"2024","OA_type":"gold","researchdata_availability":"unclear","quality_controlled":"1"}]