## Abstract

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^{2}n)=Rˆ_{r}(P_{n})=O((r^{2}logr)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 P_{n}^{(k)}; i.e. Rˆ_{r}(P_{n}^{(k)})=O_{r,k}(n). At about the same time, Winter (2023) gave the first non-trivial lower bounds on the 2-color size-Ramsey number of P_{n}^{(k)} for k≥3; i.e. [Forrmula presented] and Rˆ_{2}(P_{n}^{(k)})≥log_{2}(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_{n}^{(k)} (for fixed k and growing r). Our main result is that Rˆ_{r}(P_{n}^{(k)})=Ω_{k}(r^{k}n) 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}(P_{k+m}^{(k)})=Θ_{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 ℓ-overlapping k-uniform paths P_{n}^{(k,ℓ)}. In particular we note that when [Forrmula presented], we have Ω_{k}(r^{2}n)=Rˆ_{r}(P_{n}^{(k,ℓ)})=O((r^{2}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 [Forrmula presented], improving on the above-mentioned lower bound of Winter in the case k=3.

Original language | English |
---|---|

Article number | 103969 |

Journal | European Journal of Combinatorics |

Volume | 120 |

DOIs | |

State | Published - Aug 2024 |