On induced Ramsey numbers for k ‐uniform hypergraphs

LetK t , … , t ( k )denote the complete k ‐uniform k ‐partite hypergraph with classes of size t andK s ( k )the complete k ‐uniform hypergraph of order s . One can show that the Ramsey number forK t , … , t ( k )andK s ( k )satisfiess c 1 t k − 1≤ r ( K t , … , t ( k ) ,   K s ( k ) ) ≤ s c 2 t k − 1when t = s o (1) as s → ∞ . The main part of this paper gives an analogous result for induced Ramsey numbers: Let T be an arbitrary k ‐partite k ‐uniform hypergraph with classes of size t and S an arbitrary k ‐graph of order s . We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph ℛ ,   | V ( ℛ ) | = n such that any red/blue coloring of ℛ yields either an induced red copy of T or an induced blue copy of S ) satisfiesr ind ( T , S ) ≤ 2 O ( t 2 ks k ( k − 1 ) ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016