EQUALITY OF P-PARTITION GENERATING FUNCTIONS by Ryan Ward A Thesis Presented to the Faculty of Bucknell University in Partial Fulfillment of the Requirements for the Degree of Bachelor of Science with Honors in Mathematics May 2, 2011 Approved: Peter McNamara Thesis Advisor Karl Voss Chair, Department of Mathematics ii Acknowledgments First and foremost I would like to thank Professor Peter McNamara for his assis- tance and guidance over the past two years, without which this thesis would not have been possible. I would also like to thank the faculty, staff, and students of the Math- ematics Department for making my studies at Bucknell University both productive and enjoyable. iii Contents Abstract vi 1 Introduction 1 2 Mathematical Background 4 2.1 Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 P-partition Generating Functions . . . . . . . . . . . . . . . . . . . . 7 2.3 Quasisymmetric Functions . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Initial Results 16 4 Necessary Conditions for Equality 20 5 Sufficient Conditions for Equality 24 5.1 Removing from Known Equalities . . . . . . . . . . . . . . . . . . . . 24 5.2 Adding to Known Equalities . . . . . . . . . . . . . . . . . . . . . . . 27 6 Posets with Two Linear Extensions 32 7 Conclusion and Future Work 37 iv List of Figures 2.1 Example Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Example Labeled Poset . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Example P-partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Compositions and Permutations Corresponding to P-partitions . . . . 8 2.5 Example Calculation of K (x ,x ,x ) . . . . . . . . . . . . . . . . 10 (P,ω) 1 2 3 2.6 Sample P-partition Generating Function Equality . . . . . . . . . . . 10 2.7 Example Calculation of L(P,ω) . . . . . . . . . . . . . . . . . . . . . 13 2.8 Example Calculation of K (x) Using Linear Extensions . . . . . . 14 (P,ω) 3.1 Disjoint Union Poset . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Commutative Diagram of Poset Involutions . . . . . . . . . . . . . . . 18 4.1 Jump Sequence of a Sample Labeled Poset . . . . . . . . . . . . . . . 21 4.2 Jump Sequences Showing Impossibility of Equality . . . . . . . . . . 22 4.3 Antichain Sequence Conjecture Example . . . . . . . . . . . . . . . . 23 5.1 Removing Jump 0 Elements Preserves Equality . . . . . . . . . . . . 25 5.2 Removing Minimal Elements of Naturally Labeled Posets Preserves Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3 Adding Minimal Elements Preserves Equality . . . . . . . . . . . . . 28 5.4 Adding Minimal Elements Example . . . . . . . . . . . . . . . . . . . 29 5.5 Combining Labeled Posets in a Way that Preserves Equality . . . . . 30 5.6 Disjoint Union as Sum of Other Labeled Posets . . . . . . . . . . . . 31 6.1 Base Equality for Posets with Two Linear Extensions . . . . . . . . . 33 6.2 Sample Equality for Posets with Two Linear Extensions . . . . . . . . 34 6.3 Structure of Posets with Two Linear Extensions . . . . . . . . . . . . 35 6.4 Contradiction for Two Linear Extension Posets . . . . . . . . . . . . 36 7.1 Unexplained Equalities . . . . . . . . . . . . . . . . . . . . . . . . . . 38 vi Abstract To every partially ordered set (poset), one can associate a generating function, known as the P-partition generating function. We find necessary conditions and sufficient conditions for two posets to have the same P-partition generating function. We define the notion of a jump sequence for a labeled poset and show that having equal jump sequences is a necessary condition for generating function equality. We also develop multiple ways of modifying posets that preserve generating function equality. Finally, we are able to give a complete classification of equalities among partially ordered sets with exactly two linear extensions. 1 Chapter 1 Introduction Combinatorics is concerned with the study of finite sets. Two primary topics in combinatorics are ordered sets and generating functions. The focus of this thesis lies at the intersection of these topics. ‘ Many mathematically important sets have a natural order associated with them. For example, the positive integers have the usual order 1 ≤ 2 ≤ 3. A more interesting example is the set of subsets of the positive integers ordered by containment, e.g. {} ⊆ {1} ⊆ {1,2}. Note that in this example not every pair of elements can be compared. To illustrate, neither {1} is contained in {2} nor {2} contained in {1}. We call this order a partial order since some pairs of elements are incomparable. The study of general partially ordered sets (posets) is one of the main branches of modern algebraic combinatorics. Additionally, combinatorialists are often concerned with counting the number of elements in a particular finite set. Sometimes it is possible to derive an exact formula for the number of elements in a set. For example, the number of k-element subsets of CHAPTER 1. INTRODUCTION 2 {1,2,...,n} is known to be (cid:0)n(cid:1) = n! . However, it is often the case that it is more k k!(n−k)! feasible or more useful to construct a polynomial or power series that encodes this counting information. To illustrate, in the polynomial (1+x)n, the coefficient of xk equals the number of k-element subsets of {1,2,...,n}. A more interesting example is a power series that encodes the number of partitions of n, where a partition of n is a weakly decreasing sequence of positive integers whose sum is n. For example, the partitions of 4 are (4),(3,1),(2,2),(2,1,1), and (1,1,1,1). We denote the number of unique partitions of n by p(n). While no elementary formula for p(n) exists, the generating function (cid:80)∞ p(n)xn can be shown to be the expression (cid:80)∞ p(n)xn = n=0 n=0 (cid:81)∞ 1 . Polynomials or power series that encode counting information are known i=1 1−xi as generating functions. Relatedtothesetofpartitionsisthesetofcompositionsofn, whereacomposition ofnisawayofwritingnasasumofunordered positiveintegers. Forexample, (1,3,2) is a composition of 6 but not a partition of 6, while (3,2,1) is both a composition and partition of 6. In his 1971 Ph.D. thesis, Richard Stanley introduced P-partitions as a way to unify and interpolate between the ideas of partitions and compositions [7]. The “P” in P-partition denotes a partially ordered set. Each poset has an associated P-partition generating function, and these generating functions generalize many different combinatorial objects. Arguably the most important special case of P-partition generating functions are the skew Schur functions; classifying equalities among skew Schur functions is a topic of current research [6; 5; 1; 3]. This thesis is motivated by trying to examine the open question of skew Schur function equality in the more general P-partition generating function setting. The main goal of this thesis is to find necessary conditions and sufficient conditions for two partially ordered sets CHAPTER 1. INTRODUCTION 3 to have the same P-partition generating function. The paper is structured as follows. In Chapter 2 we provide the necessary back- ground on partially ordered sets, P-partitions, quasisymmetric functions, and P- partition generating functions. Chapter 3 collects initial results about P-partition generating function equality. In Chapter 4, we give some necessary conditions on the partially ordered sets for their generating functions to be equal. Given a P-partition generating function equality, we can modify the equivalent partially ordered sets in certain ways that preserve generating function equality; these sufficient conditions for equality are the subject of Chapter 5. In Chapter 6, we give a complete classification of equalities among partially ordered sets having exactly two linear extensions. Fi- nally, in Chapter 7, we summarize our work and discuss avenues for further research. 4 Chapter 2 Mathematical Background We first introduce the mathematical background and notation necessary to present our results. Further information about these subjects can be found in [8; 9]. 2.1 Posets Given a collection of comparable objects, it is natural to try to associate an order with them. We formalize this idea of ordering a collection of comparable objects with the notion of a partially ordered set (poset). Posets, and orderings in general, play a large role in combinatorics as they generalize many different combinatorial objects, as we will see in the case of P-partitions. We will be using posets to define generating functions whose equalities we examine. Before defining a poset, let us help build the reader’s intuition by introducing some example posets. (a) The positive integers ordered by ≤ form a poset, i.e. 1 ≤ 2 ≤ 3 ≤ ....