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

Deepak Bal, Louis DeBiasio, Allan Lo

Research output: Contribution to journalArticlepeer-review


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. [Forrmula presented] 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 [Forrmula presented], 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 [Forrmula presented], improving on the above-mentioned lower bound of Winter in the case k=3.

Original languageEnglish
Article number103969
JournalEuropean Journal of Combinatorics
StatePublished - Aug 2024


Dive into the research topics of 'A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs'. Together they form a unique fingerprint.

Cite this