Premium
On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs
Author(s) -
Dudek Andrzej,
Mubayi Dhruv
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21760
Subject(s) - ramsey's theorem , combinatorics , mathematics , graph , order (exchange) , integer (computer science) , discrete mathematics , function (biology) , computer science , finance , economics , programming language , evolutionary biology , biology
The well‐known Ramsey number r ( t , u ) is the smallest integer n such that every K t ‐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 2 . Erdős and Rogers introduced a more general problem replacing K 2 by K s for 2 ≤ s < t . Extending the problem of determining Ramsey numbers they defined the numbersf s , t( n ) = min { max { | W | : W ⊆ V ( G )andG [ W ]contains noK s } } ,where the minimum is taken over all K t ‐free graphs G of order n . In this note, we study an analogous functionf s , t ( 3 )( n )for 3‐uniform hypergraphs. In particular, we show that there are constants c 1 and c 2 depending only on s such thatc 1( log n ) 1 / 4log log n log log log n1 / 2 < f s , s + 1 ( 3 )( n ) < c 2 log n .