Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Generalized Turan Problems For Even Cycles
 
research article

Generalized Turan Problems For Even Cycles

Gerbner, D.
•
Gyori, E.
•
Methuku, A.
Show more
January 1, 2019
Acta Mathematica Universitatis Comenianae

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 T-free graph on n vertices. We investigate the function ex(n, H, F), when H and members of F are cycles. Let C-k denote the cycle of length k and let c(k) = {C-3, C-4, ... C-k}. We highlight the main results below. (i) We show that ex(n, C-21, C-2k) = Theta(n(l)) for any l,k >= 2. Moreover, in some cases we determine it asymptotically. (ii) Erdos'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 WO such that vertical bar V(G(n))vertical bar = n, vertical bar E(G(n))vertical bar >= cn(1+1/k) with girth more than 2k. Solymosi and Wong proved that if this conjecture holds, then for any l >= 3 we have ex (n, C-2l, e(2l-1)) = Theta(n(2l/(l - 1))). We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of C-2l's significantly. (iii) We prove ex(n, c(2l+1), e(2l)) = Theta(n(2+1/l)), provided a stronger version of Erdos'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.

  • Details
  • Metrics
Type
research article
Web of Science ID

WOS:000484349000057

Author(s)
Gerbner, D.
Gyori, E.
Methuku, A.
Vizer, M.
Date Issued

2019-01-01

Published in
Acta Mathematica Universitatis Comenianae
Volume

88

Issue

3

Start page

723

End page

728

Subjects

Mathematics

•

graphs

•

pentagons

•

number

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
September 23, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/161448
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés