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) over cap (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 Omega(r(2)n) = (R) over cap (r)(P-n) = O((r(2) log r)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-n((k)); i.e. (R) over cap (r)(P-n((k)))=O-r,O-k(n). Winter gave the first non-trivial lower bounds on the 2-color size-Ramsey number of P-n((k)) for k >= 3; i.e. (R) over cap (2)(P-n((3))) >= 8/3n - O(1) and (R) over cap (P-n((k))) >= (sic)log(2)(k + 1)(sic) 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-n((k)) (for fixed k and growing r). Our main result is that (R) over cap (r)(P-n((k))) = Omega(k)(r(k)n) 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) over cap (r)(P-k+m((k))) = Theta(k)(r(m)) 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 l-overlapping k-uniform paths P-n((k,l)). In particular we note that when 1 <= l <= k/2, we have Omega(k)(r(2)n) = (R) over cap (r)(P-n(()(k,l)) = O((r(2) log r)n) which essentially matches the best known bounds for graphs mentioned above. Additionally, in the case k = 3, l = 2, and r = 2, we give a more precise estimate which implies (R) over cap (2)(P-n((3))) >= 28/9n - O(1), improving on the above-mentioned lower bound of Winter in the case k = 3. (c) 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).