Complex tiling: breaking translational symmetry

Leonid Levin

Boston University

October 2,
refreshments at 3:45pm


A tile is a unit size square with colored edges. A palette P is a finite set of tiles with copies of which one can tile the plane so that the colors of adjacent tiles match. Classical works constructed palettes that can tile an infinite plane, but cannot do this recursively. That is, consider all P-squares, i.e. those appearing in P-tilings of a plane. For any c, only P-squares of bounded size can be generated (from their diameter) by c-bit programs. We pushed these results to the limit, with a palette for which all such squares have diameter c or less. This bound is tight since specifying the tiles on the square's frame suffices for tiling the square recursively. Thus, this palette allows only tilings with all frames being "nearly-random".

My talk, however, will only briefly mention this our result. I will mostly talk about just one old tool we are using: a palette P which precludes any translational symmetry in any P-tiling. The set of all P-tilings is, of course, symmetric under translations. Yet, any specific P-tiling is aperiodic, this symmetry spontaneously broken. Classical proofs of this result are very cumbersome. I will try to present a more transparent construction and proof.

Joint work with Bruno Durand and Alexander Shen.

Speaker's Contact Info: (lnd(at-sign)cs) (correct in an obvious way)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on September 13, 2002 at 11:11 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.