Hypergraph Ramsey numbers: Triangles versus cliques

A celebrated result in Ramsey Theory states that the order of magnitude of the triangle-complete graph Ramsey numbers R(3, t) is ^t2/logt. In this paper, we consider an analogue of this problem for uniform hypergraphs. A triangle is a hypergraph consisting of edges e, f, g such that |e ∩ f| = |f ∩ g| = |g ∩ e| = 1 and e ∩ f ∩ g = θ For all r ≥ 2, let R(C3,Ktr) be the smallest positive integer n such that in every red-blue coloring of the edges of the complete r-uniform hypergraph Knr, there exists a red triangle or a blue Ktr. We show that there exist constants a, _{b r} > 0 such that for all t ≥ 3,at32(logt)34≤R(C3,Kt3)≤b3t32 and for r ≥ 4t32(logt)34+o(1)≤R(C3,Ktr)≤brt32. This determines up to a logarithmic factor the order of magnitude of R(C3,K_t^r). We conjecture that R(C3,Ktr)=o(t3/2) for all r ≥ 3. We also study a generalization to hypergraphs of cycle-complete graph Ramsey numbers R(_{C k}, _{K t}) and a connection to _r3(N), the maximum size of a set of integers in {1, 2, . , N} not containing a three-term arithmetic progression.