What is an application?

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 mgon.
The Physics student went back to sleep.
(Short sketch of proof: Let n be the 3hypergraph ramsey
number such that for any 2coloring of the 3sets of [n]
there is a homogenous set of size m.
Given the n points in the plane, color setsofthree
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 mgon. 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 ErdosSzekeres 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 nhypergraph Ramsey
number such that for any n!coloring of the nsubsets of U
there is a homogenous set of size 2n1.
Color an nsubset of U by the permutation it is stored in.
There will be 2n1 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 ErdosSzekeres problem.
The third applies Ramsey Theory to Data Structures.
The first and third seem like legit applications.
The second one is suspect applying one Erdosstyle 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.

Posted By GASARCH to
Computational Complexity at 5/12/2008 10:02:00 AM