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 Pn, it is known that Ω(r2n)=Rˆr(Pn)=O((r2logr)n) with the best bounds essentially due to Krivelevich (2019). In a recent breakthrough result, Letzter et al. (2021) gave a linear upper bound on the r-color size-Ramsey number of the k-uniform tight path Pn(k); i.e. Rˆr(Pn(k))=Or,k(n). At about the same time, Winter (2023) gave the first non-trivial lower bounds on the 2-color size-Ramsey number of Pn(k) for k≥3; i.e. Rˆ2(Pn(3))≥83n−O(1) and Rˆ2(Pn(k))≥log2(k+1)n−Ok(1) for k≥4. We consider the problem of giving a lower bound on the r-color size-Ramsey number of Pn(k) (for fixed k and growing r). Our main result is that Rˆr(Pn(k))=Ωk(rkn) which generalizes the best known lower bound for graphs mentioned above. One of the key elements of our proof turns out to be an interesting result of its own. We prove that Rˆr(Pk+m(k))=Θk(rm) for all 1≤m≤k; that is, we determine the correct order of magnitude of the r-color size-Ramsey number of every sufficiently short tight path. All of our results generalize to ℓ-overlapping k-uniform paths Pn(k,ℓ). In particular we note that when 1≤ℓ≤k2, we have Ωk(r2n)=Rˆr(Pn(k,ℓ))=O((r2logr)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ˆ2(Pn(3))≥289n−O(1), improving on the above-mentioned lower bound of Winter in the case k=3.