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.
Showing posts with label opinions. Show all posts
Showing posts with label opinions. Show all posts
Friday, November 30, 2007
Thursday, August 30, 2007
Things I Believe, Part 1: 13.7*10^9 B.C.E - c. 1 B.C.E.
So, just for the hell of it, I've decided to attempt a complete inventory of all the things that I believe. All my beliefs, if you will. This'll be a three-part series: Part 1 will cover events from the Beginning of the Universe 'til around the time of some guy's birth in Judea (since that's how people tend to reckon their calendars these days); Part 2 will cover around that dude's birth until the present day; and Part 3 will cover what I believe to be Mathematical and Other Truths (and the Future?). Capitalized. So, without further ado, here is What Harrison Believes.
1. I believe that the Universe as we know it exploded out of a small, hot, dense region approximately 13.7 billion years ago, plus or minus 200 million;
2. That an infinitesimal fraction of a second later, space expanded at an exponential rate far beyond c, and that this led to a "flattening" of local spacetime, and that quantum fluctuations were magnified to macroscopic scales;
3. That a fraction of a second later, the electromagnetic force separated from the weak force, and fundamental particles acquired mass;
4. That under a second after this, quarks were bound together by the strong nuclear force into hadrons and anti-hadrons (most of which annihilated each other immediately);
5. That about 100-300 seconds later, temperatures were right for some protons and neutrons left over to fuse into deuterium nuclei and those of a few other light elements (mostly helium);
6. That hadron/anti-hadron and lepton/anti-lepton annihilation reactions created an abundance of photons, which reacted over the next ~400,000 years with other nuclei, leptons, and hadrons wandering the cosmos;
7. That, as nuclei and electrons combined to form atoms (at around 400,000 years after the Big Bang), the Universe became transparent to radiation, and we see this radiation today as the cosmic microwave background;
8. That, around 200-500 million years later, the first stars (made almost entirely of lightweight elements) began to form, as did the first galaxies;
9. That, around this time, a very special galaxy began forming, one that certain sentient beings living in it would later call the "Milky Way"...
More to come - hold on tight.
1. I believe that the Universe as we know it exploded out of a small, hot, dense region approximately 13.7 billion years ago, plus or minus 200 million;
2. That an infinitesimal fraction of a second later, space expanded at an exponential rate far beyond c, and that this led to a "flattening" of local spacetime, and that quantum fluctuations were magnified to macroscopic scales;
3. That a fraction of a second later, the electromagnetic force separated from the weak force, and fundamental particles acquired mass;
4. That under a second after this, quarks were bound together by the strong nuclear force into hadrons and anti-hadrons (most of which annihilated each other immediately);
5. That about 100-300 seconds later, temperatures were right for some protons and neutrons left over to fuse into deuterium nuclei and those of a few other light elements (mostly helium);
6. That hadron/anti-hadron and lepton/anti-lepton annihilation reactions created an abundance of photons, which reacted over the next ~400,000 years with other nuclei, leptons, and hadrons wandering the cosmos;
7. That, as nuclei and electrons combined to form atoms (at around 400,000 years after the Big Bang), the Universe became transparent to radiation, and we see this radiation today as the cosmic microwave background;
8. That, around 200-500 million years later, the first stars (made almost entirely of lightweight elements) began to form, as did the first galaxies;
9. That, around this time, a very special galaxy began forming, one that certain sentient beings living in it would later call the "Milky Way"...
More to come - hold on tight.
Subscribe to:
Posts (Atom)