### BROWSE

#### Related Scientist

Abhishek, Methuku
이산수학 그룹

Generalized Turán problems for even cycles

Cited 0 time in Cited 0 time in
Title
Generalized Turán problems for even cycles
Author(s)
; ; ;
Publication Date
2020-11
Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B, v.145, pp.169 - 213
Publisher
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.