2023/07/31 by Eden Kuperwasser, Kuperwasser, Eden, Wojciech Samotij +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2307.16611
openalex publication_date 2023/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let us say that a graph G is Ramsey for a tuple (H1,…,Hr) of graphs if every r-coloring of the edges of G contains a monochromatic copy of Hi in color i, for some i ∈ [r]. A famous conjecture of Kohayakawa and Kreuter, extending seminal work of Rödl and Ruciński, predicts the threshold at which the binomial random graph Gn,p becomes Ramsey for (H1,…,Hr) asymptotically almost surely. In this paper, we resolve the Kohayakawa-Kreuter conjecture for almost all tuples of graphs. Moreover, we reduce its validity to the truth of a certain deterministic statement, which 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 H1,…,Hr. Additionally, we pose a natural (deterministic) graph-partitioning conjecture, which we believe to be of independent interest, and whose resolution would imply the Kohayakawa-Kreuter conjecture.