BROWSE

Related Scientist

Abhishek, Methuku's photo.

Abhishek, Methuku
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

RAMSEY PROBLEMS FOR BERGE HYPERGRAPHS

Cited 0 time in webofscience Cited 0 time in scopus
43 Viewed 0 Downloaded
Title
RAMSEY PROBLEMS FOR BERGE HYPERGRAPHS
Author(s)
Gerbner, D; Abhishek Methuku; Omidi, G; Vizer, M
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.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse