The size-Ramsey number of cubic graphs

被引：5
作者：
Conlon, David [1 ]
Nenadov, Rajko [2 ]
Trujic, Milos [3 ]
机构：
[1] CALTECH, Dept Math, Pasadena, CA USA
[2] Google Zurich, Brandschenkestr 110, CH-8002 Zurich, Switzerland
[3] Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland
来源：
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY | 2022年 / 54卷 / 06期
基金：
瑞士国家科学基金会;
关键词：
K-4-FREE SUBGRAPHS; POWERS;
D O I：
10.1112/blms.12682
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the size-Ramsey number of any cubic graph with n vertices is O(n(8/5)), improving a bound of n5(/3+o(1)) due to Kohayakawa, Rodl, Schacht, and Szemeredi. The heart of the argument is to show that there is a constant C such that a random graph with Cn vertices where every edge is chosen independently with probability p >= Cn-(2/5) is with high probability Ramsey for any cubic graph with n vertices. This latter result is best possible up to the constant.
引用
收藏
页码：2135 / 2150
页数：16
相关论文
共 33 条
  • [1] SPANNING SUBGRAPHS OF RANDOM GRAPHS
    ALON, N
    FUREDI, Z
    [J]. GRAPHS AND COMBINATORICS, 1992, 8 (01) : 91 - 94
  • [2] Alon N, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P373
  • [3] Balogh J, 2015, J AM MATH SOC, V28, P669
  • [4] ON SIZE RAMSEY NUMBER OF PATHS, TREES, AND CIRCUITS .1.
    BECK, J
    [J]. JOURNAL OF GRAPH THEORY, 1983, 7 (01) : 115 - 129
  • [5] Beck J., 1990, MATH RAMSEY THEORY, V5, P34
  • [6] The size-Ramsey number of powers of bounded degree trees
    Berger, Soeren
    Kohayakawa, Yoshiharu
    Maesaka, Giulia Satiko
    Martins, Taisa
    Mendonca, Walner
    Mota, Guilherme Oliveira
    Parczyk, Olaf
    [J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2021, 103 (04): : 1314 - 1332
  • [7] THE RAMSEY NUMBER OF A GRAPH WITH BOUNDED MAXIMUM DEGREE
    CHVATAL, C
    RODL, V
    SZEMEREDI, E
    TROTTER, WT
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (03) : 239 - 243
  • [8] On the size-Ramsey number of grid graphs
    Clemens, Dennis
    Miralaei, Meysam
    Reding, Damian
    Schacht, Mathias
    Taraz, Anusch
    [J]. COMBINATORICS PROBABILITY AND COMPUTING, 2021, 30 (05) : 670 - 685
  • [9] The size-Ramsey number of powers of paths
    Clemens, Dennis
    Jenssen, Matthew
    Kohayakawa, Yoshiharu
    Morrison, Natasha
    Mota, Guilherme Oliveira
    Reding, Damian
    Roberts, Barnaby
    [J]. JOURNAL OF GRAPH THEORY, 2019, 91 (03) : 290 - 299
  • [10] ON THE KLR CONJECTURE IN RANDOM GRAPHS
    Conlon, D.
    Gowers, W. T.
    Samotij, W.
    Schacht, M.
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 2014, 203 (01) : 535 - 580
1234