1 |
Research on Combinatorial Statistics: Crossings and Nestings in Discrete StructuresPoznanovikj, Svetlana 2010 August 1900 (has links)
We study the distribution of combinatorial statistics that exhibit a structure of crossings and nesting in various discrete structures, in particular, in set partitions, matchings, and fillings of moon polyominoes with entries 0 and 1. Let pi and y be two set partitions with the same number of blocks. Assume pi is a partition of [n]. For any integers l, m >̲ 0, let T (pi, l) be the set of partitions of [n + l] whose restrictions to the last n elements are isomorphic to pi, and T (pi, l, m) the subset of T (pi, l) consisting of those partitions with exactly m blocks. Similarly define T (pi, l) and T (y, l, m). We prove that if the statistic cr (ne), the number of crossings (nestings) of two edges, coincides on the sets T (pi, l) and T (pi, l) for l = 0; 1, then it coincides on T (pi, l, m) and T (y, l, m) for all l, m >̲ 0. These results extend the ones obtained by Klazar on the distribution of crossings and nestings for matchings. Moreover, we give a bijection between partially directed paths in the symmetric wedge y = +̲ x and matchings, which sends north steps to nestings. This gives a bijective proof of a result of E. J. Janse van Rensburg, T. Prellberg, and A. Rechnitzer that was first discovered through the corresponding generating functions: the number of partially directed paths starting at the origin confined to the symmetric wedge y = +̲ x with k north steps is equal to the number of matchings on [2n] with k nestings. Furthermore, we propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M, s, A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.
|
2 |
New Perspectives of Quantum AnaloguesCai, Yue 01 January 2016 (has links)
In this dissertation we discuss three problems. We first show the classical q-Stirling numbers of the second kind can be expressed more compactly as a pair of statistics on a subset of restricted growth words. We extend this enumerative result via a decomposition of a new poset which we call the Stirling poset of the second kind. The Stirling poset of the second kind supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done. We also give a bijective argument showing the (q, t)-Stirling numbers of the first and second kind are orthogonal. In the second part we give combinatorial proofs of q-Stirling identities via restricted growth words. This includes new proofs of the generating function of q-Stirling numbers of the second kind, the q-Vandermonde convolution for Stirling numbers and the q-Frobenius identity. A poset theoretic proof of Carlitz’s identity is also included. In the last part we discuss a new expression for q-binomial coefficients based on the weighting of certain 01-permutations via a new bistatistic related to the major index. We also show that the bistatistics between the inversion number and major index are equidistributed. We generalize this idea to q-multinomial coefficients evaluated at negative q values. An instance of the cyclic sieving phenomenon related to flags of unitary spaces is also studied.
|
3 |
HILBERT BASES, DESCENT STATISTICS, AND COMBINATORIAL SEMIGROUP ALGEBRASOlsen, McCabe J. 01 January 2018 (has links)
The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.
Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.
In Chapter 3, the aim is to characterize Hilbert basis elements of certain 𝒔-lecture hall cones. In particular, the main focus is the classification of the Hilbert bases for the 1 mod 𝑘 cones and the 𝓁-sequence cones, both of which generalize a previous known result. Additionally, there is much broader characterization of Hilbert bases in dimension ≤ 4 for 𝒖-generated Gorenstein lecture hall cones.
Finally, Chapter 4 focuses on certain algebraic and geometric properties of 𝒔-lecture hall polytopes. This consists of partial classification results for the Gorenstein property, the integer-decomposition property, and the existence of regular, unimodular triangulations.
|
Page generated in 0.5207 seconds