Projects per year
Abstract
The rcolor sizeRamsey number of a kuniform hypergraph H, denoted by R^_{r}(H), is the minimum number of edges in a kuniform hypergraph G such that for every rcoloring of the edges of G there exists a monochromatic copy of H. In the case of 2uniform 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. In a recent breakthrough result, Letzter, Pokrovskiy, and Yepremyan gave a linear upper bound on the rcolor sizeRamsey number of the kuniform tight path P^{(k)}_{n}; i.e. R^_{r}(P^{(k)}_{n})=O_{r,k}(n). Winter gave the first nontrivial lower bounds on the 2color sizeRamsey number of P^{(k)}_{n} for k≥3; i.e. R^_{2}(P^{(3)}_{n})≥8/3n−O(1) and R^_{2}(P^{(k)}_{n})≥⌈log_{2}(k+1)⌉n−O_{k}(1) for k≥4.
We consider the problem of giving a lower bound on the rcolor sizeRamsey number of P(k)n (for fixed k and growing r). Our main result is that R^_{r}(P^{(k)}_{n})=Ω_{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 rcolor sizeRamsey 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 kuniform paths P^{(k,ℓ)}_{n}. In particular we note that when 1≤ℓ≤k/2, we have Ω_{k}(r^{2}n)=R^_{r}(P(^{k,ℓ)}_{n})=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 R^_{2}(P^{(3)}_{n})≥28/9n−O(1), improving on the abovementioned lower bound of Winter in the case k=3.
We consider the problem of giving a lower bound on the rcolor sizeRamsey number of P(k)n (for fixed k and growing r). Our main result is that R^_{r}(P^{(k)}_{n})=Ω_{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 rcolor sizeRamsey 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 kuniform paths P^{(k,ℓ)}_{n}. In particular we note that when 1≤ℓ≤k/2, we have Ω_{k}(r^{2}n)=R^_{r}(P(^{k,ℓ)}_{n})=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 R^_{2}(P^{(3)}_{n})≥28/9n−O(1), improving on the abovementioned lower bound of Winter in the case k=3.
Original language  English 

Article number  103969 
Number of pages  14 
Journal  European Journal of Combinatorics 
Volume  120 
Early online date  12 Apr 2024 
DOIs  
Publication status  Published  Aug 2024 
Bibliographical note
Funding:1. Research supported in part by U.S. National Science Foundation grant DMS1954170.
2. The research leading to these results was supported by EPSRC, United Kingdom, grant no. EP/V002279/1 and EP/V048287/1. There are no additional data beyond that contained within the main manuscript.
Fingerprint
Dive into the research topics of 'A lower bound on the multicolor sizeRamsey numbers of paths in hypergraphs'. Together they form a unique fingerprint.
Ramsey theory: an extremal perspective
Engineering & Physical Science Research Council
1/01/22 → 31/12/24
Project: Research Councils

Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils