Hypergraph Ramsey numbers
Open Access
- 18 August 2009
- journal article
- Published by American Mathematical Society (AMS) in Journal of the American Mathematical Society
- Vol. 23 (1) , 247-266
Abstract
The Ramsey number r k ( s , n ) r_k(s,n) is the minimum N N such that every red-blue coloring of the k k -tuples of an N N -element set contains a red set of size s s or a blue set of size n n , where a set is called red (blue) if all k k -tuples from this set are red (blue). In this paper we obtain new estimates for several basic hypergraph Ramsey problems. We give a new upper bound for r k ( s , n ) r_k(s,n) for k ≥ 3 k \geq 3 and s s fixed. In particular, we show that \[ r 3 ( s , n ) ≤ 2 n s − 2 log n , r_3(s,n) \leq 2^{n^{s-2}\log n}, \] which improves by a factor of n s − 2 / polylog n n^{s-2}/\textrm {polylog}\,n the exponent of the previous upper bound of Erdős and Rado from 1952. We also obtain a new lower bound for these numbers, showing that there is a constant c > 0 c>0 such that \[ r 3 ( s , n ) ≥ 2 c s n log ( n s + 1 ) r_3(s,n) \geq 2^{c \, sn \, \log (\frac {n}{s}+1)} \] for all 4 ≤ s ≤ n 4 \leq s \leq n . For constant s s , this gives the first superexponential lower bound for r 3 ( s , n ) r_3(s,n) , answering an open question posed by Erdős and Hajnal in 1972. Next, we consider the 3 3 -color Ramsey number r 3 ( n , n , n ) r_3(n,n,n) , which is the minimum N N such that every 3 3 -coloring of the triples of an N N -element set contains a monochromatic set of size n n . Improving another old result of Erdős and Hajnal, we show that \[ r 3 ( n , n , n ) ≥ 2 n c log n . r_3(n,n,n) \geq 2^{n^{c \log n}}. \] Finally, we make some progress on related hypergraph Ramsey-type problems.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- The triangle-free processAdvances in Mathematics, 2009
- Complete r-partite subgraphs of dense r-graphsDiscrete Mathematics, 2009
- Ramsey numbers of sparse hypergraphsRandom Structures & Algorithms, 2008
- On Ramsey numbers of uniform hypergraphs with given maximum degreeJournal of Combinatorial Theory, Series A, 2006
- Two variants of the size Ramsey numberDiscussiones Mathematicae Graph Theory, 2005
- The Ramsey number R(3, t) has order of magnitude t2/log tRandom Structures & Algorithms, 1995
- Asymptotic lower bounds for Ramsey functionsDiscrete Mathematics, 1977
- On some extremal problems on r-graphsDiscrete Mathematics, 1971
- Partition relations for cardinal numbersActa Mathematica Hungarica, 1965
- Some remarks on the theory of graphsBulletin of the American Mathematical Society, 1947