Back to Search Start Over

ON THE SIZE-RAMSEY NUMBER OF TIGHT PATHS.

Authors :
LINYUAN LU
ZHIYU WANG
Source :
SIAM Journal on Discrete Mathematics. 2018, Vol. 32 Issue 3, p2172-2179. 8p.
Publication Year :
2018

Abstract

For any r ≥ 2 and k ≥ 3, the r-color size-Ramsey number R(G,r) of a k-uniform hypergraph G is the smallest integer m such that there exists a k-uniform hypergraph H on m edges such that any coloring of the edges of H with r colors yields a monochromatic copy of G. Let Pn,k-1 (k) denote the k-uniform tight path on n vertices. Dudek et al. [J. Graph Theory, 86 (2017), pp. 104-121] showed that the size-Ramsey number of tight paths R(Pn,k-1 (k), 2) = O(nk-1-α(logn)1+α) where α = (k-2)/2k-1 +1. In this paper, we improve their bound by showing that R(Pn,k-1(k), r) = O(rk(nlogn)k/2) for all k ≥ 3 and r ≥ 2. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
08954801
Volume :
32
Issue :
3
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
132351602
Full Text :
https://doi.org/10.1137/18M1170546