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 eache in E(G) we have esubseteq 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 Hprime, we denote by R(H, Hprime ) the smallest number n such that in any red-blue coloring of the (hyper)edges ofscrK nr (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 nr 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,.
Original language | English (US) |
---|---|
Pages (from-to) | 351-369 |
Number of pages | 19 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 34 |
Issue number | 1 |
DOIs | |
State | Published - 2020 |
Externally published | Yes |
Keywords
- Berge hypergraphs
- Hypergraphs
- Ramsey theory
ASJC Scopus subject areas
- General Mathematics