From Turan's theorem we know that we can have $O(n^2)$ edges in a triangle-free graph. The theorem talks about $k$-free graphs, where the graph doesn't contain any cliques of size $k$.

I am looking for an analogy for $k$-cycle-free graphs, that is a graph that doesn't contain a cycle of size $k$ or smaller. All cycles must be of size at least $k+1$.

For $k = 3$, the two definitions are the same (a triangle is a clique and a cycle). So even help with $k=4,5$ will help me a lot.



migrated from mathoverflow.net Dec 3 '17 at 20:36

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ Look up girth. $\endgroup$ – Aaron Meyerowitz Dec 1 '17 at 10:14
  • 1
    $\begingroup$ For a survey of the most important results regarding this problem you may look at arxiv.org/pdf/1306.5167.pdf (especially section 4.1). $\endgroup$ – Oliver Krüger Dec 1 '17 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy