## Monday, November 02, 2009

### 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.

1. ome institute having the entire Fall devoted to Combinatorics (I forget which inst. but they are in California).

That would be IPAM, at UCLA. See e.g. my blog report on their combinatorial geometry workshop.

2. How did you like Bertinoro? I have been in the scientific advisory board of BICI since 2002 and I am therefore biased, but I have enjoyed organizing and attending workshops there. Participants in the workshops I organized seemed to enjoy the atmosphere too.

3. D. Eppstein- THANKS for the pointer.

Luca Aceto- YES, I liked it alot- I was going to (and still will) talk about that in my next posting.

4. "The talks on Complexity were all on Proof Complexity- things like blah-blah logical system needs blah-blah space to prove blah-blah theorem."

I think proof complexity is a serious research topic. This is especially true for this workshop with the "Logic" in the title. I don't think it's fair to mention it as "blah blah" stuffs.

5. Anon 4- I did not mean any
offense or belittling of the subject of proof complexity. blah-blah meant more like
`fill in the blank, there are many such great theorems with blah-blah filled in with interesting things.'