标题： Kohayakawa-Kreuter猜想的解决 显示英文标题

标题： Resolution of the Kohayakawa-Kreuter conjecture

摘要： 一个图$G$被称为对于图的元组$(H_1,\dots,H_r)$是Ramsey的，如果每个$r$-颜色的边的$G$包含一个颜色为$i$的$H_i$的单色副本，对于某个$i$。 一个在Ramsey理论和随机图理论交汇处的基本问题是确定二项式随机图$G_{n,p}$变成几乎必然Ramsey的阈值，对于固定的元组$(H_1,\dots,H_r)$，Kohayakawa和Kreuter的一个著名猜想预测了这个阈值。Mousset-Nenadov-Samotij、Bowtell-Hancock-Hyde和Kuperwasser-Samotij-Wigderson的早期工作将这个概率问题简化为一个确定性图分解猜想。在本文中，我们解决了这个确定性问题，从而证明了Kohayakawa-Kreuter猜想。在此过程中，我们证明了一些新颖的图分解结果，这些结果可能具有独立的兴趣。 显示英文摘要

摘要： A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph $G_{n,p}$ becomes a.a.s. Ramsey for a fixed tuple $(H_1,\dots,H_r)$, and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset-Nenadov-Samotij, Bowtell-Hancock-Hyde, and Kuperwasser-Samotij-Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this paper, we resolve this deterministic problem, thus proving the Kohayakawa-Kreuter conjecture. Along the way, we prove a number of novel graph decomposition results which may be of independent interest.