BROWSE

Related Scientist

Abhishek, Methuku's photo.

Abhishek, Methuku
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Generalized Turán problems for even cycles

Cited 0 time in webofscience Cited 0 time in scopus
37 Viewed 0 Downloaded
Title
Generalized Turán problems for even cycles
Author(s)
Dániel Gerbner; Ervin Győri; Abhishek Methuku; Máté Vizer
Publication Date
2020-11
Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B, v.145, pp.169 - 213
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Abstract
© 2020 Elsevier Inc. Given a graph H and a set of graphs F, let ex(n,H,F) denote the maximum possible number of copies of H in an F-free graph on n vertices. We investigate the function ex(n,H,F), when H and members of F are cycles. Let Ck denote the cycle of length k and let Ck={C3,C4,…,Ck}. We highlight the main results below. (i) We show that ex(n,C2l,C2k)=Θ(nl) for any l,k≥2. Moreover, in some cases we determine it asymptotically: We show that [Figure presented] and that the maximum possible number of C6's in a C8-free bipartite graph is n3+O(n5/2). (ii) Erdős's Girth Conjecture states that for any positive integer k, there exist a constant c>0 depending only on k, and a family of graphs {Gn} such that |V(Gn)|=n, |E(Gn)|≥cn1+1/k with girth more than 2k. Solymosi and Wong [37] proved that if this conjecture holds, then for any l≥3 we have ex(n,C2l,C2l−1)=Θ(n2l/(l−1)). We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of C2l's significantly: For any k>l, we have ex(n,C2l,C2l−1∪{C2k})=Θ(n2). More generally, we show that for any k>l and m≥2 such that 2k≠ml, we have ex(n,Cml,C2l−1∪{C2k})=Θ(nm). (iii) We prove ex(n,C2l+1,C2l)=Θ(n2+1/l), provided a stronger version of Erdős's Girth Conjecture holds (which is known to be true when l=2,3,5). This result is also sharp in the sense that forbidding one more cycle decreases the number of C2l+1's significantly: More precisely, we have [Figure presented], and ex(n,C2l+1,C2l∪{C2k+1})=O(n2) for l>k≥2. (iv) We also study the maximum number of paths of given length in a Ck-free graph, and prove asymptotically sharp bounds in some cases
URI
https://pr.ibs.re.kr/handle/8788114/7573
DOI
10.1016/j.jctb.2020.05.005
ISSN
0095-8956
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