The extremal utility belt: Cauchy-Schwarz

I found this little gem in an old post on Terry Tao’s blog. There’s not really enough content in it to merit an entire Extremal Toolbox post, but it’s too cool not to point out.

Theorem. Graphs of order $n$ and girth at least 5 have $o(n^2)$ edges.

Proof. Suppose that $G$ has $1/2*c*n^2$ edges. Define the function $A: V^2 \rightarrow \{0, 1\}$ to be the “adjacency characteristic function.” Now, by Cauchy-Schwarz:

$n^4 \Sigma A(x_1, y_1)A(x_1, y_2)A(x_2, y_1)A(x_2, y_2)$

$\geq (n \Sigma A(x, y_1) A(x, y_2))^2$

$\geq (\Sigma A(x, y))^4 = \frac{1}{16} c^4 n^8$ .

Clearly for $c$ fixed, $\frac{1}{16} c^4 n^8$ is unbounded as $n \rightarrow \infty$ . But the first expression is $n^4$ times the number of (possibly degenerate) 4-cycles in the graph; it’s easy to check that there are $O(n^3)$ degenerate 4-cycles, so as n is unbounded our graph must contain a 4-cycle. QED

Now, it’s possible to get better bounds by cleverly doing “surgery” on the graph and just using pigeonhole. (See here for details.) But it’s tricky and far less beautiful than the argument with Cauchy-Schwarz, which really demonstrates one way in which C-S can be thought of as “strengthening” pigeonhole.

Like this:

Be the first to like this post.

Tags: graph theory, math.CA, math.CO, pigeonhole principle

This entry was posted on March 10, 2010 at 23:46 and is filed under expository, extremal toolbox. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Portrait of the Mathematician

The extremal utility belt: Cauchy-Schwarz

Like this:

Leave a Reply Cancel reply

Follow “Portrait of the Mathematician”