On the size-Ramsey number of grids

被引：1
作者：
Conlon, David [1 ]
Nenadov, Rajko [2 ]
Trujic, Milos [3 ]
机构：
[1] CALTECH, Dept Math, Pasadena, CA 91125 USA
[2] Univ Auckland, Sch Comp Sci, Auckland, New Zealand
[3] Swiss Fed Inst Technol, Inst Theoret Comp Sci, CH-8092 Zurich, Switzerland
来源：
COMBINATORICS PROBABILITY AND COMPUTING | 2023年 / 32卷 / 06期
基金：
瑞士国家科学基金会;
关键词：
Ramsey theory; random graphs; grid graph; GRAPHS; POWERS;
D O I：
10.1017/S0963548323000147
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the size-Ramsey number of the root n x root n grid graph is O(n(5/4)), improving a previous bound of n(3/2+o(1)) by Clemens, Miralaei, Reding, Schacht, and Taraz.
引用
收藏
页码：874 / 880
页数：7
相关论文
共 50 条
  • [21] The size Ramsey number of short subdivisions of bounded degree graphs
    Kohayakawa, Yoshiharu
    Retter, Troy
    Rodl, Vojtech
    RANDOM STRUCTURES & ALGORITHMS, 2019, 54 (02) : 304 - 339
  • [22] The chromatic Ramsey number of odd wheels
    Paul, Nathalie
    Tardif, Claude
    JOURNAL OF GRAPH THEORY, 2012, 69 (02) : 198 - 205
  • [23] ONLINE SIZE RAMSEY NUMBER FOR C4 AND P6
    Litka, Mateusz
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) : 1607 - 1615
  • [24] On the Ramsey number of the triangle and the cube
    Griffiths, Simon
    Morris, Robert
    Pontiveros, Gonzalo Fiz
    Saxton, David
    Skokan, Jozef
    COMBINATORICA, 2016, 36 (01) : 71 - 89
  • [25] Three Early Problems on Size Ramsey Numbers
    Conlon, David
    Fox, Jacob
    Wigderson, Yuval
    COMBINATORICA, 2023, 43 (4) : 743 - 768
  • [26] The Ramsey number of the clique and the hypercube
    Pontiveros, Gonzalo Fiz
    Griffiths, Simon
    Morris, Robert
    Saxton, David
    Skokan, Jozef
    JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2014, 89 : 680 - 702
  • [27] Chromatic number is Ramsey distinguishing
    Savery, Michael
    JOURNAL OF GRAPH THEORY, 2022, 99 (01) : 152 - 161
  • [28] The Tripartite Ramsey Number for Trees
    Bottcher, Julia
    Hladky, Jan
    Piguet, Diana
    JOURNAL OF GRAPH THEORY, 2012, 69 (04) : 264 - 300
  • [29] Directed Ramsey number for trees
    Bucic, Matija
    Letzter, Shoham
    Sudakov, Benny
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 137 : 145 - 177
  • [30] Size bipartite Ramsey numbers
    Sun, Yuqin
    Li, Yusheng
    DISCRETE MATHEMATICS, 2009, 309 (05) : 1060 - 1066
12345