A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs

The r-color size-Ramsey number of a k-uniform hypergraph H, denoted by R^_r(H), is the minimum number of edges in a k-uniform hypergraph G such that for every r-coloring of the edges of G there exists a monochromatic copy of H. In the case of 2-uniform paths P_n, it is known that Ω(r²n)=R^_r(P_n)=O((r²logr)n) with the best bounds essentially due to Krivelevich. In a recent breakthrough result, Letzter, Pokrovskiy, and Yepremyan gave a linear upper bound on the r-color size-Ramsey number of the k-uniform tight path P^(k)_n; i.e. R^_r(P^(k)_n)=O_r,k(n). Winter gave the first non-trivial lower bounds on the 2-color size-Ramsey number of P^(k)_n for k≥3; i.e. R^₂(P⁽³⁾_n)≥8/3n−O(1) and R^₂(P^(k)_n)≥⌈log₂(k+1)⌉n−O_k(1) for k≥4.

We consider the problem of giving a lower bound on the r-color size-Ramsey number of P(k)n (for fixed k and growing r). Our main result is that R^_r(P^(k)_n)=Ω_k(r^kn) which generalizes the best known lower bound for graphs mentioned above. One of the key elements of our proof is a determination of the correct order of magnitude of the r-color size-Ramsey number of every sufficiently short tight path; i.e. R^_r(P^(k)_k+m) = Θ_k(r^m) for all 1≤m≤k.

All of our results generalize to ℓ-overlapping k-uniform paths P^(k,ℓ)_n. In particular we note that when 1≤ℓ≤k/2, we have Ω_k(r²n)=R^_r(P(^k,ℓ)_n)=O((r²logr)n) which essentially matches the best known bounds for graphs mentioned above. Additionally, in the case k=3, ℓ=2, and r=2, we give a more precise estimate which implies R^₂(P⁽³⁾_n)≥28/9n−O(1), improving on the above-mentioned lower bound of Winter in the case k=3.