Lower bounds for Ramsey numbers of bounded degree hypergraphs
Abstract
We prove that, for all k ≥ 3, and any integers Δ, n with n ≥ Δ, there exists a k-uniform hypergraph on n vertices with maximum degree at most Δ whose 4-color Ramsey number is at least twk(ckΔ)⋅n, for some constant ck>0, where twk denotes the tower function. For k ≥ 4, this is tight up to the constant ck and for k = 3 it is known to be tight up to a factor of log Δ on top of the tower. Our bound extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from 2009 for four colors.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Topology and Set Theory
Advanced Graph Theory Research
Publication details
- Journal / source
- Journal of Combinatorial Theory Series B
- Volume
- 179
- Pages
- 250–269
- Publication date
- 10 April 2026
- Language
- EN