### BROWSE

#### Related Scientist

Abhishek, Methuku
이산수학 그룹

RAMSEY PROBLEMS FOR BERGE HYPERGRAPHS

Cited 0 time in Cited 0 time in
Title
RAMSEY PROBLEMS FOR BERGE HYPERGRAPHS
Author(s)
; ; ;
Publication Date
2020-02
Journal
SIAM Journal on Discrete Mathematics, v.34, no.1, pp.351 - 369
Publisher
Society for Industrial and Applied Mathematics
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 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 BrG. For families of r-uniform hypergraphs H and H\prime , we denote by R(H,H\prime ) the smallest number n such that in any red-blue coloring of the (hyper)edges of \scrK rn (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 rn 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.
URI
https://pr.ibs.re.kr/handle/8788114/12414
DOI
10.1137/18M1225227
ISSN
0895-4801
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.