Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012.
| Päätekijä: | |
|---|---|
| Muut tekijät: | |
| Aineistotyyppi: | Opinnäyte |
| Kieli: | eng |
| Julkaistu: |
Massachusetts Institute of Technology
2012
|
| Aiheet: | |
| Linkit: | http://hdl.handle.net/1721.1/73176 |
| _version_ | 1826211287580803072 |
|---|---|
| author | Morales, Alejandro Henry |
| author2 | Alexander Postnikov. |
| author_facet | Alexander Postnikov. Morales, Alejandro Henry |
| author_sort | Morales, Alejandro Henry |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012. |
| first_indexed | 2024-09-23T15:03:32Z |
| format | Thesis |
| id | mit-1721.1/73176 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:03:32Z |
| publishDate | 2012 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/731762019-04-10T17:07:19Z Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields Morales, Alejandro Henry 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, 2012. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student submitted PDF version of thesis. Includes bibliographical references (p. 123-127). In the first part of this thesis we study factorizations of the permutation (1; 2,..., n) into k factors of given cycle type. Using representation theory, Jackson obtained for each k an elegant formula for counting these factorizations according to the number of cycles of each factor. For the case k = 2, Bernardi gave a bijection between these factorizations and tree-rooted maps; certain graphs embedded on surfaces with a distinguished spanning tree. This type of bijection also applies to all k and we use it to show a symmetry property of a refinement of Jackson's formula first exhibited in the case k = 2; 3 by Morales and Vassilieva. We then give applications of this symmetry property. First, we study the mixing properties of permutations obtained as a product of two uniformly random permutations of fixed cycle types. For instance, we give an exact formula for the probability that elements 1; 2,..., k are in distinct cycles of the random permutation of f1; 2,..., ng obtained as product of two uniformly random n-cycles. Second, we use the symmetry to give a short bijective proof of the number of planar trees and cacti with given vertex degree distribution calculated by Goulden and Jackson. In the second part we establish the relationship between volumes of ow polytopes associated to signed graphs and the Kostant partition function. A special case of this relationship, namely, when the graphs are signless, has been studied combinatorially by Postnikov and Stanley and by Baldoni and Vergne using residues. As a special family of ow polytopes, we study the Chan-Robbins-Yuen polytope whose volume is the product of the consecutive Catalan numbers. We introduce generalizations of this polytope and give intriguing conjectures about their volume. In the third part we consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). Extending a result of Haglund, we show that when the set of entries is a skew Young diagram, the numbers, up to a power of q - 1, are polynomials with nonnegative coefficients. We apply this result to the case when the set of entries is the Rothe diagram of a permutation. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order. by Alejandro Henry Morales. Ph.D. 2012-09-26T14:17:47Z 2012-09-26T14:17:47Z 2012 2012 Thesis http://hdl.handle.net/1721.1/73176 809680284 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 127 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Morales, Alejandro Henry Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title | Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title_full | Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title_fullStr | Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title_full_unstemmed | Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title_short | Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields |
| title_sort | combinatorics of colored factorizations flow polytopes and of matrices over finite fields |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/73176 |
| work_keys_str_mv | AT moralesalejandrohenry combinatoricsofcoloredfactorizationsflowpolytopesandofmatricesoverfinitefields |