RAMSEY PROBLEMS FOR BERGE HYPERGRAPHS

Abstract

For a graph G, a hypergraph \scrH is a Berge copy of G (or a Berge-G in short) if there is a bijection f : E(G) \rightarrow E(\scrH ) such that for each e \in E(G) we have e \subseteq f(e). We denote the family of r-uniform hypergraphs that are Berge copies of G by BrG. For families of r-uniform hypergraphs H and H\prime , we denote by R(H,H\prime ) the smallest number n such that in any red-blue coloring of the (hyper)edges of \scrK rn (the complete r-uniform hypergraph on n vertices) there is a monochromatic blue copy of a hypergraph in H or a monochromatic red copy of a hypergraph in H\prime . Rc(H) denotes the smallest number n such that in any coloring of the hyperedges of \scrK rn with c colors, there is a monochromatic copy of a hypergraph in H. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if r > 2c, then Rc(BrKn) = n. In the case r = 2c, we show that Rc(BrKn) = n+1, and if G is a noncomplete graph on n vertices, then Rc(BrG) = n, assuming n is large enough. In the case r < 2c we also obtain bounds on Rc(BrKn). Moreover, we also determine the exact value of R(B3T1,B3T2) for every pair of trees T1 and T2.