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 -