Ramsey numbers of berge-hypergraphs and related structures

Nika Salia, Casey Tompkins, Zhiyu Wang, Oscar Zamora

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

For a graph G = (V, E), a hypergraph H is called a Berge-G, denoted by BG, if there is an injection i: V (G) → V (H) and a bijection f: E(G) → E(H) such that for all e = uv ∈ E(G), we have {i(u), i(v)} ⊆ f(e). Let the Ramsey number Rr (BG, BG) be the smallest integer n such that for any 2-edge-coloring of a complete r-uniform hypergraph on n vertices, there is a monochromatic Berge-G subhypergraph. In this paper, we show that the 2-color Ramsey number of Berge cliques is linear. In particular, we show that R3 (BKs, BKt) = s + t − 3 for s, t ≥ 4 and max{s, t} ≥ 5 where BKn is a Berge-Kn hypergraph. For higher uniformity, we show that R4 (BKt, BKt) = t + 1 for t ≥ 6 and Rk (BKt, BKt) = t for k ≥ 5 and t sufficiently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs.

Original languageEnglish
Article numberP4.40
JournalElectronic Journal of Combinatorics
Volume26
Issue number4
DOIs
StatePublished - 2019
Externally publishedYes

Bibliographical note

Publisher Copyright:
©The authors.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Ramsey numbers of berge-hypergraphs and related structures'. Together they form a unique fingerprint.

Cite this