1
$\begingroup$

In a paper I am reading, the author states:

"It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"

He says that a proof can be found on Extremal Graph Theory, by Bela Bollobas.

However, I do not have easy access to that book.

Could someone please direct me to a more common graph theory book that has this result?

(btw: Modern Graph Theory, by Bollobas, does not have the result, as far as I can tell. But then again, I have not finished searching the book for it, and might have missed it)

$\endgroup$
5
  • 1
    $\begingroup$ There's a website called Library Genesis gen.lib.rus.ec where you can access that book. $\endgroup$
    – Saikat
    Jul 6, 2016 at 6:01
  • $\begingroup$ Cross-posted at mathoverflow.net/questions/243815/… $\endgroup$
    – user43208
    Jul 6, 2016 at 16:21
  • $\begingroup$ You can find the paper proving a sharp result here: tau.ac.il/~nogaa/PDFS/ahl1.pdf $\endgroup$
    – Shagnik
    Aug 2, 2016 at 6:26
  • $\begingroup$ @Shagnik, could you post this as an answer? I had already found a bound, asking in mathoverflow. $\endgroup$
    – josinalvo
    Aug 3, 2016 at 17:47
  • $\begingroup$ After you post your answer, I can compliment it with mathoverflow.net/questions/243987/… ,give credit to both you and the other answerer, and help the next person looking. $\endgroup$
    – josinalvo
    Aug 3, 2016 at 17:49

1 Answer 1

2
$\begingroup$

Suppose we have a graph with $q$ vertices and girth $g$. Since it has large girth, it must be locally treelike - there cannot be two paths of length $< \frac{g}{2}$ between any pair of vertices, since this would create a cycle of length less than $g$. Hence when we expand the first $\lfloor \frac{g-1}{2} \rfloor \ge \frac{g}{2} - 1$ neighbourhoods of a vertex $v$, there are no collisions - the neighbours of one vertex are disjoint from all others.

If the graph $G$ had minimum degree $d$, then since at every step each vertex contributes at least $d$ distinct neighbours, there must be at least $d^{\frac{g}{2} - 1}$ vertices in the final neighbourhood. As there are only $q$ vertices in total, it follows that $d^{\frac{g}{2} - 1} \le q$, or $d \le q^{\frac{2}{g-2}}$.

This was assuming a minimum degree condition. However, every graph with $q$ vertices and $m$ edges has a subgraph with minimum degree at least $\frac{m}{q}$ (iteratively delete any vertices with smaller degree, which causes us to lose fewer than $\frac{m}{q} \cdot q = m$ edges, and hence there must be a nonempty subgraph left). Thus $\frac{m}{q} \le q^{\frac{2}{g-2}}$, which gives $m = q^{1 + \frac{2}{g-2}} = q^{1 + O(1)/g}$.

However, this bound is not sharp - even if you do not estimate $\lfloor \frac{g-1}{2} \rfloor$, and handle the cases of $g$ even and odd properly, when passing to a subgraph of large minimum degree, this minimum degree is half of the average degree of the original graph. On the other hand, the expanding neighbourhood calculations are tight when the graph is regular, which would suggest the minimum degree should be close to the average degree.

This gap was resolved in the following paper of Alon, Hoory and Linial: paper available here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .