2023/08/21 by Bradač, Domagoj, Fox, Jacob, Sudakov, Benny
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.10833
The q-color Ramsey number of a k-uniform hypergraph H is the minimum integer N such that any q-coloring of the complete k-uniform hypergraph on N vertices contains a monochromatic copy of H. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximize the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed k ≥ 3 and q ≥ 2 we prove that the largest possible q-color Ramsey number of a k-uniform hypergraph with m edges is at most twk(O(√(m))), where tw denotes the tower function. We also present a construction showing that this bound is tight for q ≥ 4. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for k ≥ 4 and the lower bound for k=3. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs.