Back from
RaTLoCC 2009
which is Ramsey Theory in Logic, Combinatorics, and Complexity.

Here are the list of talks:
here.

Reverse Mathematics
tries to classify theorems by what is the strength of the axioms needed
to prove them. There are five levels that almost all theorems in
mathematics fit into. One curious outlier: the infinite Ramsey Theorem
for pairs (for all c, for all ccolorings of the unordered pairs of
naturals, there exists an infinite homogeneous set that is, a set of naturals
where every pair has the same color).
It does not fit in nicely. Ramsey for triples, etc, does.

One of the first natural theorems to be proven independent
of PA was a Ramseytype theorem. (One can debate if its natural.)
See
here.

Van der Waerden's Theorem
In 1985 and earlier people thought that one of two things
would happen with VDW's theorem. At that time the only proof
lead to INSANE bounds on the VDW numbers.
EITHER a combinatorist would obtain a proof with smaller bounds
OR a logician would prove that the bounds were inherent.
What happened: A logician (Shelah) came up with a proof
that yielded primitive recursive bounds on VDW numbers.
(Later Gowers got much better bounds.)

The talks on Complexity were all on Proof Complexity things like
blahblah logical system needs blahblah space to prove
blahblah theorem. Some of the theorems considered were Ramsey Theorems.

A while back I did a guest post on Luca's blog on the poly VDW theorem
here.
At the conference I found out two things that I said or implied that
are INCORRECT.

I said that the first proof of Poly VDW, using Ergodic theory,
did not give bounds.
Philipp Gerhardy
gave a talk
at RaTLOcCC that claims
that the ergodic proofs either do yield bounds, or can easily
be made to yield bounds.
See his webpage (above pointer) for his paper.
(When I later asked him if he prefers the classical proof of VDW's theorem
or the Ergodic proof he said he can't tell them apart anymore.)

I said that the only bounds known for PolyVDW numbers are the ones
coming from an omega^omega induction. It turns out that
Shelah has a paper that gives primitive recursive bounds.
See either
here
or entry 679
here.
(The entry 679 version looks like its better typeset.)
The paper is from 2002.
I am not surprised that this is true or that Shelah proved it.
I am surprised that I didn't know about it since I am on the
lookout for such things.

The conference was about 1/3 logicians, 1/3 combinatorists and
1/3 complexity theorists. There were only 27 people there,
partially because it conflicted with FOCS and partially
because there is some institute having the entire Fall devoted
to Combinatorics (I forget which inst. but they are in California).

They plan to run it again, and if so I will so be there.
Or I will be so there. Or something.

Posted By GASARCH to
Computational Complexity at 11/02/2009 12:47:00 PM