Combinatorics of permutation patterns, interlacing networks, and Schur functions

In the first part, we study pattern avoidance and permutation statistics. For a set of patterns n and a permutation statistic st, let Fst/n ([Pi]; q) be the polynomial that counts st on the permutations avoiding all patterns in [Pi]. Suppose [Pi] contains the pattern 312. For a class of permutation statistics (including inversion and descent statistics), we give a formula that expresses Fst/n ([Pi]; q) in terms of these st-polynomials for some subblocks of the patterns in [Pi]. Using this recursive formula, we construct examples of nontrivial st-Wilf equivalences. In particular, this disproves a conjecture by Dokos, Dwyer, Johnson, Sagan, and Selsor that all inv-Wilf equivalences are trivial. The second part is motivated by the problem of giving a bijective proof of the fact that the birational RSK correspondence satisfies the octahedron recurrence. We define interlacing networks to be certain planar directed networks with a rigid structure of sources and sinks. We describe an involution that swaps paths in these networks and leads to a three-term relations among path weights, which immediately implies the octahedron recurrences. Furthermore, this involution gives some interesting identities of Schur functions generalizing identities by Fulmek-Kleber. Then we study the balanced swap graphs, which encode a class of Schur function identities obtained this way.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Trongsiriwat, Wuttisak

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/99322

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99322