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.

Advertisements

Tags: , , ,

One Response to “The extremal utility belt: Cauchy-Schwarz”

  1. home garden and lifestyle gun show lafayette la Says:

    Tickets are available on line or at the IX Center and are
    priced $14. Terracotta Pottery is an affordable garden pot that will enhances garden decor.
    Some people also use it as a decorative piece during festive season in the living room.

    These include eco friendly because they do not create any smoke or sound pollution.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: