The List-Ramsey threshold for families of graphs

被引:0
|
作者
Kuperwasser, Eden [1 ]
Samotij, Wojciech [1 ]
机构
[1] Tel Aviv Univ, Sch Math Sci, Tel Aviv, Israel
基金
以色列科学基金会; 欧洲研究理事会; 美国国家科学基金会;
关键词
Ramsey; thresholds; threshold; list-Ramsey; families; RANDOM SUBSETS;
D O I
10.1017/S0963548324000245
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Given a family of graphs $\mathcal{F}$ and an integer $r$ , we say that a graph is $r$ -Ramsey for $\mathcal{F}$ if any $r$ -colouring of its edges admits a monochromatic copy of a graph from $\mathcal{F}$ . The threshold for the classic Ramsey property, where $\mathcal{F}$ consists of one graph, in the binomial random graph was located in the celebrated work of R & ouml;dl and Ruci & nacute;ski.In this paper, we offer a twofold generalisation to the R & ouml;dl-Ruci & nacute;ski theorem. First, we show that the list-colouring version of the property has the same threshold. Second, we extend this result to finite families $\mathcal{F}$ , where the threshold statements might also diverge. This also confirms further special cases of the Kohayakawa-Kreuter conjecture. Along the way, we supply a short(-ish), self-contained proof of the $0$ -statement of the R & ouml;dl-Ruci & nacute;ski theorem.
引用
收藏
页码:829 / 851
页数:23
相关论文
共 24 条