Through the definition of a new insertion algorithm this paper seeks to provide an alternative to the existing bijections between permutations and certain kinds of tableaux. We will define two versions of each algorithm covered, both the existing ones and the novel one. These different constructions will include one using a lot of small intermediate steps and one which directly creates the tableaux from the permutation. After showing that these are equivalent, we will briefly discuss the results of pattern avoidance on tableau shape. / Doctor of Philosophy / Building up tableaux from permutations can be a helpful way to get information about that permutation without having to check by hand. Different methods of building tableaux will tell us different types of information about the permutation. For that reason, we are defining a new method of building tableaux so that we can extract useful information from the permutations used.

We construct a new operation among representations of the symmetric group that interpolates between the classical internal and external products, which are defined in terms of tensor product and induction of representations. Following Malvenuto and Reutenauer, we pass from symmetric functions to non-commutative symmetric functions and from there to the algebra of permutations in order to relate the internal and external products to the composition and convolution of linear endomorphisms of the tensor algebra. The new product we construct corresponds to the Heisenberg product of endomorphisms of the tensor algebra. For symmetric functions, the Heisenberg product is given by a construction which combines induction and restriction of representations. For non-commutative symmetric functions, the structure constants of the Heisenberg product are given by an explicit combinatorial rule which extends a well-known result of Garsia, Remmel, Reutenauer, and Solomon for the descent algebra. We describe the dual operation among quasi-symmetric functions in terms of alphabets.

It is not hard to see that the number of equiangular lines in a complex space of dimension $d$ is at most $d^{2}$. A set of $d^{2}$ equiangular lines in a $d$-dimensional complex space is of significant importance in Quantum Computing as it corresponds to a measurement for which its statistics determine completely the quantum state on which the measurement is carried out. The existence of $d^{2}$ equiangular lines in a $d$-dimensional complex space is only known for a few values of $d$, although physicists conjecture that they do exist for any value of $d$. The main results in this thesis are: \begin{enumerate} \item Abelian covers of complete graphs that have certain parameters can be used to construct sets of $d^2$ equiangular lines in $d$-dimen\-sion\-al space; \item we exhibit infinitely many parameter sets that satisfy all the known necessary conditions for the existence of such a cover; and \item we find the decompose of the space into irreducible modules over the Terwilliger algebra of covers of complete graphs. \end{enumerate} A few techniques are known for constructing covers of complete graphs, none of which can be used to construct covers that lead to sets of $d^{2}$ equiangular lines in $d$-dimensional complex spaces. The third main result is developed in the hope of assisting such construction.

It is not hard to see that the number of equiangular lines in a complex space of dimension $d$ is at most $d^{2}$. A set of $d^{2}$ equiangular lines in a $d$-dimensional complex space is of significant importance in Quantum Computing as it corresponds to a measurement for which its statistics determine completely the quantum state on which the measurement is carried out. The existence of $d^{2}$ equiangular lines in a $d$-dimensional complex space is only known for a few values of $d$, although physicists conjecture that they do exist for any value of $d$. The main results in this thesis are: \begin{enumerate} \item Abelian covers of complete graphs that have certain parameters can be used to construct sets of $d^2$ equiangular lines in $d$-dimen\-sion\-al space; \item we exhibit infinitely many parameter sets that satisfy all the known necessary conditions for the existence of such a cover; and \item we find the decompose of the space into irreducible modules over the Terwilliger algebra of covers of complete graphs. \end{enumerate} A few techniques are known for constructing covers of complete graphs, none of which can be used to construct covers that lead to sets of $d^{2}$ equiangular lines in $d$-dimensional complex spaces. The third main result is developed in the hope of assisting such construction.

The Kostka-Foulkes polynomials describe the change of basis between Schur polynomials and Hall-Littlewood polynomials. In this paper, we extend this idea to the family of BCn Macdonald spherical functions, with multiparameter Kostka-Foulkes polynomials acting as the change of basis from the BC_n spherical functions to the type Cn Schur polynomials. We develop a Kato-Lusztig formula that describes the multiparameter BCn-Kostka-Foulkes polynomials. / Master of Science / The work done in [11] gives a formula to calculate Kostka-Foulkes polynomials that convert between two other forms of polynomials. However, this only applies in specific instances. In this paper, we generalize those ideas to allow for more parameters, and find that a similar formula still holds.

In this dissertation we will look at properties of two different posets from different perspectives. The first poset is the Rees product of the face lattice of the n-cube with the chain. Specifically we study the Möbius function of this poset. Our proof techniques include straightforward enumeration and a bijection between a set of labeled augmented skew diagrams and barred signed permutations which label the maximal chains of this poset. Because the Rees product of this poset is Cohen-Macaulay, we find a basis for the top homology group and a representation of the top homology group over the symmetric group both indexed by the set of labeled augmented skew diagrams. We also show that the Möbius function of the Rees product of a graded poset with the t-ary tree and the Rees product of its dual with the t-ary tree coincide. We discuss labelings for Rees and Segre products in general, particularly the Rees product of the face lattice of a polytope with the chain. We also look at cases where the Möbius function of a poset is equal to the permanent of a matrix and we consider local h-vectors for the barycentric subdivision of the n-cube. In each section we state open conjectures. The second poset in this dissertation is the Dowling lattice. In particular we look at the k = 1 case, that is, the partition lattice. We study inequalities on the flag vector of the partition lattice via a weighted boustrophedon transform and determine a more generalized version for the Dowling lattice. We generalize a determinantal formula of Niven and conclude with conjectures and avenues of study.

