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 条
  • [21] Threshold Protocol Game on Graphs with Magic Square-Generalization Labelings
    Fedrigo, Alexandra
    GAMES, 2024, 15 (06):
  • [22] Upper bounds on the non-3-colourability threshold of random graphs
    Fountoulakis, N
    McDiarmid, C
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2002, 5 (01): : 205 - 225
  • [23] On the threshold: the emergence of reflexivity. Constructing relationships within ethnographic studies on families
    Padiglione, Vincenzo
    Fatigante, Marilena
    Giorgi, Sabina
    RIVISTA DI PSICOLINGUISTICA APPLICATA-JOURNAL OF APPLIED PSYCHOLINGUISTICS, 2007, 7 (03): : 53 - 79
  • [24] Ligand/receptor signaling threshold (LIST) model accounts for gp130-mediated embryonic stem cell self-renewal responses to LIF and HIL-6
    Viswanathan, S
    Benatar, T
    Rose-John, S
    Lauffenburger, DA
    Zandstra, PW
    STEM CELLS, 2002, 20 (02) : 119 - 138