Report From Ramsey-Logic-Complexity Workshop

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

1. Here are the list of talks: here.
2. 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 c-colorings 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.
3. One of the first natural theorems to be proven independent of PA was a Ramsey-type theorem. (One can debate if its natural.) See here.
4. 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.)
5. The talks on Complexity were all on Proof Complexity- things like blah-blah logical system needs blah-blah space to prove blah-blah theorem. Some of the theorems considered were Ramsey Theorems.
6. A while back I did two guest posts on Luca's blog on the poly VDW theorem here and here At the conference I found out two things that I said or implied that are INCORRECT.
   1. 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.)
   2. 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.
7. 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).
8. They plan to run it again, and if so I will so be there. Or I will be so there. Or something.