6
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.