Sorry all, I accidentally sent that piece of mail before I was quite done with it. In particular, Dylan asked:
Claim: a valley of length k must contain a valley of length j for some j<k. So by induction, we're done.
Why does there have to be a valley at all?
The induction for an axb rectangle is started by the pseudo-valley consisting of the first three rows of the rectangle, i.e. a 3xa or 3xb hole that needs to be filled. That is, the bottom edge of the rectangle must have some row of horizontal strips along it, bounded either by vertical strips (i.e. you have a valley) or by one or both side walls of the original rectangle, which behaves precisely like a valley for the purposes of the downwards induction argument. The interesting thing to notice here is that, as a result, I'm not really using the fact that you're tiling a *rectangle* per se. All that's needed is that you're tiling a region which (1) forces a valley and (2) doesn't let you out of the nesting of valleys. You can only get out of the nesting of valleys with a funny-shaped bumpy roof -- so with flat roof, as in a rectangle, or any sort of monotone roof, or even no roof at all, the argument goes forwards. So, for example, the half-plane {(x,y):y>0} together with a valley-forcing rectangular dip {(x,y):0<=x<=a, -2<=y<=0} for any a>=2 supports exactly the same proof. It seems to me that this must be stronger than what you can prove with a coloring argument, since it is so insensitive to the shape of the region. Maybe with work this could lead to some sort of lower bound on how many 3x3 squares a tiling of an axb rectangle must contain, but I haven't thought through this at all. --Michael Kleber kleber@brandeis.edu