RaTLoCC (Ramsey Theory in...)

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity. The idea was to bring in researchers for all three areas (actually its more than three) and have them learn about each others areas.

1. During Szemeredi's talk he said I am not an expert on Ramsey Theory. He meant to say I am not an expert on Ramsey Numbers, e.g., the current upper and lower bounds on R(5).
2. An anagram of Banach-Tarski is Banach-Tarski Banach-Tarski.
3. Bertinoro hosted both RaTLoCC and SUBLINEAR (a workshop on ... SUBLINEAR things) at the same time. We had some shared activities with them. They were a younger, hipper crowd. Ronitt Rubinfeld (who was there) told me they had LESS women than they thought they would have- only 4. We had MORE women then we thought we would have- 2 (we had 0 last time).
4. There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b
5. One measure of how much you get out of a workshop or conference is how many papers you are inspired to read when you get back home (or perhaps how many pages-of-papers or theorems, or some measure.) With that in mind, here is a list of some of the papers that inspired me. (Slides and abstracts are posted at the workshop's website.)
   1. Szemeredi talked on Arithmetic progressions in sumsets. Here is a sample theorem. Throughout A is a subset of {1,...,n} and n is large. A+A is the set of all sums of two elements of A. LA is A+A+...+A (L times). Sample theorem: For all C there exists c such that if |LA| > Cn then LA has a cn-AP (an arithmetic progression of length cn.) These theorems look HARD but it inspires me to read some papers on Alon's website on this topic, and also my own writeup of sum-product theorems (He used C and c in his talk- though some of them looked the same.)
   2. Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is L-List colorable if there is a way to assign each vertex L colors so that there IS a coloring of the graph where each vertex uses on of the colors assigned to it. Let G be the unit distance graph in the plane: vertices are points in the plane and two points are connected if they are distance one apart. This graph is known to be 7 colorable, known to NOT be 3-colorable. All else is open. Noga talked about his proof (co-author Kostochka) that G is NOT list-s-colorable for any s. The paper is on his website and I am INSPIRED to read it. (ADDED LATER- THE DEFINITION I GAVE ABOVE IS NOT CORRECT. SEE COMMENT BELOW.)
   3. Peter Cholak talked on Reverse Mathematics of Ramsey Theory. Reverse mathematics is a field where they have set up several axiom systems for mathematics (in a hierarchy) and, for MANY theorems of math, they know EXACTLY which system is needed. Infinite Ramsey Theory for PAIRS seems to be stubborn- it is not in any of the usual systems. (formally: RCA cannot prove it, but ACA is too much). It is provably DIFFERENT from Infinite Ramsey for TRIPLETS (which is equivalent to the theorem for 4-tuples, 5-tuples, etc, and for all of them ACA is exact.) My question: when I prove Ramsey for triples I do not feel the earth move or think MY GOODNESS- THAT STEP WAS NONCONSTRUCTIVE!!!! or anything else that is different from Ramsey for pairs. They told me that there IS a proof of Ramsey for pairs that, once you see it, you DO NOT know how to generalize to triples. I may try to look into this. I may not. The paper is at Peter Cholak's webpage and is titled On the strength of Ramsey's theorem for pairs. (co-authored by Jockusch and Slaman)
   4. David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is double-exp but the lower bound is single-exp. They made some progress on this, but the upper and lower bounds are still, pretty much, what they were. Still- proofs look very interesting. Progress here is unpredictable--- Conlon said that the problem could be solved next week or next month or not for one hundred years. Also, the proofs are clever- so Erdos COULD HAVE done them. (As opposed to results that use mathematics unknown to anyone in Math at the time.) I am INSPIRED to read this paper by Conlon, Fox, and Sudakov. The case of 3-hypergraph is interesting because, if the lower bound can be gotten up to double exp then for k-hypergraphs we will know that upper and lower bounds are roughly tower(k-1). (Uses the STEPPING UP Lemma.)
   5. Swastik Kopparty talked on The complexity of computing roots and residuosity in finite fields. Say you are in a ints mod p and you want to know whether x is a cube root or not by a constant depth circuit. This will take exp number of gates. Framework is the same as the Parity not in ACC_0 proof, but requires lots more math. MIGHT want to read it. MIGHT be too hard.
   6. Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in Rⁿ. IS it the case that, for all c there exists a finite set T in R^m. (m \ge n) such that, no matter how you c-color T there will be a CONGRUENT copy of S? The unit line has this property. If so then S is RAMSEY. It is known that if S is Ramsey then S lies on the surface of some (many dim) sphere. The Main conjecture is that the converse is true. NO says Imre! He has an alternative conjecture here. This paper I am INSPIRED to read.
   7. Jan-Christoph Schlage-Puchta (that is one person) gave an application of VDW's theorem to Completely Multiplicative Automatic Functions This one I NEED to read to put in my book on VDW's theorem. Its here
6. The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the no-specialist could at least here that and then TOLD YOU WHY THEY CARE (even if you don't care you should know why they care) and TOLD YOU SOMETHING ABOUT THE TECHNIQUES. Not all of the talks did this. Also, the best talks were on BLACKBOARD- it forces you to go slower. Not possible at STOC/FOCS etc since the audience is too big, but quite possible here. Only drawback- can't put blackboard talks on the web so easily (though you can if you videotape).
7. The youngest participant: James Pinkerton, my High School Student, gave his talk on Duplicator Spoiler Games that go on an ordinal number of moves. The talk was AWESOME! Before hand he was not scared. He said Whats the worst they can do? Throw red and blue tomatoes at me?
8. One of the people there wore a T-shirt that said Stand back, I'm doing SCIENCE! that had a picture (stick figure really) of a scientists with a test tube. He wore it two days in a row. I commented: Nonconstructive proof that you are a supernerd. Either (1) You wore the same T-shirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy T-shirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.