On induced Ramsey numbers for k‐uniform hypergraphs1. Issue 1 (17th February 2015)

• Record Type: Journal Article
• Authors: Dellamonica, Domingos; La Fleur, Steven; Rödl, Vojtěch
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 5
• Page End: 20
• Publication Date: 2015-02-17
• Subjects: Ramsey -- induced -- hypergraph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20580
• Languages: English
• ISSNs: 1042-9832

Abstract

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