Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009. / Includes bibliographical references (p. 87-88). / 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. / by Alexey Spiridonov. / Ph.D.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/50597 |
| Date | January 2009 |
| Creators | Spiridonov, Alexey |
| Contributors | Alexander Postnikov., Massachusetts Institute of Technology. Dept. of Mathematics., Massachusetts Institute of Technology. Dept. of Mathematics. |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 88 p., application/pdf |
| 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., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0097 seconds