Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X\_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C\_3, C\_4, \ldots, C\_{f(n)})$-free, i.e. $G$ contains no cycles of length at most $f(n)$.


It is known that if $f$ is constant, then graphs in $X\_f$ can have a superlinear number $n^{1+\epsilon(f)}$ of edges. On the other hand, if $f : n \mapsto n$, then $X\_f$ is the class of forests, which have a linear number of edges.


I'm wondering if there is a transition from the superlinear to the linear regime.


For example, is there a known function $f^\*$ such that


1. for any $g \in o(f^\*)$, the class $X\_g$ has $n$-vertex graphs with a superlinear number ($\omega(n)$) of edges;
2. for any $g \in \omega(f^\*)$, the graphs in $X\_g$ have a linear number of edges?



Graphs without short cycles and with linear number of edges
Threshold is $\log n$.


1. If the graph has at least, say, $2n$ edges, it has a cycle of length at most, say, $2\log\_2 n$ (proof: remove vertices of degree at most 2 while it is possible. After each step, $|E|\geqslant 2|V|$ property is preserved. So, you get a graph with all degrees at least 3,and considering DFS from any vertex you find a cycle of above mentioned length.)
2. For any $C>0$, there exists $\varepsilon>0$ such that there exists a graph with $Cn$ edges and all cycles not shorter than $\varepsilon \log n$. (proof: take a random graph $G(n, 5C/n)$ and destroy all short cycles.)


