[{"date_published":"2025-04-28T00:00:00Z","arxiv":1,"title":"On the Kohayakawa–Kreuter conjecture","publication_identifier":{"eissn":["1469-8064"],"issn":["0305-0041"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2307.16611","open_access":"1"}],"oa_version":"Preprint","_id":"22168","external_id":{"arxiv":["2307.16611"]},"scopus_import":"1","publication":"Mathematical Proceedings of the Cambridge Philosophical Society","author":[{"full_name":"KUPERWASSER, EDEN","first_name":"EDEN","last_name":"KUPERWASSER"},{"last_name":"SAMOTIJ","first_name":"WOJCIECH","full_name":"SAMOTIJ, WOJCIECH"},{"full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"date_updated":"2026-07-14T08:38:08Z","day":"28","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."}],"fulldoi":"https://doi.org/10.1017/s0305004125000143","language":[{"iso":"eng"}],"month":"04","status":"public","article_processing_charge":"No","type":"journal_article","volume":178,"date_created":"2026-06-29T10:55:00Z","extern":"1","intvolume":"       178","OA_type":"green","publisher":"Cambridge University Press","issue":"3","oa":1,"OA_place":"repository","mathsc":["05C80","05C55","05D10"],"article_type":"original","publication_status":"published","citation":{"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>.","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>.","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>","ista":"KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.","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>","short":"E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the Cambridge Philosophical Society 178 (2025) 293–320."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1017/s0305004125000143","year":"2025","page":"293-320"},{"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"Yes (via OA deal)","volume":172,"date_created":"2021-05-02T22:01:29Z","day":"01","date_updated":"2026-08-06T11:08:12Z","abstract":[{"lang":"eng","text":"Let t : Fp → C be a complex valued function on Fp. A classical problem in analytic number theory is bounding the maximum M(t) := max 0≤H<p ∣ 1/√p ∑ 0≤n<H t (n) ∣ of the absolute value of the incomplete sums(1/√p)∑0≤n<H t (n). In this very general context one of the most important results is the Pólya–Vinogradov bound M(t)≤IIˆtII∞ log 3p, where ˆt : Fp → C is the normalized Fourier transform of t. In this paper we provide a lower bound for certain incomplete Kloosterman sums, namely we prove that for any ε > 0 there exists a large subset of a ∈ F×p such that for kl a,1,p : x → e((ax+x) / p) we have M(kla,1,p) ≥ (1−ε/√2π + o(1)) log log p, as p→∞. Finally, we prove a result on the growth of the moments of {M (kla,1,p)}a∈F×p. 2020 Mathematics Subject Classification: 11L03, 11T23 (Primary); 14F20, 60F10 (Secondary)."}],"fulldoi":"https://doi.org/10.1017/S030500412100030X","language":[{"iso":"eng"}],"month":"05","has_accepted_license":"1","status":"public","department":[{"_id":"TiBr"}],"oa_version":"Published Version","acknowledgement":"I am most thankful to my advisor, Emmanuel Kowalski, for suggesting this problem and for his guidance during these years. I also would like to thank Youness Lamzouri for informing me about his work on sum of incomplete Birch sums and Tal Horesh for her suggestions on a previous version of the paper. Finally, I am very grateful to the anonymous referee for their careful reading of the manuscript and their valuable comments.","_id":"9364","external_id":{"arxiv":["1811.10563"],"isi":["000784421500001"]},"scopus_import":"1","publication":"Mathematical Proceedings of the Cambridge Philosophical Society","author":[{"first_name":"Dante","full_name":"Bonolis, Dante","id":"6A459894-5FDD-11E9-AF35-BB24E6697425","last_name":"Bonolis"}],"file_date_updated":"2021-12-01T14:01:54Z","date_published":"2022-05-01T00:00:00Z","arxiv":1,"title":"On the size of the maximum of incomplete Kloosterman sums","publication_identifier":{"issn":["0305-0041"],"eissn":["1469-8064"]},"ddc":["510"],"quality_controlled":"1","year":"2022","doi":"10.1017/S030500412100030X","page":"563 - 590","researchdata_availability":"no","publication_status":"published","citation":{"ama":"Bonolis D. On the size of the maximum of incomplete Kloosterman sums. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. 2022;172(3):563-590. doi:<a href=\"https://doi.org/10.1017/S030500412100030X\">10.1017/S030500412100030X</a>","short":"D. Bonolis, Mathematical Proceedings of the Cambridge Philosophical Society 172 (2022) 563–590.","apa":"Bonolis, D. (2022). On the size of the maximum of incomplete Kloosterman sums. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/S030500412100030X\">https://doi.org/10.1017/S030500412100030X</a>","ieee":"D. Bonolis, “On the size of the maximum of incomplete Kloosterman sums,” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 172, no. 3. Cambridge University Press, pp. 563–590, 2022.","ista":"Bonolis D. 2022. On the size of the maximum of incomplete Kloosterman sums. Mathematical Proceedings of the Cambridge Philosophical Society. 172(3), 563–590.","mla":"Bonolis, Dante. “On the Size of the Maximum of Incomplete Kloosterman Sums.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 172, no. 3, Cambridge University Press, 2022, pp. 563–90, doi:<a href=\"https://doi.org/10.1017/S030500412100030X\">10.1017/S030500412100030X</a>.","chicago":"Bonolis, Dante. “On the Size of the Maximum of Incomplete Kloosterman Sums.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge University Press, 2022. <a href=\"https://doi.org/10.1017/S030500412100030X\">https://doi.org/10.1017/S030500412100030X</a>."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"das_tickbox":"0","isi":1,"article_type":"original","supplementarymaterial":"no","file":[{"date_updated":"2021-12-01T14:01:54Z","file_name":"2021_MathProcCamPhilSoc_Bonolis.pdf","creator":"cchlebak","access_level":"open_access","success":1,"file_id":"10395","checksum":"614d2e9b83a78100408e4ee7752a80a8","relation":"main_file","file_size":334064,"content_type":"application/pdf","date_created":"2021-12-01T14:01:54Z"}],"intvolume":"       172","publisher":"Cambridge University Press","issue":"3"}]