Posts Tagged ‘pigeonhole principle’

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.

2^n \geq n: The graph theory proof?

February 15, 2010

Theorem. For every positive integer n, $2^n \geq n$.

Proof. Consider a tree on n vertices $T = (V, E)$ with root $v_0$. Assign to each edge $\{v, w\}$ an element of the vector space $GF(2)^V$, obtained by setting 1s in the the coordinates corresponding to v and w and 0s elsewhere. I claim that these vectors are linearly independent; for suppose otherwise, and letthe vectors corresponding to $S \subset E$ sum to 0. There is a natural “distance” function on E w/r/t $v_0$; let $e_0 = \{s, t\}$ have maximal distance in S, and suppose WLOG that t is farther than s from $v_0$. Then the coordinate corresponding to t is nonzero for exactly one element of S, and the sum over all elements of S must therefore be nonzero. This is a contradiction. So in particular these |E| = n-1 elements are distinct and nonzero, which means (by Pigeonhole) that there are at most $2^n-1$ of them.

GILA 1: van der Waerden and all that

August 22, 2009

I’m beginning my GILA series announced on Thursday with a short exposition of van der Waerden’s theorem, and an attempt to extend its proof to the density version (at least in the k=3 case). Before I start, I should mention something I neglected in the last post: that this series is as much for my benefit as for that of any “interested lay audience” out there. Someone like Terry Tao could undoubtedly do a better series of this type (and, indeed, I’ll be leaning heavily on my borrowed copy of Tao and Van Vu’s Additive Combinatorics throughout) but they haven’t, so I’ll try. However, there are certain to be a number of embarrassing mistakes, unjustified statements, lines of thinking left unresolved, etc., throughout (indeed, an anonymous commenter noted two in the introductory post!), and I encourage readers to point them out in the comments.

So, on to van der Waerden’s theorem. van der Waerden’s theorem is one of the early jewels of Ramsey theory (actually predating Ramsey’s article by a couple of years) and can be viewed as a weaker version of Szemeredi’s theorem. It states simply that, for any integers $c, k > 0$, if you color the positive integers with c colors, then there exists a monochromatic k-term arithmetic progression.

Khinchin, in his wonderful book which unfortunately appears to be out of print (at least in English), gives some history of the problem:

All to whom this question [the theorem in the c = 2 case] was put regarded the problem at first sight as quite simple; its solution in the affirmative appeared to be almost self-evident. The first attempts to solve it, however, led to nought… [T]his problem, provoking in its resistance, soon became the object of general mathematical interest… I made [van der Waerden's] acquaintance, and learned the solution from him personally. It was elementary, but not simple by any means. The problem turned out to be deep; the appearance of simplicity was deceptive.

This last clause is particularly wonderful, describing as it does not only van der Waerden’s theorem but Ramsey theory and perhaps even combinatorics in general.

The usual proof (given in story-form by Zeilberger here) is not van der Waerden’s, however, but comes from Khinchin, attributed by him to a M.A. Lukomskaya in Minsk. It is a masterpiece, using nothing but a very clever inductive argument and some application of the pigeonhole principle. For the sake of self-containedness, I’ll sketch the argument below the fold.