Pattern-avoidance in binary fillings of grid shapes
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/50597 |
| _version_ | 1811080627042123776 |
|---|---|
| author | Spiridonov, Alexey |
| author2 | Alexander Postnikov. |
| author_facet | Alexander Postnikov. Spiridonov, Alexey |
| author_sort | Spiridonov, Alexey |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009. |
| first_indexed | 2024-09-23T11:34:16Z |
| format | Thesis |
| id | mit-1721.1/50597 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:34:16Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/505972019-04-11T04:03:32Z Pattern-avoidance in binary fillings of grid shapes Spiridonov, Alexey Alexander Postnikov. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. 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. 2010-01-07T20:58:39Z 2010-01-07T20:58:39Z 2009 2009 Thesis http://hdl.handle.net/1721.1/50597 465223718 eng 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 88 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Spiridonov, Alexey Pattern-avoidance in binary fillings of grid shapes |
| title | Pattern-avoidance in binary fillings of grid shapes |
| title_full | Pattern-avoidance in binary fillings of grid shapes |
| title_fullStr | Pattern-avoidance in binary fillings of grid shapes |
| title_full_unstemmed | Pattern-avoidance in binary fillings of grid shapes |
| title_short | Pattern-avoidance in binary fillings of grid shapes |
| title_sort | pattern avoidance in binary fillings of grid shapes |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/50597 |
| work_keys_str_mv | AT spiridonovalexey patternavoidanceinbinaryfillingsofgridshapes |