Friday, November 30, 2007

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.

5 comments:

GASARCH said...

I would add the following
to your list, but then
it would no longer be
`10 combinatorics Results
to see before you die.'

11) ORIGINAL proof of VDW
theorem. Easier than
Shelah's proof, and the
EEEEEEEEENORMOUS bounds
are kind of fun.

12) The proof using the
crossing lemma that,
given n points in the
plane there are
Omega(n^{0.8}) distinct
distances. Szekely's
paper, available on
my ERDOS-DISTANCE PROBLEM
WEBSITE
http://www.cs.umd.edu/~gasarch/erdos_dist/szekely.pdf

13) the following SEQUENCE
of results
about Ramsey Numbers
(I state for 2 colors,
but versions are true
for c colors)

a) R(\omega,\omega)=\omega

b) From (a) you can get
that R(k,k) exists.

c) R(k,k) \le 2^{2k-1},
standard proof

d) LR(k,k) exists
(LR is Large Ramsey.
LR(k,k) is the least n
such that if you 2-color
the edges of K_n
WITH VERTEX LABELS
k,k+1,...,k+n you have
a homogenous set that
has more elements then
its least element).
PROOF is FROM
R(omega,omega) exists

WHY is this interesting:
There IS NO `normal'
proof that LR(k,k) exists.
The statement that it
exists is ind of PA.
Hence the large bounds
on LR(k,k) are legit-
unlike VDW they CANNOT
come down.

John said...

bill: Yeah, I found myself regretting restricting myself to 10. Oh well.

(Obligatory Douglas Adams reference: If you count in base 13, it's still 10, but nobody does math in base 13...)

smbelcas said...

Ah, well. Guess I'm not a graph theorist, then.

Anonymous said...

Bonjour, inferiorcomplexity.blogspot.com!
[url=http://cialissexc.pun.pl/ ]Achat cialis online[/url] [url=http://viagraginc.pun.pl/ ]Acheter du viagra en ligne[/url] [url=http://cialispite.pun.pl/ ] cialis en ligne[/url] [url=http://viagravalo.pun.pl/ ]Acheter du viagra online[/url] [url=http://cialisanta.pun.pl/ ]Acheter cialis en ligne[/url] [url=http://viagrapeck.pun.pl/ ]Acheter viagra online[/url]

Anonymous said...

xanax cost xanax withdrawal constipation - xanax drug anxiety