共 24 条
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
相关论文