Matching Items (2)
Filtering by
- All Subjects: cd-index
- All Subjects: Lattice theory
- Creators: Kierstead, Henry
Description
The uncrossing partially ordered set $P_n$ is defined on the set of matchings on $2n$ points on a circle represented with wires. The order relation is $\tau'\leq \tau$ in $P_n$ if and only if $\tau'$ is obtained by resolving a crossing of $\tau$. %This partial order has been studied by Alman-Lian-Tran, Huang-Wen-Xie, Kenyon, and Lam. %The posets $P_n$ emerged from studies of circular planar electrical networks. Circular planar electrical networks are finite weighted undirected graphs embedded into a disk, with boundary vertices and interior vertices. By Curtis-Ingerman-Morrow and de Verdi\`ere-Gitler-Vertigan, the electrical networks can be encoded with response matrices. By Lam the space of response matrices for electrical networks has a cell structure, and this cell structure can be described by the uncrossing partial orders. %Lam proves that the posets can be identified with dual Bruhat order on affine permutations of type $(n,2n)$. Using this identification, Lam proves the poset $\hat{P}_n$, the uncrossing poset $P_n$ with a unique minimum element $\hat{0}$ adjoined, is Eulerian. This thesis consists of two sets of results: (1) flag enumeration in intervals in the uncrossing poset $P_n$ and (2) cyclic sieving phenomenon on the set $P_n$.
I identify elements in $P_n$ with affine permutations of type $(0,2n)$. %This identification enables us to explicitly describe the elements in $P_n$ with the elements in $\mathcal{MP}_n$.
Using this identification, I adapt a technique in Reading for finding recursions for the cd-indices of intervals in Bruhat order of Coxeter groups to the uncrossing poset $P_n$. As a result, I produce recursions for the cd-indices of intervals in the uncrossing poset $P_n$. I also obtain a recursion for the ab-indices of intervals in the poset $\hat{P}_n$, the poset $P_n$ with a unique minimum $\hat0$ adjoined. %We define an induced subposet $\mathcal{MP}_n$ of the affine permutations under Bruhat order.
Reiner-Stanton-White defined the cyclic sieving phenomenon (CSP) associated to a finite cyclic group action on a finite set and a polynomial. Sagan observed the CSP on the set of non-crossing matchings with the $q$-Catalan polynomial. Bowling-Liang presented similar results on the set of $k$-crossing matchings for $1\leq k \leq 3$. In this dissertation, I focus on the set of all matchings on $[2n]:=\{1,2,\dots,2n\}$. I find the number of matchings fixed by $\frac{2\pi}{d}$ rotations for $d|2n$. I then find the polynomial $X_n(q)$ such that the set of matchings together with $X_n(q)$ and the cyclic group of order $2n$ exhibits the CSP.
I identify elements in $P_n$ with affine permutations of type $(0,2n)$. %This identification enables us to explicitly describe the elements in $P_n$ with the elements in $\mathcal{MP}_n$.
Using this identification, I adapt a technique in Reading for finding recursions for the cd-indices of intervals in Bruhat order of Coxeter groups to the uncrossing poset $P_n$. As a result, I produce recursions for the cd-indices of intervals in the uncrossing poset $P_n$. I also obtain a recursion for the ab-indices of intervals in the poset $\hat{P}_n$, the poset $P_n$ with a unique minimum $\hat0$ adjoined. %We define an induced subposet $\mathcal{MP}_n$ of the affine permutations under Bruhat order.
Reiner-Stanton-White defined the cyclic sieving phenomenon (CSP) associated to a finite cyclic group action on a finite set and a polynomial. Sagan observed the CSP on the set of non-crossing matchings with the $q$-Catalan polynomial. Bowling-Liang presented similar results on the set of $k$-crossing matchings for $1\leq k \leq 3$. In this dissertation, I focus on the set of all matchings on $[2n]:=\{1,2,\dots,2n\}$. I find the number of matchings fixed by $\frac{2\pi}{d}$ rotations for $d|2n$. I then find the polynomial $X_n(q)$ such that the set of matchings together with $X_n(q)$ and the cyclic group of order $2n$ exhibits the CSP.
ContributorsKim, Younghwan (Author) / Fishel, Susanna (Thesis advisor) / Bremner, Andrew (Committee member) / Czygrinow, Andrzej (Committee member) / Kierstead, Henry (Committee member) / Paupert, Julien (Committee member) / Arizona State University (Publisher)
Created2018
Description
The Tamari lattices have been intensely studied since they first appeared in Dov Tamari’s thesis around 1952. He defined the n-th Tamari lattice T(n) on bracketings of a set of n+1 objects, with a cover relation based on the associativity rule in one direction. Despite their interesting aspects and the attention they have received, a formula for the number of maximal chains in the Tamari lattices is still unknown. The purpose of this thesis is to convey my results on progress toward the solution of this problem and to discuss future work.
A few years ago, Bergeron and Préville-Ratelle generalized the Tamari lattices to the m-Tamari lattices. The original Tamari lattices T(n) are the case m=1. I establish a bijection between maximum length chains in the m-Tamari lattices and standard m-shifted Young tableaux. Using Thrall’s formula, I thus derive the formula for the number of maximum length chains in T(n).
For each i greater or equal to -1 and for all n greater or equal to 1, I define C(i,n) to be the set of maximal chains of length n+i in T(n). I establish several properties of maximal chains (treated as tableaux) and identify a particularly special property: each maximal chain may or may not possess a plus-full-set. I show, surprisingly, that for all n greater or equal to 2i+4, each member of C(i,n) contains a plus-full-set. Utilizing this fact and a collection of maps, I obtain a recursion for the number of elements in C(i,n) and an explicit formula based on predetermined initial values. The formula is a polynomial in n of degree 3i+3. For example, the number of maximal chains of length n in T(n) is n choose 3.
I discuss current work and future plans involving certain equivalence classes of maximal chains in the Tamari lattices. If a maximal chain may be obtained from another by swapping a pair of consecutive edges with another pair in the Hasse diagram, the two maximal chains are said to differ by a square move. Two maximal chains are said to be in the same equivalence class if one may be obtained from the other by making a set of square moves.
A few years ago, Bergeron and Préville-Ratelle generalized the Tamari lattices to the m-Tamari lattices. The original Tamari lattices T(n) are the case m=1. I establish a bijection between maximum length chains in the m-Tamari lattices and standard m-shifted Young tableaux. Using Thrall’s formula, I thus derive the formula for the number of maximum length chains in T(n).
For each i greater or equal to -1 and for all n greater or equal to 1, I define C(i,n) to be the set of maximal chains of length n+i in T(n). I establish several properties of maximal chains (treated as tableaux) and identify a particularly special property: each maximal chain may or may not possess a plus-full-set. I show, surprisingly, that for all n greater or equal to 2i+4, each member of C(i,n) contains a plus-full-set. Utilizing this fact and a collection of maps, I obtain a recursion for the number of elements in C(i,n) and an explicit formula based on predetermined initial values. The formula is a polynomial in n of degree 3i+3. For example, the number of maximal chains of length n in T(n) is n choose 3.
I discuss current work and future plans involving certain equivalence classes of maximal chains in the Tamari lattices. If a maximal chain may be obtained from another by swapping a pair of consecutive edges with another pair in the Hasse diagram, the two maximal chains are said to differ by a square move. Two maximal chains are said to be in the same equivalence class if one may be obtained from the other by making a set of square moves.
ContributorsNelson, Luke (Author) / Fishel, Susanna (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Jones, John (Committee member) / Kierstead, Henry (Committee member) / Spielberg, John (Committee member) / Arizona State University (Publisher)
Created2016