TY - JOUR

T1 - The Size-Ramsey Number of 3-uniform Tight Paths

AU - Han, Jie

AU - Kohayakawa, Yoshiharu

AU - Letzter, Shoham

AU - Mota, Guilherme Oliveira

AU - Parczyk, Olaf

N1 - Publisher Copyright:
© 2021 Jie Han, Yoshiharu Kohayakawa, Shoham Letzter, Guilherme Oliveira Mota and Olaf Parczyk cb Licensed under a Creative Commons Attribution License (CC-BY).

PY - 2021

Y1 - 2021

N2 - Given a hypergraph H, the size-Ramsey number ˆr2(H) is the smallest integer m such that there exists a hypergraph G with m edges with the property that in any colouring of the edges of G with two colours there is a monochromatic copy of H. We prove that the size-Ramsey number of the 3-uniform tight path on n vertices Pn(3) is linear in n, i.e., ˆr2(Pn(3)) = O(n). This answers a question by Dudek, La Fleur, Mubayi, and Rödl for 3-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417–434], who proved ˆr2(Pn(3)) = O(n3/2 log3/2 n).

AB - Given a hypergraph H, the size-Ramsey number ˆr2(H) is the smallest integer m such that there exists a hypergraph G with m edges with the property that in any colouring of the edges of G with two colours there is a monochromatic copy of H. We prove that the size-Ramsey number of the 3-uniform tight path on n vertices Pn(3) is linear in n, i.e., ˆr2(Pn(3)) = O(n). This answers a question by Dudek, La Fleur, Mubayi, and Rödl for 3-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417–434], who proved ˆr2(Pn(3)) = O(n3/2 log3/2 n).

KW - Hypergraph

KW - Size-Ramsey number

KW - Tight path

UR - http://www.scopus.com/inward/record.url?scp=85106358788&partnerID=8YFLogxK

U2 - 10.19086/aic.24581

DO - 10.19086/aic.24581

M3 - Article

AN - SCOPUS:85106358788

SN - 2517-5599

VL - 2021

JO - Advances in Combinatorics

JF - Advances in Combinatorics

IS - 1

M1 - 5

ER -