12
$\begingroup$

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?

$\endgroup$

1 Answer 1

20
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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