The size-Ramsey Number of 3-uniform tight paths
Han, Jie; Kohayakawa, Yoshiharu; Letzter, Shoham; Mota, Guilherme Oliveira; and Parczyk, Olaf
(2021)
The size-Ramsey Number of 3-uniform tight paths.
Advances in Combinatorics, 2021 (1): 5.
ISSN 2517-5599
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).
| Item Type | Article |
|---|---|
| Keywords | hypergraph,size-Ramsey number,tight path |
| Departments | Mathematics |
| DOI | 10.19086/aic.24581 |
| Date Deposited | 07 Apr 2022 11:30 |
| URI | https://researchonline.lse.ac.uk/id/eprint/114616 |
