Ramsey numbers of Berge-hypergraphs and related structures

Abstract

For a graph G = (V;E), a hypergraph H is called a Berge-G, denoted by BG, if there is an injection i : V (G) ! V (H) and a bijection f : E(G) ! E(H) such that for all e = uv 2 E(G), we have fi(u); i(v)g f(e). Let the Ramsey num- ber Rr(BG;BG) be the smallest integer n such that for any 2-edge-coloring of a complete r-uniform hypergraph on n vertices, there is a monochromatic Berge-G subhypergraph. In this paper, we show that the 2-color Ramsey number of Berge cliques is linear. In particular, we show that R3(BKs;BKt) = s + t 3 for s; t > 4 and maxfs; tg > 5 where BKn is a Berge-Kn hypergraph. For higher uniformity, we show that R4(BKt;BKt) = t+1 for t > 6 and Rk(BKt;BKt) = t for k > 5 and t suciently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs. c The authors. Released under the CC BY license (International 4.0).