- When I took Algebraic Topology the professor said at one point I will now show you an application of homotopy theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use homotopy theory to show that every polynomial with complex coefficients has a complex root The Physics student went back to sleep. (Short sketch of proof: Using Homotopy theory you can show that the complex plane and the punctured complex Plane (remove the origin) are different topologically- the former has trivial homotopy group, while the later has homotopy group Z. Therefore there is no `nice' map between them. If there was a poly p(z) with no roots then you can use this to get a nice map between the two.)
- When I took Ramsey Theory the professor said at one point I will now show you an application of Ramsey theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use Ramsey's Theorem to show that, for all m, there exists an n so that, for all sets of n points in the plane, no three colinear, there exists m that form a convex m-gon. The Physics student went back to sleep. (Short sketch of proof: Let n be the 3-hypergraph ramsey number such that for any 2-coloring of the 3-sets of [n] there is a homogenous set of size m. Given the n points in the plane, color sets-of-three as follows: if the number of points in the triangle formed by the 3 points is ODD then color it RED, otherwise BLUE. There will be m points such that every set of 3 has the same parity inside it. One can show that these m points form a convex hull of an m-gon. First step of this proof: if one of the points is inside the convex hull then its inside a triangle formed by three of the other points. NOTE1: Much better bounds are known. NOTE2: Finding the smallest n is called the Erdos-Szekeres problem or the happy ending problem. See this paper for a survey.)
- I have a website of website of applications of Ramsey Theory to Computer Science. One of the first ones was Yao's paper Should tables be sorted?. This paper shows that in the Cell Probe Model, if the universe is big enough then yes indeed, tables should be sorted. (Short Sketch: Assume there is a scheme for, given n elements of the ordered universe U, stores them in an array of length n cells. Let the universe U be of size the n-hypergraph Ramsey number such that for any n!-coloring of the n-subsets of U there is a homogenous set of size 2n-1. Color an n-subset of U by the permutation it is stored in. There will be 2n-1 elements such that any subset of n is stored in the same permuation. Assume that it is SORTED (if not then it is a fixed perm to make it SORTED). One can show that if the list is sorted then binary search is the best way to find an element. See this paper for a survey. )
So, are these applications or not? The first one applies topology to algebra. The second one applies Ramsey Theory to the Erdos-Szekeres problem. The third applies Ramsey Theory to Data Structures.
The first and third seem like legit applications. The second one is suspect- applying one Erdos-style branch of combinatorics to another. But they are different branches. One metric of how legit an application is might be how far apart the fields are.
Another pair of entries for the computational geometry section of your Ramsey applications page: http://arxiv.org/abs/math.CO/0109195 and http://arxiv.org/abs/math.CO/0204252
ReplyDeleteThere are two different reasons for including "applications" in theoretical publications:
ReplyDelete(1) because the application is what you really want to solve, and the theory you're publishing really was useful for solving that application, and
(2) to convince program committees (or students) that the theory you're about to show them is worth reading or learning about because it's good for something they're more likely to already care about.
One might argue that applications of type (1) are better than applications of type (2), because they're more real and less just for show.
Of your three examples, I find the second and third to be better by this criterion than the first. There are other simpler ways of proving the fundamental theorem of algebra than by homotopy theory, so proving the FTA in this way is less about actually needing homotopy theory to prove it and more about showing off what homotopy theory is good for. On the other hand, the happy ending problem really was a historical motivation for the development of Ramsey theory, and Yao really couldn't find a better way at the time of proving his result about the cell probe model than to use Ramsey theory.
One criterion in judging the worth of an application of a complex theory: How much of the complexity of the theory is needed to derive the consequence?
ReplyDeleteA much simpler case than the ones you mentioned is Kolmogorov complexity. Some applications use the general notions of incompressible strings and prefix-free encoding wrt universal TMs while others can be more easily replaced by simple counting arguments that yield better results because they do not lose the constants inherent in the universal approach. The latter ones do not seem to be applications of the theory that justify its worth.
I just submitted a paper that shows an absolute time lower bound for stochastic models of nano self-assembly, using the Naor and Stockmeyer paper I first found on your "Applications of Ramsey Theory" page. Applications are where you find them... and thank you, Bill!
ReplyDelete