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.

Subscribe to:
Post Comments (Atom)

## 5 comments:

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.

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...)

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

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]

xanax cost xanax withdrawal constipation - xanax drug anxiety

Post a Comment