Premium
On induced Ramsey numbers for k ‐uniform hypergraphs
Author(s) -
Dellamonica Domingos,
La Fleur Steven,
Rödl Vojtěch
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20580
Subject(s) - hypergraph , ramsey's theorem , combinatorics , mathematics , order (exchange) , probabilistic logic , graph , discrete mathematics , ramsey theory , statistics , finance , economics
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