Combinatorial proof that large-girth graphs are sparse? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:07:03Z http://mathoverflow.net/feeds/question/17117 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17117/combinatorial-proof-that-large-girth-graphs-are-sparse Combinatorial proof that large-girth graphs are sparse? Harrison Brown 2010-03-04T18:27:57Z 2010-03-04T19:12:19Z <blockquote> <p>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.</p> </blockquote> <p>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</p> <p>$n^8 \epsilon^4 = (\sum \delta_{x, y})^4$</p> <p>and apply Cauchy-Schwarz twice; finally, note that there are $O(n^3)$ "degenerate 4-cycles".</p> <p>A basic corollary of this is the following fact:</p> <blockquote> <p>Corollary. Any graph with girth at least 5 and n vertices has $o(n^2)$ edges.</p> </blockquote> <p>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.</p> <p>Is it possible to get a good bound on the density of large-girth graphs without using Cauchy-Schwarz or equivalent? </p> http://mathoverflow.net/questions/17117/combinatorial-proof-that-large-girth-graphs-are-sparse/17121#17121 Answer by David Eppstein for Combinatorial proof that large-girth graphs are sparse? David Eppstein 2010-03-04T19:12:19Z 2010-03-04T19:12:19Z <p>It's known more specifically that any graph with girth ≥ 5 has $O(n^{3/2})$ edges — see e.g. <a href="http://en.wikipedia.org/wiki/Zarankiewicz_problem" rel="nofollow">Wikipedia on the Zarankiewicz problem</a>.</p> <p>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.</p>