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 条
  • [1] On the Size-Ramsey Number of Hypergraphs
    Dudek, Andrzej
    La Fleur, Steven
    Mubayi, Dhruv
    Rodl, Vojtech
    JOURNAL OF GRAPH THEORY, 2017, 86 (01) : 104 - 121
  • [2] The vertex size-Ramsey number
    Dudek, Andrzej
    Lesniak, Linda
    DISCRETE MATHEMATICS, 2016, 339 (06) : 1753 - 1762
  • [3] The size-Ramsey number of short subdivisions
    Draganic, Nemanja
    Krivelevich, Michael
    Nenadov, Rajko
    RANDOM STRUCTURES & ALGORITHMS, 2021, 59 (01) : 68 - 78
  • [4] The size-Ramsey number of trees
    Dellamonica, Domingos, Jr.
    RANDOM STRUCTURES & ALGORITHMS, 2012, 40 (01) : 49 - 73
  • [5] The size-Ramsey number of cubic graphs
    Conlon, David
    Nenadov, Rajko
    Trujic, Milos
    BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2022, 54 (06) : 2135 - 2150
  • [6] The size-Ramsey number of powers of paths
    Clemens, Dennis
    Jenssen, Matthew
    Kohayakawa, Yoshiharu
    Morrison, Natasha
    Mota, Guilherme Oliveira
    Reding, Damian
    Roberts, Barnaby
    JOURNAL OF GRAPH THEORY, 2019, 91 (03) : 290 - 299
  • [7] The multicolour size-Ramsey number of powers of paths
    Han, Jie
    Jenssen, Matthew
    Kohayakawa, Yoshiharu
    Mota, Guilherme Oliveira
    Roberts, Barnaby
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 145 : 359 - 375
  • [8] THE SIZE-RAMSEY NUMBER OF POWERS OF BOUNDED DEGREE TREES
    Berger, S.
    Kohayakawa, Y.
    Maesaka, G. S.
    Martins, T.
    Mendonca, W.
    Mota, G. O.
    Parczyk, O.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 451 - 456
  • [9] New lower bounds on the size-Ramsey number of a path
    Bal, Deepak
    DeBiasio, Louis
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (01)
  • [10] A note on the size-Ramsey number of long subdivisions of graphs
    Donadelli, J
    Haxell, PE
    Kohayakawa, Y
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2005, 39 (01): : 191 - 206
12345