Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647417 | Discrete Mathematics | 2014 | 9 Pages |
Given an rr-uniform hypergraph HH, the multicolor Ramsey number rk(H)rk(H) is the minimum nn such that every kk-coloring of the edges of the complete rr-uniform hypergraph Knr yields a monochromatic copy of HH. We investigate rk(H)rk(H) when kk grows and HH is fixed. For nontrivial 33-uniform hypergraphs HH, the function rk(H)rk(H) ranges from 6k(1+o(1)) to double exponential in kk.We observe that rk(H)rk(H) is polynomial in kk when HH is rr-partite and at least single-exponential in kk otherwise. Erdős, Hajnal and Rado gave bounds for large cliques Ksr with s≥s0(r)s≥s0(r), showing its correct exponential tower growth. We give a proof for cliques of all sizes, s>rs>r, using a slight modification of the celebrated stepping-up lemma of Erdős and Hajnal.For 33-uniform hypergraphs, we give an infinite family with sub-double-exponential upper bound and show connections between graph and hypergraph Ramsey numbers. Specifically, we prove thatrk(K3)≤r4k(K43−e)≤r4k(K3)+1, where K43−e is obtained from K43 by deleting an edge.We provide some other bounds, including single-exponential bounds for F5={abe,abd,cde}F5={abe,abd,cde} as well as asymptotic or exact values of rk(H)rk(H) when HH is the bow {abc,ade}{abc,ade}, kite {abc,abd}{abc,abd}, tight path {abc,bcd,cde}{abc,bcd,cde} or the windmill {abc,bde,cef,bce}{abc,bde,cef,bce}. We also determine many new “small” Ramsey numbers and show their relations to designs. For example, the lower bound for r6(kite)=8r6(kite)=8 is demonstrated by decomposing the triples of a seven element set into six partial STS (two of them are Fano planes).