On generalized Ramsey numbers for 3-uniform hypergraphs

Original · EN

The well-known Ramsey number r(t,u) is the smallest integer n such that every Kₜ-free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd os and Rogers introduced a more general problem replacing K₂ by Kₛ for 2≤ s<t. Extending the problem of determining Ramsey numbers they defined the numbers fₛ,ₜ(n)= { {|W|: W V(G) and G[W] contains no Kₛ}}, where the minimum is taken over all Kₜ-free graphs G of order n. In this note, we study an analogous function fₛ,ₜ⁽³⁾(n) for 3-uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that c₁(n)¹/⁴ (n/ n)¹/² < fₛ, ₛ₊₁⁽³⁾(n) < c₂ n.