Ramsey problems for berge hypergraphs

Daniel Gerbner, Abhishek Methuku, Gholamreza Omidi, Mate Vizer

Research output: Contribution to journalArticlepeer-review

Abstract

For a graph G, a hypergraph scrH is a Berge copy of G (or a Berge-G in short) if there is a bijection f: E(G) rightarrow E(scrH ) such that for eache in E(G) we have esubseteq f(e). We denote the family of r-uniform hypergraphs that are Berge copies of G by BrG. For families of r-uniform hypergraphs H and Hprime, we denote by R(H, Hprime ) the smallest number n such that in any red-blue coloring of the (hyper)edges ofscrK nr (the complete r-uniform hypergraph on n vertices) there is a monochromatic blue copy of a hypergraph in H or a monochromatic red copy of a hypergraph in H\prime. Rc(H) denotes the smallest number n such that in any coloring of the hyperedges of scrK nr with c colors, there is a monochromatic copy of a hypergraph in H. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if r > 2c, then Rc(BrKn) = n. In the case r = 2c, we show that Rc(BrKn) = n+ 1, and if G is a noncomplete graph on n vertices, then Rc(BrG) = n, assuming n is large enough. In the case r < 2c we also obtain bounds on Rc(BrKn). Moreover, we also determine the exact value of R(B3T1, B3T2) for every pair of trees T1 and T2,.

Original languageEnglish (US)
Pages (from-to)351-369
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number1
DOIs
StatePublished - 2020
Externally publishedYes

Keywords

  • Berge hypergraphs
  • Hypergraphs
  • Ramsey theory

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Ramsey problems for berge hypergraphs'. Together they form a unique fingerprint.

Cite this