Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.