 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).
 An anagram of BanachTarski is BanachTarski BanachTarski.
 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).
 There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b

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 pagesofpapers 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.)
 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 cnAP (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 sumproduct theorems (He used C and c in his talk though some of them looked the same.)
 Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is LList 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 3colorable. All else is open. Noga talked about his proof (coauthor Kostochka) that G is NOT listscolorable 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.)
 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 4tuples, 5tuples, 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. (coauthored by Jockusch and Slaman)
 David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is doubleexp but the lower bound is singleexp. 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 3hypergraph is interesting because, if the lower bound can be gotten up to double exp then for khypergraphs we will know that upper and lower bounds are roughly tower(k1). (Uses the STEPPING UP Lemma.)
 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.
 Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in R^{n}. 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 ccolor 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.
 JanChristoph SchlagePuchta (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
 The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the nospecialist 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).
 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?
 One of the people there wore a Tshirt 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 Tshirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy Tshirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, May 31, 2011
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.
That was truly inspiring, thanks. If I were your dean that report would cause me to fund your next five years ttendance with no need to file a formal request! I immediately looked up the Cholak/Jockusch/Slaman paper although it looks too long to add to my current reading pile. What a different world it would be if there were some way for people without mathematics backgrounds to be equally inspired by the great work that is out there.
ReplyDeleteIt's almost surely this shirt: http://store.xkcd.com/xkcd/#StandBackScience
ReplyDeleteJust noticed that there seem to be 3 notions for coloring planar graphs:
ReplyDeleteLlistcolorable
ncolorable
listscolorable
They went by so fast I didn't realize I was making acquaintance with 3 different terms. At least I think it was only 3, are there more?
Red and blue tomatoes. Tomatoes don't read or are read.
ReplyDeleteMicki apologies, there are only two notions of graph coloring, and they apply to all graphs not just planar ones.
ReplyDeleteLlistcolorable and list scolorable
are the same thing, though with a diff parameter.
ncolorable is of course the usual notion of graph coloring.
MAJOR CORRECTION: a graph is Llistcolorable if
ReplyDeleteFOR ANY assignment of L colors to each vertex
there is a way to pick for each vertex a color
from its list and get a proper coloring.
(Thanks to the email that pointed this out.)