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. 351369. ISSN 08954801
Text
SIAM Journal on Discrete Mathematics Volume 34 issue 1 2020 Ramsey Problems for Berge Hypergraphs.pdf Restricted to Repository staff only Download (414kB) 


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 BergeG 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 runiform hypergraphs that are Berge copies of G by $B^rG$. For families of runiform hypergraphs $\mathbf{H}$ and $\mathbf{H}'$, we denote by $R(\mathbf{H},\mathbf{H}')$ the smallest number n such that in any redblue coloring of the (hyper)edges of $\mathcal{K}_n^r$ (the complete runiform 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
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
Depositing User:  Máté Vizer 
Date Deposited:  28 Sep 2020 13:12 
Last Modified:  28 Sep 2020 13:12 
URI:  http://real.mtak.hu/id/eprint/115184 
Actions (login required)
Edit Item 