In reading a paper, I came across an affirmation
"a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
In a previous question I asked in this site about it, I was reffered to a theorem by Bondy and Simonovits, that states:
$ex(q,C_{2k}) < (k – 1 + o(1)) q^{1+1/k}$
This is a bound that does the job, assuming a fixed girth.
However, in my case, I have a girth that grows with $n$ (a variable independent of $q$).
So, now I ask a more generic question: what kind of bounds are known, to limit a graph's number of edges, given its girth and its number of vertices?
Best Answer
The bound you quote is actually a little inefficient, because it is harder to find a cycle of fixed length $t$ than to find a cycle of length at most $t$. I recommend that you look at Section 4.1 of the excellent survey by Füredi and Simonovits:
https://arxiv.org/pdf/1306.5167.pdf
In particular, Theorem 4.1 of that survey, saying that $$\textrm{ex}(n, \{C_3, C_4, \dots, C_{2k}\}) < \frac{1}{2} n^{1 + 1/k} + \frac{1}{2} n,$$ gives a fairly satisfactory answer to your question for odd girth.