Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Theorem. Fix $\epsilon > 0$; for sufficiently large n, any graph with n vertices and $\epsilon \binom{n}{2}$ edges contains many (nondegenerate) cycles of length 4.

The proof is simple; put an indicator variable $\delta_{x, y}$ for each pair of vertices corresponding to whether or not there is an edge there; then start with

$n^8 \epsilon^4 = (\sum \delta_{x, y})^4$

and apply Cauchy-Schwarz twice; finally, note that there are $O(n^3)$ "degenerate 4-cycles".

A basic corollary of this is the following fact:

Corollary. Any graph with girth at least 5 and n vertices has $o(n^2)$ edges.

This seems like it should be possible to prove without resorting to "analytic" machinery like Cauchy-Schwarz; indeed, it seems like it should be weak enough to prove almost by arguing "locally." But none of the obvious lines of reasoning seem to provide a proof.

Is it possible to get a good bound on the density of large-girth graphs without using Cauchy-Schwarz or equivalent?

share|improve this question
add comment

1 Answer 1

up vote 16 down vote accepted

It's known more specifically that any graph with girth ≥ 5 has $O(n^{3/2})$ edges — see e.g. Wikipedia on the Zarankiewicz problem.

Here's a combinatorial proof. Suppose that graph $G$ has $\ge kn^{3/2}$ edges for a sufficiently large constant $k$. As long as there are vertices with degree smaller than some appropriate constant times $\sqrt n$ one can remove them and get a smaller graph with the same property of having at least $kn^{3/2}$ edges, so eventually one can reach a state where every vertex has degree at least $\Omega(\sqrt n)$. Once this happens, there are $O(n^2)$ possible pairs of neighbors that a vertex might have, and each vertex has $\Omega(n)$ pairs of neighbors, so some pair of neighbors appears twice causing the graph to have a 4-cycle.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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