Hypergraph Ramsey numbers

Details Hypergraph Ramsey numbers Hypergraph Ramsey numbers

2008-08-27

arxiv.org/abs/0808.3760v1

Mathematics

Combinatorics

Scientific paper

The Ramsey number r_k(s,n) is the minimum N such that every red-blue coloring of the k-tuples of an N-element set contains either a red set of size s or a blue set of size n, where a set is called red (blue) if all 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) for k \geq 3 and s fixed. In particular, we show that r_3(s,n) \leq 2^{n^{s-2}\log n}, which improves by a factor of n^{s-2}/ polylog n the exponent of the previous upper bound of Erdos and Rado from 1952. We also obtain a new lower bound for these numbers, showing that there are constants c_1,c_2>0 such that r_3(s,n) \geq 2^{c_1 sn \log (n/s)} for all 4 \leq s \leq c_2n. When s is a constant, it gives the first superexponential lower bound for r_3(s,n), answering an open question posed by Erdos and Hajnal in 1972. Next, we consider the 3-color Ramsey number r_3(n,n,n), which is the minimum N such that every 3-coloring of the triples of an N-element set contains a monochromatic set of size n. Improving another old result of Erdos and Hajnal, we show that r_3(n,n,n) \geq 2^{n^{c \log n}}. Finally, we make some progress on related hypergraph Ramsey-type problems.

Affiliated with

Also associated with

No associations

Rating

Hypergraph Ramsey numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hypergraph Ramsey numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypergraph Ramsey numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-530030