On induced Ramsey numbers for k‐uniform hypergraphs1. Issue 1 (17th February 2015) - Dellamonica, Domingos; La Fleur, Steven; Rödl, Vojtěch
Abstract: Let K t, …, t ( k ) denote the complete k ‐uniform k ‐partite hypergraph with classes of size t and K s ( k ) the complete k ‐uniform hypergraph of order s . One can show that the Ramsey number for K t, …, t ( k ) and K s ( k ) satisfies s c 1 t k − 1 ≤ r ( K t, …, t ( k ), K s ( k ) ) ≤ s c 2 t k − 1 when 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 ) satisfies r ind ( T, S ) ≤ 2 O ( t 2 k s k ( k − 1 ) ) . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016