10 Combinatorics Results to See Before You Die

OK, this is my personal list of the 10 most beautiful, useful, or interesting results in combinatorics. (Note: I'm leaving out complexity theory, since I'll hopefully cover that in a future post). These are, of course, heavily biased toward my interests and specialties, but I hope that anyone interested in the subject will be able to appreciate the list. So, in no particular order:


1. Erdos' lower bound for the Ramsey numbers R(k,k).
WHY? It's one of the best examples of the probabilistic method in action. Furthermore, it showcases the often-seen phenomenon in combinatorics where we can prove the existence of a certain object (a complete graph with 2^(k/2) vertices and no monochromatic k-clique), but can't come close to constructing it.

2. Szemeredi's regularity lemma.
WHY? It's a highly unintuitive proof of a highly unintuitive result, but both the proof and the lemma have turned out to be incredibly useful. If you're a graph theorist, you have no excuse for not knowing the statement of the Lemma; if you do additive combinatorics or theoretical CS, you have no reason not to know its proof. And if you're a mathematical aficionado, you should at least look at both.

3. Shelah's proof of the Hales-Jewett theorem.
WHY? Even though Hales and Jewett's original proof is shorter and cleaner, Shelah's strikes at the heart of "why" HJT is true. It manages to sidestep the Ackermann-type bounds that arose in all virtually all earlier proofs of Ramsey-type theorems on the integers, and it does it in such an incredibly simple way, you'll be left dumbstruck.

4. Sum-product inequalities from the crossing number inequality.
WHY? The crossing number inequality, the Szemeredi-Trotter theorem, and good sum-product estimates are all examples of highly nontrivial, very interesting results in combinatorics. And yet all three can be derived in just a couple of pages from what's essentially high-school level mathematics. A great example of how interesting combinatorial results often have simple and beautiful "Book proofs."

5. The Marcus-Tardos proof of the Stanley-Wilf conjecture.
WHY? OK, it would be wrong not to give a shout-out to my semi-official mentor, Adam Marcus. But there's more than that; this is another Book proof of a long-standing and unobvious conjecture. Just more evidence that combinatorics is the most level of mathematical playing fields.

6. Thomassen's proof of the five-list-color theorem.
WHY? This is the four-color theorem for list colorings, except, well, it doesn't take fifty pages and 200 hours of computer time to lay out. More like half a page -- pretty much as simple as Kempe's proof of the regular 5CT. And a wonderful illustration of the general principle that, with induction, it's sometimes easier to prove a more restrictive result.

7. Arrow's impossibility theorem.
WHY? OK, OK, this isn't usually considered to be part of combinatorics. But the statement of the theorem, as well as the proof, are heavily combinatorial. The theorem has (gasp!) a real-world interpretation, in terms of (duh) voting methods, and the proof is canonical combinatorial contradiction.

8. Kuperberg's proof of the alternating sign matrix conjecture.
WHY? Zeilberger's original proof is a tour de force of combinatorial reasoning, but Kuperberg's argument is unsurpassed in its originality. Statistical mechanics and its offshoots (mathematical physics, ergodic theory) have surprisingly many applications in combinatorics, and Kuperberg's masterful use of the Yang-Baxter equation is a novel example of this trend.

9. The "necklace proof" of Fermat's Little Theorem.
WHY? First of all, the fact that FLT, often considered a "number-theoretical" result, permits a strictly combinatorial argument shows combinatorics' applicability to other branches of math. Second, the proof itself shows that symmetry groups are useful for more than just enumeration. (They're also good for enumeration (mod p).

10. Add your own! What's one of the most original, informative, clever, or beautiful combinatorial results of all time? Comments are more than welcome.

The Riemann Hypothesis for Dummies; or, How Bad Music can Make You Obscenely Rich

No, this blog post isn't about 50 Cent.

Here's the scenario:

I'm an ultra-modern, avant-garde composer. I...compose music. One day, I decide, "Hey! I'm gonna write the weirdest piece EVER!"

Here's what I do:

For strings, I write a waltz (which, as you probably know, is in 3/4 time.) But actually, I lied. I don't write a waltz; I only write one measure of a waltz. Which seems like a weird thing to do, but you'll see my plan.

Then, for horns, I write, say, one measure of 4/4 time. And for piano, one measure of, let's say, 7/4 time. And so on.

Then I instruct each section to play their one single measure over and over and over again until they get tired, and then to keep playing it until all the sections finish their respective measures at the same moment.

The musicians will gripe about this arrangement, as musicians often do, but the overall sound won't repeat for a very long time! For example: If, as above, the strings play in 3/4, the horns in 4/4, and the piano in 7/4, then the piece will last a total of 3*4*7 = 84 beats.

But there's a catch! Yes, I'm an edgy and avant-garde composer, but I'm also environmentally conscious. Which means I want to make this piece as long as I possibly can (without repeating itself, of course) while only using a fixed number of beats, so that I won't waste paper. (Don't think too hard about that part. It's avant-garde composer logic.)

So, here's my question: Exactly how long can I make my piece last without writing more than, oh, n total beats?

Believe it or not, this question is actually unsolved! More than 100 years ago, in 1902, a German mathematician named Edmund Landau proved that when n is really big, I can't make it go on for much longer than e^\sqrt{n ln n} beats (where e is the base of the natural logarithms, or 2.71828...) This is a weird function! It grows a LOT slower than any exponential function (e.g. 1,2,4,8,...) but a LOT faster than any polynomial (for example, n^2, or 1,4,9,16...).

But mathematicians think they can do better than Landau. In fact, they think that something similar to Landau's answer -- exactly the same, in fact, except that n ln n has been replaced by something called "Li^-1(n)," which behaves very similarly -- provides an upper bound for big enough n, not just a close-to-upper bound.

But no one's been able to prove their conjecture! In fact, mathematicians have shown that this conjecture is precisely equivalent to the famous Riemann Hypothesis.

And the RH is considered to be one of the hardest problems in mathematics. It's so hard, in fact, that the Clay Mathematics Institute is offering a million-dollar reward to the first person who can publish a correct proof. In other words, my composer's idle question is actually worth seven figures.