Archive for the ‘extremal toolbox’ Category

The extremal utility belt: Cauchy-Schwarz

March 10, 2010

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

The extremal toolbox: A matrix problem

January 10, 2010

I’m starting a new series of posts this semester where I get “back to basics.” One of the few areas of mathematics in which I can claim anything even in the same connected component as “expertise” is extremal combinatorics. Unfortunately for me and my lazy, big-picture brain, though, extremal combinatorics is very much a “problem-solving” subject, with a relatively small number of tools that are used to solve all sorts of different problems. So without some practice solving these problems, or expositing the solutions, it’s easy to get rusty.

Hence, “The Extremal Toolbox.” In each post, I’ll take a (solved!) problem in extremal combinatorics — anything from Sperner’s theorem to Kakeya over finite fields, as long as there’s an extremal flavor — and try to break down a proof into its component parts.

Today I’m going to examine a problem which appeared on MathOverflow some time ago, which I didn’t quite solve (but came within epsilon of!) The relevant post is here; if you don’t care to click through, here’s the problem.

Let M be an n \times n matrix with non-negative integer entries. Suppose further that if m_{ij} is 0, then the sum of all the entries in the ith row or the jth column is at least n. Then the sum of all the entries in M is at least n^2/2.

(more…)