BROWSE

Related Scientist

Abhishek, Methuku's photo.

Abhishek, Methuku
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs

Cited 0 time in webofscience Cited 0 time in scopus
15 Viewed 0 Downloaded
Title
Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs
Author(s)
Dániel Grósz; Abhishek Methuku; Casey Tompkins
Publication Date
2020-08
Journal
EUROPEAN JOURNAL OF COMBINATORICS, v.88, pp.103109
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Abstract
© 2020 Elsevier Ltd. Let F=(U,E) be a graph and H=(V,E) be a hypergraph. We say that H contains a Berge-F if there exist injections ψ:U→V and φ:E→E such that for every e={u,v}∈E, {ψ(u),ψ(v)}⊂φ(e). Let exr(n,F) denote the maximum number of hyperedges in an r-uniform hypergraph on n vertices which does not contain a Berge-F. For small enough r and non-bipartite F, exr(n,F)=Ω(n2); we show that for sufficiently large r, exr(n,F)=o(n2). Let th(F)=min{r0:exr(n,F)=o(n2)for allr≥r0}. We show lower and upper bounds for th(F), the uniformity threshold of F. In particular, we obtain that th(△)=5, improving a result of Győri (2006). We also study the analogous problem for linear hypergraphs. Let exr L(n,F) denote the maximum number of hyperedges in an r-uniform linear hypergraph on n vertices which does not contain a Berge-F, and let the linear uniformity threshold thL(F)=min{r0:exr L(n,F)=o(n2)for allr≥r0}. We show that thL(F) is equal to the chromatic number of F
URI
https://pr.ibs.re.kr/handle/8788114/7724
DOI
10.1016/j.ejc.2020.103109
ISSN
0195-6698
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