Ramsey Problems for Berge Hypergraphs

Gerbner, Dániel and Methuku, Abhishek and Omidi, Gholamreza and Vizer, Máté (2020) Ramsey Problems for Berge Hypergraphs. SIAM Journal on Discrete Mathematics, 34 (1). pp. 351-369. ISSN 0895-4801

	Text SIAM Journal on Discrete Mathematics Volume 34 issue 1 2020 Ramsey Problems for Berge Hypergraphs.pdf Restricted to Repository staff only Download (414kB)
Preview	Text (arXiv preprint) 1808.10434.pdf Download (262kB) | Preview

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) \rightarrow 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^rG$. For families of r-uniform hypergraphs $\mathbf{H}$ and $\mathbf{H}'$, we denote by $R(\mathbf{H},\mathbf{H}')$ the smallest number n such that in any red-blue coloring of the (hyper)edges 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}'$. $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^rK_n)=n$. In the case r = 2c, we show that $R^c(B^rK_n)=n+1$, and if G is a noncomplete graph on n vertices, then $R^c(B^rG)=n$, assuming n is large enough. In the case $r < 2c$ we also obtain bounds on $R^c(B^rK_n)$. Moreover, we also determine the exact value of $R(B^3T_1,B^3T_2)$ for every pair of trees T_1 and T_2. Read More: https://epubs.siam.org/doi/abs/10.1137/18M1225227?journalCode=sjdmec

Actions (login required)

Edit Item