Ramsey problems for Berge hypergraphs

Abstract

For a graph $G$, a hypergraph $\mathcal{H}$ is a Berge copy of $G$ (or a Berge-$G$ in short), if there is a bijection $f:E(G)\to E(\mathcal{H})$ 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 $B^{r}G$. For families of $r$-uniform hypergraphs $\mathbf{H}$ and ${\mathbf{H}}^{\prime }$, we denote by $R(\mathbf{H},{\mathbf{H}}^{\prime })$ the smallest number $n$ such that in any blue-red coloring of ${\mathcal{K}}_n^r$ (the complete $r$-uniform hypergraph on $n$ vertices) there is a monochromatic blue copy of a hypergraph in $\mathbf{H}$ or a monochromatic red copy of a hypergraph in ${\mathbf{H}}^{\prime }$. $R^c(\mathbf{H})$ denotes the smallest number $n$ such that in any coloring of the hyperedges of ${\mathcal{K}}_n^r$ with $c$ colors, there is a monochromatic copy of a hypergraph in $\mathbf{H}$. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if $r>2c$, then $R^c(B^r{K}_n)=n$. In the case $r=2c$, we show that $R^c(B^r{K}_n)=n+1$, and if $G$ is a non-complete graph on $n$ vertices, then $R^c(B^{r}G)=n$, assuming $n$ is large enough. In the case $r<2c$ we also obtain bounds on $R^c(B^r{K}_n)$. Moreover, we also determine the exact value of $R(B^3{T}_1,B^3{T}_2)$ for every pair of trees $T_1$ and $T_2$.

Revised based on the suggestions of the referees