The Size-Ramsey Number of 3-uniform Tight Paths

Jie Han; Yoshiharu Kohayakawa; Shoham Letzter; Guilherme Oliveira Mota; Olaf Parczyk

doi:10.19086/aic.24581

The Size-Ramsey Number of 3-uniform Tight Paths

Jie Han, Yoshiharu Kohayakawa, Shoham Letzter, Guilherme Oliveira Mota, Olaf Parczyk

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

Given a hypergraph H, the size-Ramsey number ˆr₂(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⁽³⁾ is linear in n, i.e., ˆr₂(Pn⁽³⁾) = 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 ˆr₂(Pn⁽³⁾) = O(n^3/2 log^3/2 n).

Original language	English
Article number	5
Journal	Advances in Combinatorics
Volume	2021
Issue number	1
DOIs	https://doi.org/10.19086/aic.24581
Publication status	Published - 2021

Keywords

Hypergraph
Size-Ramsey number
Tight path

Access to Document

10.19086/aic.24581

Cite this

Han, J., Kohayakawa, Y., Letzter, S., Mota, G. O., & Parczyk, O. (2021). The Size-Ramsey Number of 3-uniform Tight Paths. Advances in Combinatorics, 2021(1), Article 5. https://doi.org/10.19086/aic.24581

@article{f17ed52607ca46f5a0f55a093e726093,

title = "The Size-Ramsey Number of 3-uniform Tight Paths",

abstract = "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{\"o}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).",

keywords = "Hypergraph, Size-Ramsey number, Tight path",

author = "Jie Han and Yoshiharu Kohayakawa and Shoham Letzter and Mota, {Guilherme Oliveira} and Olaf Parczyk",

note = "Publisher Copyright: {\textcopyright} 2021 Jie Han, Yoshiharu Kohayakawa, Shoham Letzter, Guilherme Oliveira Mota and Olaf Parczyk cb Licensed under a Creative Commons Attribution License (CC-BY).",

year = "2021",

doi = "10.19086/aic.24581",

language = "English",

volume = "2021",

journal = "Advances in Combinatorics",

issn = "2517-5599",

publisher = "Alliance of Diamond OA Journals",

number = "1",

}

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

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 -

The Size-Ramsey Number of 3-uniform Tight Paths

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this