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 条
  • [1] The anti-Ramsey threshold of complete graphs
    Kohayakawa, Yoshiharu
    Mota, Guilherme Oliveira
    Parczyk, Olaf
    Schnitzer, Jakob
    DISCRETE MATHEMATICS, 2023, 346 (05)
  • [2] Anti-Ramsey Threshold of Cycles for Sparse Graphs
    Barros, G. F.
    Cavalar, B. P.
    Mota, G. O.
    Parczyk, O.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 89 - 98
  • [3] On an anti-Ramsey threshold for sparse graphs with one triangle
    Kohayakawa, Y.
    Konstadinidis, P. B.
    Mota, G. O.
    JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 176 - 187
  • [4] A RAMSEY THEOREM FOR BIASED GRAPHS
    Nelson, Peter
    Park, Sophia
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (04) : 2270 - 2281
  • [5] Classes of graphs that are not vertex Ramsey
    Kierstead, HA
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1997, 10 (03) : 373 - 380
  • [6] Constrained Ramsey numbers of graphs
    Jamison, RE
    Jiang, T
    Ling, ACH
    JOURNAL OF GRAPH THEORY, 2003, 42 (01) : 1 - 16
  • [7] Anti-Ramsey threshold of cycles?
    Barros, Gabriel Ferreira
    Cavalar, Bruno Pasqualotto
    Mota, Guilherme Oliveira
    Parczyk, Olaf
    DISCRETE APPLIED MATHEMATICS, 2022, 323 : 228 - 235
  • [8] On vertex Ramsey graphs with forbidden subgraphs
    Diskin, Sahar
    Hoshen, Ilay
    Krivelevich, Michael
    Zhukovskii, Maksim
    DISCRETE MATHEMATICS, 2024, 347 (03)
  • [9] The minimum degree of Ramsey-Minimal graphs
    Fox, Jacob
    Lin, Kathy
    JOURNAL OF GRAPH THEORY, 2007, 54 (02) : 167 - 177
  • [10] DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS
    Barros, Gabriel Ferreira
    Cavalar, Bruno Pasqualotto
    Kohayakawa, Yoshiharu
    Mota, Guilherme Oliveira
    Naia, Tassio
    RAIRO-OPERATIONS RESEARCH, 2024, 58 (04) : 3607 - 3619