Ramsey problems for Berge hypergraphs

DOI10.1137/18M1225227MaRDI QIDQ5215899zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Abhishek Methuku, Gholamreza Omidi, Máté Vizer

Publication date 13 February 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.10434

zbMATH Keywords

Berge hypergraphs hypergraphs Ramsey theory

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: For a graph

G

, a hypergraph

m a t h c a l H

is a Berge copy of

G

(or a Berge-

G

in short), if there is a bijection

f : E (G) i g h t a r r o w E (m a t h c a l H)

such that for each

e i n E (G)

we have

e s u b s e t e q f (e)

. We denote the family of

r

-uniform hypergraphs that are Berge copies of

G

by

B^{r} G

. For families of

r

-uniform hypergraphs

m a t h b f H

and

m a t h b f H^{'}

, we denote by

R (m a t h b f H, m a t h b f H^{'})

the smallest number

n

such that in any blue-red coloring of

m a t h c a l K_{n}^{r}

(the complete

r

-uniform hypergraph on

n

vertices) there is a monochromatic blue copy of a hypergraph in

m a t h b f H

or a monochromatic red copy of a hypergraph in

m a t h b f H^{'}

.

R^{c} (m a t h b f H)

denotes the smallest number

n

such that in any coloring of the hyperedges of

m a t h c a l K_{n}^{r}

with

c

colors, there is a monochromatic copy of a hypergraph in

m a t h b f H

. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if

r > 2 c

, then

R^{c} (B^{r} K_{n}) = n

. In the case

r = 2 c

, we show that

R^{c} (B^{r} K_{n}) = n + 1

, and if

G

is a non-complete graph on

n

vertices, then

R^{c} (B^{r} G) = n

, assuming

n

is large enough. In the case

r < 2 c

we also obtain bounds on

R^{c} (B^{r} K_{n})

. Moreover, we also determine the exact value of

R (B^{3} T_{1}, B^{3} T_{2})

for every pair of trees

T_{1}

and

T_{2}

.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Ramsey problems for Berge hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215899)