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

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.

Okay, so this seems like a lot of work to establish something that can be done in two lines with induction. And in fact you can view the above proof as inductive as well; if we build T edge by edge, we get the necessary statement that |E| = n-1 as a bonus.

But of course that can also be established by topological methods, which means that the only “combinatorial” part of the whole proof lies in picking the basis of our vector space. And in fact that’s really all we need, the rest of the proof being more or less window dressing:

Proof (of Theorem). Let V \cong GF(2)^n. Pick a basis of V. Proceed as in the end of the first proof.

So the first proof is pretty much useless. However, there are at least two ways it can be modified to be made (potentially!) interesting.

First, note that the construction of the vector space and independent set in the first proof was, in fact, a construction of a representation for the cycle matroid of T over GF(2). It’s a famous theorem that every graphic matroid is representable over $latex  GF(2)$ (and, in fact, over every field) — if this theorem, or more likely a purely matroid-theoretic version, can be proved without recourse to induction or linear algebra, we might obtain a “new” proof that 2^n \geq n.

Second, the cycle matroid of a simple graph is a simple matroid. In particular, if we consider the representation over GF(2) of the cycle matroid of K_n analogous to the one we constructed, we have an immediate proof that 2^n \geq \binom{n}{2}.

Questions: Can we give a “purely matroid-theoretic” proof of 2^n \geq n? Can we give a matroid-theoretic proof that exponential functions eventually dominate polynomial functions?


Tags: , , , , ,

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: