On the cover Ramsey number of Berge hypergraphs

Abstract

For a fixed set of positive integers $R$, we say $\mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $\mathcal{H}$ is \emph{covering} if every vertex pair of $\mathcal{H}$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a \textit{Berge}-$G$, denoted by $BG$, if there exists an injection $f:E(G)\to E(\mathcal{H})$ such that for every $e\in E(G)$, $e\subseteq f(e)$. In this note, we define a new type of Ramsey number, namely the \emph{cover Ramsey number}, denoted as ${\hat{R}}^R(B{G}_1,B{G}_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $\mathcal{H}$ on $n\ge n_0$ vertices and every $2$-edge-coloring (blue and red) of $\mathcal{H}$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $k\ge 2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1,G_2)\le {\hat{R}}^{[k]}(B{G}_1,B{G}_2)\le c_k\cdot R(G_1,G_2{)}^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c=c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then ${\hat{R}}^{[k]}(BG,BG)\le cn$.

9 pages

References in corpus (4)

• Avoiding long Berge cycles
• Avoiding long Berge cycles, the missing cases $k=r+1$ and $k=r+2$
• A note on Ramsey numbers for Berge-G hyper graphs
• On Hamiltonian Berge cycles in $3$-uniform hypergraphs