This thesis presents an introduction to Schur rings (S-rings) and their various properties. Special attention is given to S-rings that are commutative. A number of original results are proved, including a complete classification of the central S-rings over the simple groups PSL(2,q), where q is any prime power. A discussion is made of the counting of symmetric S-rings over cyclic groups of prime power order. An appendix is included that gives all S-rings over the symmetric group over 4 elements with basic structural properties, along with code that can be used, for groups of comparatively small order, to enumerate all S-rings and compute character tables for those S-rings that are commutative. The appendix also includes code optimized for the enumeration of S-rings over cyclic groups.

What is the cohomology of a graph? Cohomology is a topological invariant and encodes such information as genus and euler characteristic. Graphs are combinatorial objects which may not a priori admit a natural and isomorphism invariant cohomology ring. In this project, given any finite graph G, we constructively define a cohomology ring H*(G) of G. Our method uses graph associahedra and toric varieties. Given a graph, there is a canonically associated convex polytope, called the graph associahedron, constructed from G. In turn, a convex polytope uniquely determines a toric variety. We synthesize these results, and describe the cohomology of the associated variety directly in terms of the graph G itself.

The character theory of the symmetric group is a powerful method of studying enu- merative questions about factorizations of permutations, which arise in areas including topology, geometry, and mathematical physics. This method relies on having an encoding of the enumerative problem in the centre Z(n) of the algebra C[S_n] spanned by the symmetric group S_n. This thesis develops methods to deal with permutation factorization problems which cannot be encoded in Z(n). The (p,q,n)-dipole problem, which arises in the study of connections between string theory and Yang-Mills theory, is the chief problem motivating this research. This thesis introduces a refinement of the (p,q,n)-dipole problem, namely, the (a,b,c,d)- dipole problem. A Join-Cut analysis of the (a,b,c,d)-dipole problem leads to two partial differential equations which determine the generating series for the problem. The first equation determines the series for (a,b,0,0)-dipoles, which is the initial condition for the second equation, which gives the series for (a,b,c,d)-dipoles. An analysis of these equa- tions leads to a process, recursive in genus, for solving the (a,b,c,d)-dipole problem for a surface of genus g. These solutions are expressed in terms of a natural family of functions which are well-understood as sums indexed by compositions of a binary string. The combinatorial analysis of the (a,b,0,0)-dipole problem reveals an unexpected fact about a special case of the (p,q,n)-dipole problem. When q=n−1, the problem may be encoded in the centralizer Z_1(n) of C[S_n] with respect to the subgroup S_{n−1}. The algebra Z_1(n) has many combinatorially important similarities to Z(n) which may be used to find an explicit expression for the genus polynomials for the (p,n−1,n)-dipole problem for all values of p and n, giving a solution to this case for all orientable surfaces. Moreover, the algebraic techniques developed to solve this problem provide an alge- braic approach to solving a class of non-central problems which includes problems such as the non-transitive star factorization problem and the problem of enumerating Z_1- decompositions of a full cycle, and raise intriguing questions about the combinatorial significance of centralizers with respect to subgroups other than S_{n−1}.

The character theory of the symmetric group is a powerful method of studying enu- merative questions about factorizations of permutations, which arise in areas including topology, geometry, and mathematical physics. This method relies on having an encoding of the enumerative problem in the centre Z(n) of the algebra C[S_n] spanned by the symmetric group S_n. This thesis develops methods to deal with permutation factorization problems which cannot be encoded in Z(n). The (p,q,n)-dipole problem, which arises in the study of connections between string theory and Yang-Mills theory, is the chief problem motivating this research. This thesis introduces a refinement of the (p,q,n)-dipole problem, namely, the (a,b,c,d)- dipole problem. A Join-Cut analysis of the (a,b,c,d)-dipole problem leads to two partial differential equations which determine the generating series for the problem. The first equation determines the series for (a,b,0,0)-dipoles, which is the initial condition for the second equation, which gives the series for (a,b,c,d)-dipoles. An analysis of these equa- tions leads to a process, recursive in genus, for solving the (a,b,c,d)-dipole problem for a surface of genus g. These solutions are expressed in terms of a natural family of functions which are well-understood as sums indexed by compositions of a binary string. The combinatorial analysis of the (a,b,0,0)-dipole problem reveals an unexpected fact about a special case of the (p,q,n)-dipole problem. When q=n−1, the problem may be encoded in the centralizer Z_1(n) of C[S_n] with respect to the subgroup S_{n−1}. The algebra Z_1(n) has many combinatorially important similarities to Z(n) which may be used to find an explicit expression for the genus polynomials for the (p,n−1,n)-dipole problem for all values of p and n, giving a solution to this case for all orientable surfaces. Moreover, the algebraic techniques developed to solve this problem provide an alge- braic approach to solving a class of non-central problems which includes problems such as the non-transitive star factorization problem and the problem of enumerating Z_1- decompositions of a full cycle, and raise intriguing questions about the combinatorial significance of centralizers with respect to subgroups other than S_{n−1}.