Pattern-avoidance in binary fillings of grid shapes

A grid shape is a set of boxes chosen from a square grid; any Young diagram is an example. We consider a notion of pattern-avoidance for 0-1 fillings of grid shapes, which generalizes permutation pattern-avoidance. A filling avoids a set of patterns if none of its sub-shapes, obtained by removing some rows and columns, equal any of the patterns. We focus on patterns that are pairs of 2 x 2 fillings. Totally nonnegative Grassmann cells are in bijection with Young shape fillings that avoid particular 2 x 2 pair, which are, in turn, equinumerous with fillings avoiding another 2 x 2 pair. The latter ones correspond to acyclic orientations of the shape's bipartite graph. Motivated by this result, due to Postnikov and Williams, we prove a number of such analogs of Wilf-equivalence for these objects - that is, we show that, in certain classes of shapes, some pattern-avoiding fillings are equinumerous with others. The equivalences in this paper follow from two very different bijections, and from a family of recurrences generalizing results of Postnikov and Williams. We used a computer to test each of the described equivalences on a diverse set of shapes. All our results are nearly tight, in the sense that we found no natural families of shapes, in which the equivalences hold, but the results' hypotheses do not. One of these bijections gives rise to some new combinatorics on tilings of skew Young shapes with rectangles, which we name Popeye diagrams. In a special case, they are exactly Hugh Thomas's snug partitions for d = 2. We show that Popeye diagrams are a lattice, and, moreover, each diagram is a sublattice of the Tamari lattice. We also give a simple enumerative result.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Spiridonov, Alexey

Advisor dc:contributor.advisor

• Alexander Postnikov.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/50597

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/50597