Ramsey numbers of Berge-hypergraphs and related structures

Abstract

For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists a bijection $f:E(G)\to E(\mathcal{H})$ such that for every $e\in E(G)$, $e\subseteq f(e)$. Let the Ramsey number $R^r(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 $R^3(B{K}_s,B{K}_t)=s+t-3$ for $s,t\ge 4$ and $\max (s,t)\ge 5$ where $B{K}_n$ is a Berge-$K_n$ hypergraph. For higher uniformity, we show that $R^4(B{K}_t,B{K}_t)=t+1$ for $t\ge 6$ and $R^k(B{K}_t,B{K}_t)=t$ for $k\ge 5$ and $t$ sufficiently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs.

Updated to include suggestions of the referee