Caterpillars, Ribbons, and The Chromatic Symmetric Function by Matthew Morin B . S c , Simon Fraser University, 2003 A THESIS S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science The Faculty of Graduate Studies (Mathematics) The University Of British Columbia August 9, 2005 © Matthew Morin 2005 Abstract 11 Abstract For every n-vertex tree T , it is known that the chromatic polynomial x(T, k) is equal to k(k — l ) n _ 1 . It is known that the function in noncommuting vari-ables, yb(x) , distinguishes all simple graphs. In the midground, the question of whether or not the chromatic symmetric function X Q ( X ) distinguishes noniso-morphic trees is still open. We look at Stanley's expansion of X G ( X ) in terms of the power sum sym-metric basis { P A ( X ) | A h n) of A 7 1 , and identify properties of our trees in various coefficients of the p\ in this expansion for A " G ( X ) . B y restricting to the case when our tree is a caterpillar C , we shall use a correspondence between ribbons and caterpillars to look at the coefficients of the p\(x) in the expansion of X c ( x ) using ribbon classes. Among these ribbon classes we wil l have special interest in those which are symmetric. We show that the chromatic symmetric function distinguishes these symmetric classes from all other caterpillars. Contents i i i Contents Abstract i i Contents i i i Notations iv Acknowledgements vii 1 Introduction 1 1.1 Partitions, Compositions, Tableaux, and Ribbons 1 1.2 Symmetric Functions 4 1.3 Graphs and the Chromatic Symmetric Function 5 1.4 Ferrers Graphs 10 2 Ribbons 12 2.1 Ribbon-Caterpillar Correspondence 12 2.2 Ribbon Symmetries and Classes 16 2.3 Counting Ribbon Classes / Caterpillars 23 2.4 More with Corners 24 3 Coefficients of p\ in XG 29 3.1 Graphs 29 3.2 Trees 30 3.3 Caterpillar Coefficients via Ribbon Diagrams 32 3.4 Composition Classes 35 4 Distinguishing Certain Ribbon Classes 43 4.1 Hooks 43 4.2 Two Row Ribbons 46 4.3 Symmetric and Near-Symmetric Ribbons 47 5 Conclusions 51 Bibliography 53 Notations iv Notations Notation Meaning Page Reference The number of stable partitions of G of type A . P- 8 b A box of a diagram. P- 3 c A corner of a ribbon. P- 3 The j-th column of a diagram, or the P- 1 0 number of boxes in the j-th column of a diagram. P- 3 4 The number of corners of the ribbon pa. P- 3 5 cp deg(v) The number of corners of the ribbon p. P- 3 3 The degree of the vertex v. P- 5 e A n edge of the graph, tree, or caterpillar. P- 5 £ A ( X ) The elementary symmetric function corresponding to A . P- 4 MP) The number of F-tableaux of shape A . P- 9 h, i, j, k Indices. inc(P) The incomparability graph of the poset P. P- 9 Z(A) The number of parts of A . P- 8 m The number of vertices. P- 6 m A (x ) The monomial symmetric function corresponding to A . P- 4 m\(x)' The augmented monomial symmetric function corresponding to A . P 8 n The number of boxes in a ribbon. (Except in §2 .3 . ) P 2 0 The number of rows of a diagram. P- 1 0 P A ( X ) The power symmetric function corresponding to A . P 4 \PAXG The coefficient of p\ in XQ • P- 2 9 The number of columns of a diagram. P- 1 0 n The «-th row of p, or P- 1 0 the number of boxes in the i-th row of p. P- 3 4 r{cti) The row of pa corresponding to the part on. P- 3 8 s The number of vertices in the spine S. P- 14 « A ( X ) The Schur symmetric function corresponding to A . P 4 sne(b) The number of boxes strictly north and east of b. P- 3 4 ssw(b) The number of boxes strictly south and west of b. P- 3 4 u, v, w Vertices of a graph. P 5 Notations v Notation Meaning Page Reference A A subset of { 2 , 3 , . . . , n — 1}. P- 24 Ap The corner set of the ribbon p. P- 24 A' The reflection of A. P- 25 C A caterpillar. P 6 C(P) The conjugate of the ribbon p. P 2 D A Ferrers or skew diagram. P 2 D' The conjugate diagram of D. P 2 E The edge set of a graph. P 5 F A subset of E. P 7 G A graph. P 5 G(D) The Ferrers graph of the diagram D. P- 10 The inversion of the ribbon p. P- 16 L(T) The number of leaves of a tree T . P- 31 R{p) The 180° rotation of the ribbon p. P- 16 S The spine of a caterpillar. P 6 Sn The symmetric group on n letters. P 4 T A tree. P 6 V The vertex set of a graph. P 5 Xa The chromatic symmetric function of the ribbon pa. P- 35 x D The chromatic symmetric function of a diagram D. P- 10 *o The chromatic symmetric function of a ribbon P- 10 diagram D = p. XG The chromatic symmetric function of a graph G. P 7 YG The non-commutative symmetric function for G. P 9 X The sequence of indeterminants ( x i , X 2 , X 3 , . . . ) . P 4 X K The monomial correpsonding to the coloring K. P 7 x r The monomial correpsonding to the tableau T . P 4 N, E , S, A step in the north, east, south, or west P 2 or W direction respectively. N* A sequence of t steps north. P 3 The set of caterpillars. P 6 <*f (n + 4) The number of (n + 4)-vertex caterpillars. P- 23 C(n, c) The number of C-symmetric n-box ribbon classes P- 25 with c corners. The family of sets F C E(T) with X(F) = A. P- 30 Q The group G = {id, R, C, I}. P- 17 A/W(n + 4) The number of nonsymmetric (n + 4)-vertex P- 23 caterpillars. N{n,c) The number of nonsymmetric n-box ribbon classes P- 28 with c corners. TZ(n, c) The number of .R-symmetric n-box ribbon classes P- 25 with c corners. 5 The set of symmetric ribbons. P- 50 S' The set of near-symmetric ribbons. P- 50 S(n, c) The number of symmetric n-box ribbon classes with P- 25 c corners. The number of symmetric (n + 4)-vertex caterpillars. P- 23 r A tableau. P 1 The i, j-th entry of the tableau T . P 1 Notations vi Notation Meaning Page Reference a, /?, 7 Compositions of m and n. P 1 a* The i-th part of a. P 1 a c The conjugate of a. P- 35 a* The inversion of a. P- 35 a r The reversal of a. P- 35 OLp The composition corresponding to p. P 3 [a] The equivalence class of a. P- 35 x(G,fc) The chromatic polynomial of G. P 6 A coloring of a graph or diagram. P 6 A , p Partitions of n (or m). P 1 A / M The skew diagram, A skew \i. P 2 A , The i-th part of A . P 1 A(c) The partition obtained by deleting c from p. P- 33 A ( F ) The partition induced by the set F C E. P 7 A n The set of homogeneous symmetric functions P 4 in x of degree n. p, a Ribbons. P 3 PC; ""C The ribbons (modulo i") corresponding to C. P- 16 Pa The ribbon corresponding to a. P 3 PA The ribbon associated to the set A. P- 24 [P] The equivalence class of p. P- 17 [P]/ The equivalence class of p (modulo / ) . P- 17 2 T The set of partitions of T into two parts. P- 31 The set of partitions of G(p) into two parts. P- 33 The set of partitions of G(pa) into two parts. P- 35 C(«) The corners of a at the end of the rows. P- 41 i * The element j, repeated t times. P- 31 The partition with Vi parts of size i. P 1 h "is a partition o f P 1 h "is a composition o f P 1 "is isomorphic to" P 5 Acknowledgements vi i Acknowledgements I would like to thank all those friends, family, coworkers, and colleagues who have been in my life during the last few years. Your continual inspiration and support has been paramount to the completion of this work. I would like to give particular thanks to my advisor, Stephanie van Wi l l i -genburg, for keeping me busy, for always having helpful suggestions, and for doing such a thorough job editing. I would also like to thank Richard Anstee for taking the time to read through this thesis on my behalf, catching further typos and having fresh suggestions. Further thanks go out to Jeremy Mart in for taking a keen interest in my research, and an active role in the editing. A n d I must commend Richard Stanley for all the brilliance he adds to our field—in particular thanking him for his work on the chromatic symmetric function, from which this thesis was born. I also must take time to thank my brother Ryan for lending me a hand whenever my computer ran into difficulties (which was more often than not, it would sometimes seem). Finally, to Joanne, my darling: Thank you for taking my calls whenever I needed to take a break from work, no matter what the hour. Thank you for forcing me back to work whenever I would take too much time off. And thank you for being there, by my side, whenever and wherever I needed you. 1 Chapter 1 Introduction We first recall the definitions relevant for the following discourse. We shall be concerned with the topic of graphs, in particular trees, and their colorings. We shall also find use in looking at partitions and compositions of n, ribbon diagrams and the Ferrers graphs thereof. Additionally, we need to mention some well-known bases for the space A " of homogeneous symmetric functions of degree n. We shall remind the reader of the general definitions here, recalling the results that we will require. 1.1 Partitions, Compositions, Tableaux, and Ribbons A partition A of a positive integer n, written A h n, is a sequence of weakly decreasing positive integers A = (Ai , A 2 , . . . , Afc) with X ^ i L i = n - Given a partition A, we can represent it via the diagram of left justified rows of boxes whose ?-th row contains A, boxes. The diagrams of these type are called Ferrers diagrams. We shall use the symbol A when refering to both the partition and its Ferrers diagram. We may sometimes write A = ( l r i , 2T2,..., kTk) for the partition which has r\ parts of size one, r 2 parts of size two, . . . , and rk parts of size k. We say a — (a%, a 2 , • • • > c*fc) is a composition of n and write a \= n if each a* is a positive integer and 2Jt=i ai — n- If we relax the conditions to consider sums of nonnegative integers, that is, allowing some of the a?j to be zero, we obtain the concept of a weak composition of n. If a \= n we obtain a partition of n by reordering the c*i into weakly decreasing order. We shall sometimes abuse notation and refer to a composition of n as a partition of n when we really mean the associated partition. If A h- ra, we can fill the boxes of the Ferrers diagram A with the numbers 1,2,... ,n, obtaining a tableau T of shape A. We denote the entry in the i-th row and j-th column of A by %j. A generalized Young tableau of shape A is the array T obtained by filling the boxes of the Ferrers diagram of A with positive integers, repetition allowed. The content of a generalized tableau T is the weak composition a = (c*i, a 2 ; • • •, where j is the largest integer appearing in T , and for each 1 < i < j, ai is the number of times i occurs as an entry of T . A generalized tableau is said to Chapter 1. Introduction 2 be semistandard if each row gives a weakly increasing sequence of integers and each columns gives a strictly increasing sequence of integers. Example Here we consider a semistandard Young tableau with shape A = (4,4,2) and content /x = (2,2,3,2,1). Suppose partitions A = (Ai , A 2 , . . . , \j) h n and p = {1x1,112, • • •, Pk) \~ m, with m < n, k < j, and pi < A, for each i = 1,2, ...,k are given. Then diagramatically, A contains a copy of p in its top left corner. We can form the skew diagram A / / i by removing that copy of 11 from the top left corner of A. Given any diagram or skew diagram D, the conjugate diagram D' is obtained by simply transposing the array of boxes along the main diagonal. Example Here we consider the partitions A : the skew diagram X/p. (4, 4,2) and p = (3,1), and form The conjugates, A ' = (3,3, 2,2), p' = (2,1,1) and (X/p)' = X'/p' are shown below. A ribbon is a skew diagram that has a connected interior and contains no 2 x 2 array of boxes. The skew diagrams X/p and (A/p)' = A ' / / / shown in the above example are ribbons. In fact whenever p is a ribbon, then so is its conjugate p'. For ribbons p, we shall typically use C(p) to denote the conjugate diagram p'. We shall use n for the number of boxes in the ribbon under consideration. A n equivalent definition of ribbons consists of taking all walks formed by a finite sequence of north and east steps (or equivalently, south and west steps). We shall denote a step in the north, east, south, and west direction by N , E , S, and W respectively, and denote a walk by its sequence of steps in these four 1.1. Partitions, Compositions, Tableaux, and Ribbons 3 directions. We shall write N* for t successive steps in the north direction, and similarly for the other directions. Another way of obtaining ribbons is by compositions. Given the composition a = (c*i ,a2, • • • ,<*k) |= n, we can relate the ra-box ribbon pa with ctk+i-j boxes in the j-th row. We construct pa so that each row shares exactly one column with the row before it. Additionally, for each ribbon p, we can obtain a composition ap of n by listing, from bottom to top, the number of boxes in each row of p. This gives a bijection. We shall use this bijection to pass back and forth between ribbon and com-position representatives as we see fit. Both ribbons and compositions will later serve as representatives for certain classes of graphs known as caterpillars, which will be defined in §1.3. Example Below we see a ribbon p with 11 boxes. We may write p in terms of a walk as either E 5 N 2 E N E or W S W S 2 W 5 . P = Counting the number of boxes per row from bottom to top we obtain ap = (6,1,2,2)1=11. In a ribbon, a box b may fall into one of two categories: either the ribbon bends at that box or it does not. More precisely, given a box c in a ribbon p, we say that c is a corner of p if either: 1. There is a box of p immediately west of c and a box of p immediately north of c, or 2. There is a box of p immediately east of c and a box of p immediately south of c. Otherwise, we say that the box is a noncorner of p. Example Looking at the ribbon from the previous example, p = E 5 N 2 E N E = W S W S 2 W 5 , we see that p has 4 corners. • • • • Chapter 1. Introduction 4 1.2 Symmetric Functions In this section we consider an infinite set of variables x = ( x 1 ; x 2 , . . . ) and the ring of formal power series C[x]. B y Sn, we mean the group of permutations of the letters { 1 , 2 , . . . , n}. We can let each TT £ Sn act on elements f(xi,X2, • • •) G C[x] by defining 7 T / ( x 1 , X 2 , • • •) = / 0 * ^ ( 1 ) , 3 ^ ( 2 ) , • • • ,X^n),Xn+1,XN+2, . . .). (1.1) We are interested in certain functions / ( x i , X 2 , . . . ) € Cjx] which are fixed by each TT G S„ , for every n € N . For instance, the n-th power sum symmetric function, oo i=l is such a function, as is the n-th elementary symmetric function, Given a partition A = (Ai , A 2 , . . . , \k) by the power sum (resp. elementary) symmetric function corresponding to A we shall mean fe fc P A ( X ) = J\p\iM ( e *( x ) = IIex> W r e sP-)-i=l i=l Additionally, by the monomial symmetric function corresponding to A we mean m*(x) = where the above sum is taken over all distinct monomial terms of the form X i i X i z ' " X i k ' ^ e n ° t e t n a t m(")(X) = P"(x) a n < * m(l")( x) = era(x). Each of the p\, e\, and m\, are invariant under the action described in Equation 1.1. Further, it turns out that each of the sets {p^(x)| A h n}, { C A ( X ) | A h n } , and {m\(x)\ A h n } are independent and span the same space of functions; that is, they are all bases of a common space. This space, denoted A " , is called the set of homogeneous symmetric functions of degree n and is usually defined as the span of the m\(x) for A h n . For any tableau T of shape A = (Ai , A 2 , . . . , A&) we have the weighting * r = n ^ - - n f W With this, we can now define the last family of symmetric functions we shall have interest in mentioning. The Schur symmetric function corresponding to A is defined to be s * ( x ) = H x T ' T 1.3. Graphs and the Chromatic Symmetric Function 5 where the sum is taken over all semistandard tableaux T of shape A. If A is a partition of n, then s*(x) is a homogeneous symmetric function of degree n. As with the other symmetric functions, the set { S A ( X ) | A I- n) is a basis of A n . Further details can be found in [Sagan 2001]. We shall henceforth drop reference to the variables x and just write s\ in place of s\(x), and similarly with the other symmetric functions. 1.3 Graphs and the Chromatic Symmetric Function B y a graph G we mean a pair (V, E), where V is a finite set of elements, called the vertices of G, and E is a subset of V x V which we consider as unordered pairs of vertices, and call the set of edges of G. Often times one is interested in the cases when G can contain the same edge {u, v} more than once, which is called a multiple edge,, or when G can have edges of the form {v,v}, which are called loops. A l l the graphs that we shall work with are simple graphs, that is, those graphs with no loops or multiple edges. Given two graphs G i = (Vi , E\) and G 2 = (V2, E2), we say that G i and G 2 are isomorphic, written G\ = G 2 , if there is a one-to-one map <3> from V\ onto V2 which preserves edges. That is, a bijection $ : V i —> V2 such that {«, v} £ E\ if, and only if, {Q(u), € E2 (with correct multiplicity in the case of multiple edges). If an edge e has e = {vijV?}, we shall say that the vertices v± and V2 are endpoints of e, that the vertices v\ and v2 are incident to e, and that the vertices V\ and V2 are adjacent. We shall say that two edges are incident when they share a common vertex among their endpoints. For each vertex v, the degree of the vertex v, written deg(v), is the number of vertices adjacent to v. A walk in G is a sequence of vertices u = WQ, W\, W2, ..., Wk =v such that Wi is adjacent to tUj+i for each i = 0 , 1 ,2 , . . . , k — 1. In the case when all the vertices are distinct, we call the walk a path in G and we call u and v the endpoints. We say that u and v are connected by a path if there is a path with endpoints u and v. Path-connectedness gives an equivalence relation on V whose equivalence classes are called the connected components of G . A graph G' = (V, E') is a subgraph of a graph G = (V, E) if both V C V and E' C E. The subgraph G ' is called an induced subgraph of G if E' is the set of all edges in E whose endpoints lie in V. The subgraph G ' is a spanning subgraph if V = V. A subset of vertices is said to be stable if the subgraph induced by the set contains no edges. A graph in which the vertex set can be partitioned into two stable subsets is called a bipartite graph. Trees are graphs which are minimally connected. That is, those graphs G which have a single connected component and have the property that removing any edge of G increases the number of connected components. As such, trees are Chapter 1. Introduction 6 acyclic, that is, there are no walks of the form WQ, WI, w?,..., with wo = Wk-If T is an m-vertex tree one can show that T has m — 1 edges. Conversely, any connected m-vertex graph with m — 1 edges is a tree. For the details of these and other results on trees, see [West]. The vertices of T which have degree equal to one are called leaves, while the other vertices are called internal vertices. If both endpoints of an edge are internal vertices, it is called an internal edge. If v is a leaf, the only paths containing v have v as one of their endpoints. Hence, deleting v from G does not disconnect any pair of vertices from this graph. Therefore the induced subgraph corresponding to the vertex set V—{v} is a connected graph, and hence, another tree. Similarly, deleting all the leaves of T, by considering the subgraph induced by the set of internal vertices, we obtain another tree T". A caterpillar C is a tree for which this derived tree T" is a path. Equivalently, a caterpillar is a tree in which there is a path consisting of internal vertices of T, such that every vertex of T is either on the path, or adjacent to a vertex of the path. This path is called the spine of the caterpillar and is denoted S. We shall use "if to denote the set of all caterpillars. Example The tree we see below is a caterpillar; its spine has been highlighted. A k-coloring of a graph G, is a map K from the vertex set V into a A;-set of "colors", typically the set {1,2, 3 , . . . , k}. A coloring is said to be proper if there are no monochromatic edges. That is, K is proper when K(U) ^ K(V) for every edge E. For a coloring K, the color class of the color j is just the set of vertices v with K(V) = j. The color classes partition the vertex set, with their cardinalities giving a partition XK h | V | . Further, for a proper coloring the color classes are stable subsets of V. The function x{G, k) is defined to be the number of proper A;-colorings of G. It is called the chromatic polynomial of the graph G, and, as its name implies, it is a polynomial function in k. Details can once again be found in [West]. For every m-vertex tree T we have x(T,k) = k(k-iy (1.2) There are k choices for the color of the first vertex of T we choose to label. Now, if there are uncolored vertices left, then there is one which is adjacent to exactly one of the colored vertices, and there are k — 1 choices for its color. Therefore Equation 1.2 follows. 1.3. Graphs and the Chromatic Symmetric Function 7 We turn to the case when our set of colors is N = {1 ,2 ,3 , . . .} . Given a coloring K of an m-vertex graph G we shall write x K for the monomial term of degree m defined by For a graph G, the chromatic symmetric function J G ( X ) is defined by X G ( x ) = £ x " , K where the sum is over all proper colorings K. We note that Xa{lk) = x(G, fc), where l f c denotes setting x± = = ... = xy. = 1 and Xk+i = Xk+2 = • • • = 0, since then a monomial survives if, and only if, it comes from a proper coloring using the colors {1, 2 , . . . , fc}, in which case the contribution to the sum is 1. Permuting the color classes of a proper coloring of G yields another proper coloring of G, so the series XG(X) is indeed a symmetric function in the inde-terminants (xi,x%,X3,...). We shall again drop reference to the variables and write XQ in place of XG ( X ) . In this thesis we take interest in the following question of Stanley. Problem 1.3.1 Does the chromatic symmetric function distinguish every pair of nonisomorphic trees? That is, given nonisomorphic trees T i and T%, do we have XTX ^ XT2 ? To this end we look at expanding XG in terms of the bases for A m introduced in §1.2. For the power sum symmetric basis {p\\ A h m} we have the following expansion for XG-Theorem 1.3.2 [Stanley, 1995, Theorem 2.5] For an m-vertex graph G *G= £ ( - i ) | F W ) > FCE where E is the edge set of G and given FCE, A(F) is the partition of m whose parts correspond to the sizes of the connected components of the spanning subgraph of G with edge set F. In this thesis we shall use Theorem 1.3.2 to attack Problem 1.3.1. Results on XG for general graphs trees are collected at the beginning of Chapter 3. Chapter 2 yields, among other results, a correspondence between caterpillars and certain equivalence classes of ribbons, which we shall use in the latter portion of Chapter 3 to look at the analogue of Problem 1.3.1 restricted to the set of caterpillars. Finally in Chapter 4, we shall look at the chromatic symmetric function for some special classes of ribbons. We shall end by showing that there are collections Qm of m-vertex graphs such that: Chapter 1. Introduction 8 1. lim, \Qm\ = C O , 2. A l l graphs in Qm have the same chromatic polynomial, and 3. No two graphs from the Qm share the same chromatic symmetric function. Although we shall only use the expansion in Theorem 1.3.2 for our work with XQ, it is worth mentioning that there are expansions of XQ into the other bases we mentioned for which the coefficients of XG have graph theoretic inter-pretations. We now turn to defining the concepts needed to state the relevant theorems. As the remainder of this section is not used or referred to later on, it may be skipped by the busy reader. Instead of stating the result for the monomial symmetric basis, it is easier to deal with the augmented monomial symmetric basis m'x defined by m'x = r i ! r 2 ! . . . r^lmx, where A is the partition ( l r i , 21"2,... ,krk). Since {m\\ A V- m\ is a basis for A m , the set {m'x\ A I- m} is also a bases for A m . A stable partition of G is a partition 7r of the vertex set V in which every block of the partition is a stable subset—that is, in any given block of ir, no two vertices are adjacent. The type of 7r is defined to be the partition of n whose parts are just the sizes of the blocks of TT. From these definitions we find the following result. Theorem 1.3.3 [Stanley, 1995, Proposition 2.4] Let G be a graph and a\ be the number of stable partitions of G with type A. Given a graph G, we can obtain an oriented graph by giving each edge a direction, that is, by choosing one of the ordered edges (u, v) or (v, u) for each unordered edge {u,v} S E. A n oriented graph G is acyclic if there are no sequences of ordered edges of the form (wi,W2), (w^jWs), ..., (wk-i, Wfc), where Wk — w\. A vertex u of an oriented graph is called a sink if there are no edges of the form (u, v), for any vertex v. For the elementary symmetric functions, Stanley proves the following result. Then Theorem 1.3.4 [Stanley, 1995, Theorem 3.3] If then the number of acyclic orientations of G with j sinks is A h m ' ( A ) = J where l(X) is the number of parts of X. 1.3. Graphs and the Chromatic Symmetric Function 9 A relation & on a set Z is a subset of Z x Z, that is, ordered pairs of elements of Z. A poset (or partially-ordered set) P is a set with a relation 31 on it, that is, a subset of P x P, which is reflexive, antisymmetric, and transitive. More precisely, 1. (p,p) G ^ for a l l p G P , 2. (a, 6) G ^ and (b, a) £ @ only if a = b, and 3. (a, b) € & and (6, c) G ^ implies (a, c) G ^ . Given a poset P, the incomparability graph, inc(P), is the graph obtained by using the elements of P as vertices and having two vertices u and v adjacent if, and only if, they are incomparable in the poset, that is, neither (u, v) nor (v, u) lies in A poset is said to be (3+l)-free if it contains no induced subposet isomorphic to the disjoint union of a three-element chain and a one-element chain. Finally, we let / A ( P ) be the number of P-tableaux of shape A, where a P-tableau is a generalization of the Standard Young Tableau of shape A. W i t h the preceeding definitions we may now state the following result. Theorem 1.3.5 [Gasharov, 1994] Let P be a (3 + I)-free poset and G — inc(P). Then A graph G is said to be claw-free if it has no induced subgraph isomorphic to the complete bipartite graph on partite sets of size 1 and 3 respectively. Unfortunately, P is (3 + l)-free if, and only if, inc(P) is claw-free, so The-orem 1.3.5 only expresses the claw-free graphs G in terms of s\. As the only trees which are claw-free are the paths, this expansion holds little use for Prob-lem 1.3.1 unless it is shown to hold for graphs with claws as well. Failing that, perhaps one can obtain a different expansion for XG in terms of the in the case when G is not claw-free. The noncommutative version of the chromatic symmetric function, YG, is defined in exactly the same way as XG- We take K where V = {vi,V2,..., v m } and define K, The only difference is now the variables {xi,X2,...) no longer commute. This noncommutative function YG is certainly more robust than XG in the sense that it distinguishes more graphs. Theorem 1.3.6 [Gebhard/Sagan, 1999, Proposition 8.2] The noncommutative symmetric function YG distinguishes all graphs G with no loops or multiple edges. Chapter 1. Introduction 10 1.4 Ferrers Graphs Considering a Ferrers diagram D with o rows r 1 , r 2 , . . . , r 0 and q columns c i , C 2 , . . . , cq, one has the corresponding bipartite Ferrers graph G(D) obtained by letting the vertex set be {r%, r2, •.., rQ} U {c i , c 2 , . . . , c 9} and having vertex ri adjacent to vertex Cj whenever there is a box in the i-th row and j-th column of D. Example Here we see the Ferrers diagram corresponding to the partition A = (4, 4, 2) and its associated Ferrers graph. C i c 2 C3 c 4 Values intrinsic to the graph can be obtained from the diagram that gave rise to it. The number of edges is the number of boxes. The number of vertices is the number of rows plus the number of columns. The degree of the vertex v is the number of boxes in the row (or column resp.) that is labelled v. Two edges are incident if, and only if, the corresponding boxes share a row or column. Thus, given an edge e with associated box b, the number of edges incident to e is the number of boxes in the row and column containing b, not counting the box b itself. For a Ferrers diagram D with rows r-±, r2, • • ., rQ and columns ci,c2,.. •, cq, we say that a coloring of D is a map K : { r i , r 2 , . . .,r0,c1,c2, • • •, cq} —* N . We say that the coloring K is proper if n(ri) « ( C J ) whenever there is a box in the i, j-th position of D. Given a coloring K of a diagram D with rows r\, r2,..., rQ and columns c i , c 2 , . . . , C q , we set o q X k = ( n ^ ^ x n ^ i ) ) ' t = l 3=1 and define K where the sum is taken over all proper colorings of D. The proper colorings of G(D) are exactly the proper colorings of D, so we have XD = ^G(D) f ° r every Ferrers diagram D. We shall use this fact to avoid having to mention the Ferrers graph of the diagram, even when we are computing the chromatic symmetric function for that Ferrers graph. This way we can stay solely within the context of diagrams when we find it convenient. 1.4. Ferrers Graphs 11 We will see in the next chapter, that the set of Ferrers graphs of ribbon diagrams is exactly the set of caterpillars. We wil l then use the graph G and ribbon diagram p to look at XQ (XP resp.), in the power sum symmetric basis for A m . B y looking at various coefficients of the chromatic symmetric function in terms of properties of the graph (ribbon, composition resp.), we shall see that the chromatic symmetric function does distinguish certain classes of caterpillars. Chapter 2. Ribbons 12 Chapter 2 Ribbons In this chapter we will see that the class of caterpillars arises naturally from the set of ribbon diagrams. We then proceed to use these ribbon representatives to count certain symmetric caterpillars. 2.1 Ribbon-Caterpillar Correspondence We begin by finding which diagrams D give rise to trees. Proposition 2.1.1 A skew diagram is a ribbon if, and only if, its Ferrers graph is a tree. Proof For the forward direction, let p be a ribbon. Looking at p as a northeast walk, p consists of a finite number of north and east steps, say j north and k east, the order of the steps being immaterial. We shall show G(p) is a tree by showing that 1. G(p) has one fewer edges than vertices, 2. G(p) is connected. The number of edges in the graph G(p) is the number of boxes in the diagram p, which is one more than the number of steps in the walk, as an extra box is needed for the starting box of the walk. Hence G{p) has j + k + l edges. The j steps north imply j +1 rows in p, and the k steps east imply k + 1 columns in p, so G(p) has (J + 1) + (k + 1) = j + k + 2 vertices. Thus G(p) has the correct number of edges to be a tree. Since p is a ribbon, the diagram p is connected. Since adjacent boxes of the diagram correspond to incident edges in the graph, G(p) will also be connected. Thus every ribbon gives rise to a tree. Conversely, suppose £ is a skew diagram but not a ribbon. Then either £ is not connected, or it contains a 2 x 2 subdiagram of boxes. In the latter case we have a 4-cycle in G(£), so it cannot be a tree. Thus, we are left considering the case when £ is not connected. Taking ip to be a maximal connected subdiagram of £, then ip is also a skew diagram and since it cannot be all of £, there is some box b of £ not in ip. This box cannot be in the same row or column as any box in ip, since ip was chosen as maximal. This is because in any skew diagram, if two boxes share a row (column resp.), 2.1. Ribbon-Caterpillar Correspondence 13 then the diagram contains all the boxes between those two in that row (column resp.). Hence G(£) is not connected, as there is no path from any vertex in G(ip) to either vertex corresponding to the row and column containing of b. Therefore G(£) is not a tree. | Having seen that ribbons are the only skew diagrams giving rise to trees, we now identify which trees appear. Proposition 2.1.2 A graph G is a caterpillar if, and only if, G = G(p) for some ribbon p. Proof Recall that the caterpillars are those trees T that contain a path S, called the spine of the caterpillar, for which every vertex of T is either in S, or adjacent to a vertex in S. Since every edge has some pair of vertices as its endpoints, every edge of T is either on the spine (when both endpoints are internal vertices), or incident to an edge of the spine (when an endpoint is a leaf). For the duration of the proof we shall think of the spine in terms of its set of edges. We start by proving the converse direction. If p is a ribbon, we consider the set S of edges corresponding to the corners of p. It is clear that all boxes of p are in the same row (or column) as one of the corners, so every edge of G(p) is either associated to corner, or incident to an edge associated to a corner. Hence, to show G(p) is a caterpillar, we need only check that the edges in S form a path. Let Cov(p) be the set of corners of p and G(Cor(p)) be the induced subgraph which we wish to show is a path. Traversing the ribbon as a walk from southwest to northeast we find that each corner shares a row or a column with the next corner. Hence, the edge associated with a given corner is incident to the edge associated with the next corner in the ribbon. Hence, G(Cor(p)) is connected. Since there are no more than two corners in any given row or column, every vertex of G(Cor(p)) has degree < 2. Since additionally G(Cor(p)) is connected and acyclic, it is a path. Now consider the forward direction. Given a caterpillar C, let S be its spine. As C is a tree, there is only one bipartition of the vertex set of C (up to swapping the partite sets). Say there are partite sets Z\ and Z^, of sizes o and q respectively. We take an endpoint of S, which we may assume lies in Z\, and label it r-y. Now starting at r\, and following the path S, we iterate: 1. If vertex x is labelled r$ for some j, then we label the leaves adjacent to x with the unused labels among c\, C2, • • •, cq with the largest indices, then label the next element along the path 5, if there is one, with the largest indexed label remaining unused among c i , c 2 , . . . , cq. Chapter 2. Ribbons 14 2. If vertex x is labelled Cj for some j then we label the leaves adjacent to x with the unused labels among r i , r 2 , . . . , rQ with the smallest indices, then label the next element along the path S, i f there is one, with the smallest indexed label remaining unused among r\, r 2 , . . . , rQ. Once we finish traversing S, we wil l have labelled all of Z\ = { r i , r 2 , . . . , rQ} and Z2 = {c i , c 2 , . . . , c g }. By labelling the rows of a grid, top to bottom, by ri>R2, • • •, r0, the columns, left to right, by C i , c 2 , . • • ,cq, and by placing a box in the , C j - th position whenever the vertex labelled rj is adjacent to the vertex labelled Cj in the caterpillar C, we obtain a diagram pc with G(pc) — C. We now wish to show that the diagram pc is a ribbon. If w\, W2,w$,... ,ws is the spine of C written as a path of vertices, with u>i — r\, we let 6 = (Si, 62, • • •, Ss) be the sequence of degrees of S, that is Si — deg(u>i) for each 1 < i < s. Then pc is the ribbon obtained by the walk W ' 5 l " 1 S , 5 2 _ 1 W , 5 3 - : L . . . , since, starting with a box at coordinates (rj, cq), taking 61 — 1 steps west corresponds to the <5i — 1 edges adjacent to wi besides {r\,cq} (first the leaf edges, then the edge {11)1,11)2}), then <52 — 1 steps south for the J 2 — 1 edges adjacent to w2 besides {11)1,11)2} (first the leaf edges, then the edge { ^ 2 , ^ 3 } ) , and so forth. | Example Here we see the process of going from caterpillars to ribbons with a caterpillar with eight vertices. On the left the spine is highlighted and an end of the spine has been labelled ri. On the right we have finished labelling the vertices by the above procedure. Here, o = q = 4, and s = 3. Since the spine S = wi, 1112,11)3 = r i , c 2 , r 4 we obtain the degree sequence S = (3,4,2) and predict the ribbon p = W W S S S W . C3 T2 c 4 ri c2 r 4 C l ^3 Starting with the edge { r 1 ; c 4 } of C we place a box in the position ( r i , c 4 ) of the 4 x 4 grid whose rows are labelled top to bottom with coordinates r 1, r 2 , r$, r 4 and whose columns are labelled left to right with coordinates c i , c 2 , C3, c 4 . 2.1. Ribbon-Caterpillar Correspondence 15 c 4 C3 ri ci c 2 c 3 c 4 C2 4^ C l r4 Now for each edge {ri,ct} incident to T\ besides { r 1 ; c 4 } , we place a box in position (1, i). Since these edges are incident to r± these boxes are all in the row labelled r\, and by our method of labelling the the labels decrease one by one, so the boxes are placed one next to the other. There are deg{r\) — 1 such edges, so we have deg(r-y) — 1 = J 1 — 1 = 2 westwards steps from ( r i , c 4 ) . By the choice of how we labelled the adjacent leaves and then we labelled the next vertex in the spine, the last box we add will correspond to an edge of the spine: in this case, the edge { r i , c 2 } . C3 C\ C 2 C 3 C 4 c 4 C2 f 4 r 2 r 4 • We proceed in the same way creating boxes for the vertices adjacent to the next vertex in the spine, c 2 in this case. As the edge {ry,c2} has already been used, we obtain deg(c2) — 1 = ( 5 2 - 1 = 3 more boxes, all placed in the column of c 2 . This adds (52 — 1 = 3 steps south to the walk. C3 c 4 C2 r 4 C l ^3 ri r3 r 4 C l c 2 c 3 c 4 • • This continues until we have reached the last vertex in our spine r 4 . Of the deg(r4) edges incident to r 4 , only the one spine edge incident to it has been counted so far, and the other edges give deg(r4) — 1 = 1 boxes to add to the row of r 4 , giving deg{r4) - 1 = 1 west step to finish our walk. Chapter 2. Ribbons 16 C3 c 4 r2 C2 C l ^3 V2 ^3 r 4 C i c 2 c 3 c 4 • • Had we started from the other end of the spine we would have obtained the following labelling of C, and ribbon: C2 c i r 4 C3 ri c 4 ^3 C l C 2 C 3 C 4 ^3 r 4 • • Hence, starting at opposite ends of the spine, we can potentially obtain two different ribbons from each caterpillar C. We shall write pc and ac, to denote these two ribbons. 2.2 Ribbon Symmetries and Classes For any ribbon p there are a few simple operations on the diagram that preserve the structure of the underlying caterpillar G(p). For instance rotating p by 180° gives another ribbon R(p) whose Ferrers graph is isomorphic to G(p). Rotating the diagram only serves to reverse the ordering of the rows and the columns, hence only reverses the indices of the vertex labels. If we think of p as a skew diagram, then the conjugate skew diagram C(p) is also a ribbon whose Ferrers graph is isomorphic to G(p). This action only swaps the row labels with the column labels. We shall call these two operations rotation and conjugation respectively. Composing these two operations acts to both swap the sets of row and column labels and reverse the orders of the labellings, and it is clear that the order in which these two actions are done is immaterial. We let I(p) = CR(p) = RC(p), and call I inversion. Looking at a ribbon as a sequence of steps, / acts to invert the direction of each step. For instance, inverting the northeast walk N ^ E ^ N * 3 . . . N t f c gives the northeast walk E t l N * 2 E * 3 . . . E t f c and inverting the southwest walk W ^ S ^ W * 3 . . . S*fc gives the southwest walk S^W^S* 3 . . . W* f c . 2.2. Ribbon Symmetries and Classes 17 Example Here we see the ribbon p — E N N N E E E E , its rotation R(p), its conjugate C(p), its inversion I(p), and their Ferrer graph G(p). C l C2 C3 C 4 C 5 C6 r i r 2 r 3 r 4 r2 r3 r4 c 6 c 5 c 4 c 3 c 2 Ci c 2 c 3 c 4 C5 C6 C(P) r4 r3 r 2 r i r4 R(p) C6 I{P) c 5 c 4 c 3 C2 Cl Let i d be the identity operation on the set of ribbons, that is for every ribbon p, id(p) = p. Then we claim the set Q = {id, R, C, 1} forms a group under composition. Each of the operations f G Q has f o f = id, the identity operation on the set of ribbons, so every element is its own inverse. Since RC = I = CR, RI = C = IR, and CI = R = IC, this set is closed under composition. As function composition is always associative, Q is a group as claimed. This group acts on the set of ribbons, so the orbits of the ribbons under this action partition the set of ribbons into equivalence classes of the form [p} = {p,R(p),C(p),I(p)}. We shall call any such set a ribbon class. From the comments at the beginning of this section the operations in Q preserve the underlying Ferrers graph. That is, members of a ribbon class share the same Ferrers graph. B y the equivalence class of a ribbon p modulo I, denoted p (modulo / ) , we mean the set {p,I(p)}. Since I{p) ^ p for every ribbon p, each equivalence class p (modulo / ) has exactly two elements. Since IR = CRR = C, we have Chapter 2. Ribbons 18 [R(p)]r = {R(p), C(p)}. Thus for each ribbon class [p] we have the decomposi-tion \p] = \p]iU[R{p)]i. For both f — R and / = C we ask for which p do we have f(p) — p, that is, which ribbons are f-symmetric. We shall call a ribbon symmetric if it is either R- or (7-symmetric. We note that no ribbon with more than one box could be /-symmetric, since looking at p as northeast walk, p begins with a step north if, and only if, I(p) begins with a step east. Recall from the example and comments after the proof of Proposition 2.1.2 that from a caterpillar C we can obtain the pair of ribbons pc, oc with Ferrers graph C. Lemma 2.2.1 If C is a caterpillar, the only ribbons (modulo I) that have G(p) == C are pc and ac-Proof Given a ribbon p with G(p) = C , numbering the fc — 1 corners in the northeast to southwest direction 1, 2,..., fc — 1 will form a traversal of the spine. We label the first box of p with a 0, and call it the zeroeth corner of p. Additionally, we label the last box of p with a fc and call it the fc-th corner of p. Up to inversion we assume p begins with a step west. For each j from 1 to fc we label the column or row (depending on the parity of j) that contains both the (J — l)-th aand j-th corners with a Wj. We label the column when j is even, and the row when j is odd. This acts to label every row and column that contains a corner with a Wi. That is, it labels every vertex which is part of the spine. Example Given the ribbon p = W 2 S 3 W , we label the z-th corner of p with an i, and label the rows and columns that contain a corner with the various W{ as described in the proof of Lemma 2.2.1. W2 U>3 Wi w2 W3 On the right we show the Ferrers graph G(p), with the vertices of the spine labelled with the row/column labels inherited from the ribbon p. Now, back to proving the lemma. If, as a walk, p = W t l S * 2 W * 3 . . . , then the number of steps from the (j — l)-th corner to the j - t h corner 2.2. Ribbon Symmetries and Classes 19 = [the number of boxes in the row (or column resp.) of Wj] — 1 = deg(wj) — 1. In the proof of Proposition 2.1.2, we created the ribbon pc by using the walk W < 5 l - 1 s ' 2 _ 1 W < 5 3 ~ 1 . . . where S = («Ji,<J2, • • •) was the degree sequence of the caterpillar's spine. Wi th this labelling we have pc = \^de9b"i)-l^deg(w2)-\-^deg{w3)-\ = W ^ S ^ W * 3 . . . = p, as desired. | For each caterpillar C, Lemma 2.2.1 shows the only ribbons with Ferrers graph C are pc and crc- In particular, if the degree sequence of the spine is (<5i, Si,...,6k), the proof translated it into a southwest walk, giving a ribbon pc = W * i - i S < 5 2 - i w * 3 - i Starting from the opposite end of the spine, we create another ribbon o~c = W , 5 f c _ 1 S 5 f c - 1 - 1 W ' $ f c - 2 ~ 1 . . . . Lemma 2.2.2 For any caterpillar C we have oc = R(pc) (modulo I). Proof From pc = W ' 5 l _ 1 S , 5 2 - 1 W ' 5 3 _ 1 . . . we obtain R(pc) = E * 1 ~ 1 N * , - 1 E * , - : i . . . . If A; is even, then R(pc) = E * 1 _ 1 N * 2 - 1 . . . E l 5 f c - 1 _ 1 N < 5 f c _ 1 and this latter walk is equivalent to ac = W < 5 f c _ 1 S , 5 f c - 1 _ 1 . . . w ' 2 _ 1 S ' 1 - 1 under the action of / , since J inverts the south and west steps in a southwest walk. If k is odd, then R(pc) = E ^ N * 2 - 1 . . . ] ^ - 1 - " ^ - 1 and this latter walk is ac- I Chapter 2. Ribbons 20 We summarise Lemma 2.2.1 and Lemma 2.2.2 as follows. Corollary 2.2.3 Given a caterpillar C and a ribbon p, C = G{p) if, and only if, p € \pc\- That is, the map taking C to \pc\ gives a bisection between the set of caterpillars and the set of ribbon classes. We now turn to look at the number of R- and C-symmetric ribbons. Lemma 2.2.4 Let n be a positive integer. 1. If n is even there are 2% R-symmetric n-box ribbons, and no C-symmetric n-box ribbons. 2. If n is odd there are the same number of R-symmetric n-box ribbons as there are C-symmetric n-box ribbons, namely 2 I V~ of each. Proof In the case where n is even we construct an f-box ribbon of half the desired length by choosing § — 1 steps north or east, starting from the initial box. From this we obtain 2^~x ribbons with ^ boxes. We can now obtain two .R-symmetric n-box ribbons from each of these by rotating 180° around the midpoint of either the north or east face of the top right box. These are the only two possibilities of an even boxed p stemming from the given half ribbon with R{p) = p, since once the direction from the last box (either north or east) is specified the rest of the desired ribbon is fixed from the ribbon's rotational symmetry. A l l .R-symmetric ribbons p arise in this way, since taking the first half of p, the only ways of completing the half ribbon to be .R-symmetric are those above. Hence we find 2 x 2 * - 1 = 2? .R-symmetric n-box ribbons. If p is C-symmetric, then we claim it has an odd number of boxes. To prove this, we note that the main diagonal along which we tranpose the array of boxes must cross the diagonal of exactly one box of p. This single box is fixed under the action of C , whereas all other boxes in the ribbon are paired up by the action of C. Hence the total number of boxes is odd. In the case when n is odd we construct ribbons of approximately half the length; namely, we create 2~^~ ribbons of length I L 2 t ^ by choosing I L 2 Z ^ steps. As in the previous case, each of these half ribbons can be extended to two different symmetric n-box ribbons. This time one is .R-symmetric while the other is C-symmetric. Rotating by 180° through the center of the top right box gives an .R-symmetric ribbon, and it is the only symmetric ribbon extending the half ribbon whose next step after the initial ribbon was in the same direction as the last step of the half ribbon. A C-symmetric ribbon can be obtained by reflecting the half ribbon across the line y = —x with the origin taken as being in the center of the top right box. This is the only symmetric ribbon extending the half ribbon whose first 2.2. Ribbon Symmetries and Classes 21 step after the half ribbon was in the orthogonal direction to the last step of the half ribbon. Again, the two ribbons we obtain are distinct because they have a different number of corners, and all symmetric ribbons with an odd number of boxes arise in these ways. Since one of these was i?-symmetric and one was C-symmetric, we find that there are 2IL2~ .R-symmetric and 2 2 V _ C-symmetric n-boxed rib-bons. | Example Suppose we wish to create two ii-symmetric ribbons with n — 8 boxes stemming from the half ribbon E N N with four boxes. If we chose the next step in our ribbon to be north (resp. east), then the point that the com-pleted ribbon wil l be rotated around wil l be the midpoint of the northern (resp. eastern) face of the top right box of our initial ribbon. Rotating the initial ribbon 180° through that point completes the J?-symmetric ribbon. The ribbons we obtain from these two rotations are certainly distinct from one another as they have a different number of corners. Any /^-symmetric ribbon p of length eight can similarly be constructed. The first four boxes of p determine a ribbon of half the desired length, and rotating this half ribbon about the midpoint of either the north or east face of the top right box wil l give p. Example Here we look at the case n = 11. We are looking to create symmetric 11-box ribbons. After the first 6 boxes of the ribbon are determined, choosing the direction of the next step determines the type of symmetry we can obtain. If the direction of the next step is the same as the direction of the last step, then one can create an .R-symmetric ribbon by rotating the half ribbon 180° around the center of the top right box. Here we use the half ribbon given by E E N E E , and choose the direction of the next step to be east: Chapter 2. Ribbons 22 If the direction of our next step is in a different direction than the last step of our half ribbon, then one obtains a C-symmetric ribbon by reflecting across the line y — —x. Hence, starting with the same half ribbon E E N E E , and choosing the next step to be north we obtain the following C-symmetric ribbon: We shall say that a ribbon class [p] is R-symmetric when the members of its class are .R-symmetric, and that it is C-symmetric when the member of its class are C-symmetric. We shall say that a ribbon class is symmetric when it is either R- or C-symmetric. If \p] is .R-symmetric (C-symmetric resp.), then, since p is a member of [p], p must be .R-symmetric (C-symmetric resp.). As we shall see the converse also holds. Lemma 2.2.5 Let p be a ribbon. The ribbon class [p] is R-symmetric (C-symmetric resp.) if, and only if, p is R-symmetric (C-symmetric resp.). Proof First we shall treat the .R-symmetric case. As the forward direction was proved directly before the statement of the lemma, we need only consider the converse direction. Let p be jR-symmetric, that is R(p) = p. We intend to show that each other member of [p] = {p, R(p), C(p),T(p)} is .R-symmetric. Since R(R(p)) = R(p), R(p) is i?-symmetric. Using CR — I = RC we find that R(C(p)) C(R(p)) C(P) so C(p) is i?-symmetric, and lastly R(I(p)) R(C(R(p))) R(C(p)) I{P) 2.3. Counting Ribbon Classes / Caterpillars 23 so I(p) is also P-symmetric. Therefore [p] = {p, R(p), C{p), I{p)} is P-symmetric, as desired. For the C-symmetric case, the proof can be obtained by swapping all oc-curences of R and C in the above proof. | 2.3 Counting Ribbon Classes / Caterpillars It is a known result that Theorem 2.3.1 [Harary/ Schwenk, 1973] The number of nonisomorphic caterpillars with n + 4 vertices is 2n + 2 L n / 2 - l . We shall prove the result here using ribbon diagrams. Proof (of Theorem 2.3.1) For the duration of the proof we shall say that a caterpillar C is symmet-ric or nonsymmetric if its associated ribbon pc is symmetric or nonsymmetric respectively. We note that Harary and Schwenk used an equivalent notion of symmetric caterpillars in their proof. As G(p) = G(I(p)), we shall consider ribbon diagrams (modulo / ) . Each ribbon comes from some walk consisting of north and east steps. We wil l use J to always choose the representative (modulo J) that begins with an east step. Having n + 4 vertices in a caterpillar requires n+ 3 edges, that is, a ribbon with n + 3 boxes, or a northeast walk with n + 2 steps. We have two choices (east or north) for all but the first step in the walk, so there are 2 n + 1 (n+3)-box ribbons (modulo / ) . By Lemma 2.2.1 and Lemma 2.2.2, for each caterpillar C we obtain the pair of ribbons (pc,R(pc)), that have C as their Ferrers graph. We have that pc = R(pc) if, and only if, pc is symmetric. So nonsymmetric caterpillars receive pairs of distinct ribbons. Applying G to either member of the pair yields C , so distinct_caterpillars wil l receive distinct ordered pairs. Every pair of the form (p, R(p)) wil l show up—namely, from the caterpillar C = G{p) provided in the proof of Proposition 2.1.2. Further, by Lemma 2.2.1 and Lemma 2.2.2, pc and R(pc) are the only ribbons (modulo I) that have C as their Ferrers graph. Hence, in computing G(p) for each of the 2 n + 1 (n+3)-box ribbons p (modulo / ) , we wil l obtain each of the nonsymmetric (n+4)-vertex caterpillars twice (for both pc and o~c) and the symmetric {n + 4)-vertex caterpillars only once, since they have pc = &c by Lemma 2.2.2. Thus, if S<g(n + 4) is the number of symmetric (n + 4)-vertex caterpillars, Af<#(n+4) is the number of nonsymmetric (n+4)-vertex caterpillars, and is the number of nonisomorphic (n + 4)-vertex caterpillars, then 2 n + 1 = 2ATv(n + 4) + S<#{n + 4). Chapter 2. Ribbons 24 Since ^ ( n + 4) = Af<g(n + 4) + S^(n + 4), this becomes 2 n + 1 = 2*?(n + 4) - S<e{n + 4). Hence "^(n + 4) = 2 n + s^i^+4\ and it only remains to count S<#(n + 4). B y Lemma 2.2.4, we find that there are 2n*~ .R-symmetric (n + 3)-box ribbons when n is odd (i.e., n + 3 is even), and both 2 ^ + 1 .R-symmetric (n + 3)-box ribbons and 2*+1 C-symmetric (n + 3)-box ribbons when n is even (i.e. n + 3 is odd). Since p ^ I(p) for every p we find n+3 1. If n is odd there are 2 2 2 = 2 ^ = 2^f J + 1 symmetric (n+3)-box ribbons (modulo J), and 2. If n is even there are 2 ? + 1 + 2 ? + 1 _ 2f+i = 2 L f J+ 1 symmetric (n + 3)-box ribbons (modulo J) . Hence in each case we obtain \S<e(n + 4)| = 2^-tJ+i. Thus <g(n + 4) = 2n + 2^J as desired. | 2.4 More with Corners Given an n-box ribbon p, we shall enumerate its boxes from southwest to northeast with the numbers 1,2,3, . . . , n. The corners of p give rise to a set Ap C {2, 3 , . . . , n — 1} called the corner set of p. Conversely, given a set A C {2, 3 , . . . , n — 1}, we associate the n-box ribbon PA obtained by taking the northeast walk starting with an step east that changes direction at the i-th box if, and only if, i € A. In this way, we are guaranteed that j4p(A) = A for each A C {2, 3 , . . . , n — 1}. Example Consider the ribbon class (modulo / ) , [p]/ = { E N N E E E , N E E N N N } shown below. We have labelled the boxes of each representative of [p]j from southwest to northeast with the numbers 1, 2 , . . . , 7 and obtained the corner set {2,4} in each case. Further, the members of [p]/ are the only seven-box ribbons that have corner set {2,4}. r 7 6 5 I 6 | 7 | [p]7 I" 5 3 2 3 4 2.4. More with Corners 25 Lemma 2.4.1 Let p and a be ribbons. Then Ap = Aa if, and only if, a € [p]i-Proof We shall think of p and a as northeast walks. Both ribbons p and I(p) as walks change directions after the same number of steps, hence their corner sets wil l be identical. Conversely, if p and a have the same corner set they change directions after the same number of steps. Hence, if the first step of p and a are in the same direction, then p = a, while if the first step of p and a are in different directions, then p = 1(a). | Given a set A C {2 ,3 , . . . ,n — 1}, we call the set A' = {n+1 —i\ i £ A} the reflection of A. If the set A satisfies A = A' we shall call A a symmetric subset. Lemma 2.4.2 Let p be a ribbon. Then AR^ = A'p = AC(P)-Proof In computing Ap and A^p^ (or Ap and AQ(P) resp.) we are enumerating the boxes from opposite ends of the ribbon. Since the the i-th box from one end of p is the ( n + 1 - i)-th box from the other end, the result follows. | Lemma 2.4.3 An n-box ribbon p is symmetric if, and only if, its corner set Ap is a symmetric subset of {2, 3 , . . . , n — 1}. Moreover, if p is symmetric, then p is C-symmetric if, and only if, G Ap. Proof If p is symmetric, then by Lemma 2.4.2 we find that Ap is symmetric. Now suppose Ap is symmetric, that is Ap = A'p. We take the sets Ay = Ap fl { 2 , 3 , L 2 ^ ] } ! ^ 2 = a n c * construct n-box ribbons pi = pAi for i= 1,2. Since we can assume both p and py begin with a step east, py shares its first half with p, while one of p 2 or I {pi) (call it p 3 for convenience) shares its second half with p. Since Ap is symmetric, Ap = Ay U J 4 2 - Given A? = A[, from Lemma 2.4.2 we have that A/ j ( P l ) = J 4 2 - Then by using Lemma 2.4.1 we find that p-$ € [R(pi)]i = {R(py), C(p i )} . When p$ = R(pi) the ribbon p is .R-symmetric, while if p3 = C(p i ) the ribbon p is C-symmetric. From Lemma 2.2.4 a symmetric ribbon p can be C-symmetric if, and only if, n is odd. Further, the proof showed p was C-symmetric if, and only if, the ^y^-th box was made to be a corner. | We will let TZ(n,c), C(n, c), and S(n,c) denote the number of distinct n-box ribbon classes with c corners which are .R-symmetric, C-symmetric, and symmetric, respectively. Hence <S(n, c) = TZ(n, c) + C(n, c). Further, we have Proposition 2.4.4 Let c be a nonnegative integer. 1. If c is even, then for each n € N Chapter 2. Ribbons 26 (a) TZ(n, c) = (b) C(n,c) = 0. 2. If c is odd, then ( — \ (a) C(n,c) = I cli I when n is odd, (b) C(n,c) = 0 when n is even, and (c) lZ(n, c) = 0 for each n € N . Proof We shall use the notation A! = {2,3,..., [^f 1 ]} fl Ap and A2 = A[ for the duration of the proof. Since A2 = A\, we have \A\ \ = \A2\. Suppose that p is an .R-symmetric ribbon. Since p is symmetric, we must have A\ U A2 = Ap. If n is even then we find Ai C { 2 , 3 , . . . , ^} and A2 C +1, ^ + 2 , . . . , n — 1} so clearly A% PI A2 = 0. In the case when n is odd have A1Q{2,3,..., ^} and A 2 C { = ± i , ^ + 1,.. . , n - 1 } and using Lemma 2.4.3 to note that ^ A p , we have A\ n v42 = 0- In either case c = | A p | = | y l 1 | + | y l 2 | = 2 | A 1 | is even. Thus we find TZ(n, c) = 0 for odd values of c. When n is even, then from Lemma 2.2.4 there are no C-symmetric n-box ribbons. That is, C(n,c) = 0 whenever n is even. We have so far proved parts (6) and (c) of 2. For 1 (b) we use Lemma 2.4.3. If p is C-symmetric then, exactly as above, Ai U A2 = Ap. Further, from Lemma 2.4.3 we have G J 4 p . Hence c = \AP\ = + | A 2 | - 1 = 2 x | A i | - 1 is odd, contradicting our assumption that the number of corners was even. Therefore there are no C-symmetric even-cornered ribbons. Now when both n and c are even, we create a map from the .R-symmetric classes \p] to the subsets of {2, 3 , . . . , j } of cardinality | by sending [p] to A\. Since p is symmetric, Lemma 2.4.1 and Lemma 2.4.2 show this map is well-defined. To construct an inverse, given a set A C { 2 , 3 , . . . , with \A\ = f, we first take the ribbon p = p(A) with ^ boxes. We then rotate p around the midpoint of either the north or east face of its top right box to complete the desired n-box ribbon. Both of the rotations of p wil l form an .R-symmetric ribbon, one of these having its ^-th box a corner, while the other does not. We choose one or the other depending on whether or not ^ € A. The resulting .R-symmetric ribbon p clearly has Ai = Ap ("1 { 2 , 3 , . . . , § } = A. Since we have constructed an inverse for our map, it is a bijection. Hence, ( — \ if both n and c are even lZ(n, c) = I \ 1, proving half of 1(a). 2.4. More with Corners 27 For the case when n is odd, we have a similar correspondence. Let p be a symmetric n-box ribbon, then Ay C { 2 , 3 , . . . , ^y^} implies A2 C { ^ ± i , . . . , n — 2,n — 1} and thus AyC\ A2 C {^y^}. Since p is symmetric, Lemma 2.4.3 shows that Ap is also symmetric; this gives Ay U A2 = Ap. If 2 ± i g A i then c = 2 x | A i | is even. If ^ G Ay, then ^ G A 2 a s well, and thus c = 2 x — 1 is odd. These two cases correspond to .R-symmetric and C-symmetric ribbon classes respectively. We create a map from the symmetric n-box ribbon classes to the subsets of { 2 , 3 , . . . , ^ y 1 } of cardinality [ ^ ^ J by sending [p] to Ay. Again, this is well-defined by Lemma 2.4.1 and Lemma 2.4.2. To construct an inverse, given a set A C {2, 3 , . . . , ^y^} we first take the half ribbon p = p(A). We then rotate this ribbon around the center of its top right box or reflect across that top right box to complete the desired n-box ribbon. Both of the ribbons obtained from p will be symmetric; the ribbon obtained by reflecting has its ^y^-th box a corner and hence is C-symmetric, while the ribbon obtained by rotating does not have its z^-th box a corner and is therefore R-symmetric. We shall choose one or the other depending on whether or not I i y ^ G A. The resulting symmetric ribbon p has Ay = Ap fl {2, 3 , . . . , ^^y^} = Ap = A , as desired. Since we have constructed an inverse for our map, we have a bijection. Hence, for odd n: ( — \ 1. If c is even, then Tt{n, c) = I \ j , and 2. If c is odd then C(n, c) = This completes the proof. | Example Directly after the proof of Lemma 2.2.4 we looked at an example where n = 8, so ^ = 4. Labelling the boxes of the diagrams of that example from southwest to northeast we see the two cornered .R-symmetric class generated by {2} C {2,3,4}, and the four cornered .R-symmetric class generated by {2,4} C {2,3,4}. 4 3 1 2 8 7 8 6 4 ' 5 3 1 2 Chapter 2. Ribbons 2 8 Both the ribbons obtained are i?-symmetric. Example Directly after the proof of Lemma 2 .2 .4 we looked at an example where n = 11 . Labelling the boxes from southwest to northeast we saw the two cornered .R-symmetric ribbon generated by { 3 , 4 } C { 2 , 3 , 4 , 5 , 6 } and the C-symmetric ribbon generated by { 3 , 4 , 6 } C { 2 , 3 , 4 , 5 , 6 } . 4 5 6 1 2 3 9 1 0 11 4 5 6 7 8 1 2 3 4 5 6 1 2 3 1 2 4 5 The set with 12^- = 6 £ A gives rise to the .R-symmetric ribbon, while the 6 G A gives rise to the C-symmetric ribbon. set with 2 + 1 We let Af(n, c) denote the number of nonsymmetric, n-box ribbon classes with c corners. Then there are <S(n, c) + M(n, c) n-box ribbon classes with c corners, and so by Corollary 2 .2 .3 and Theorem 2.3.1 we obtain ^ ( S ( n , c) + 7V(n, c)) = 2 " " 3 + 2 1 T J . c In computing jV(n, c) we find Proposition 2.4.5 Af(n, c) = \ ^ ™ ^ ^ — |<S(n, c). Proof Given a set of size c, say A = {a i , a2,..., a c} C { 2 , 3 , . . . , n — 1 } where a i < G.2 < . . . < a c , we can obtain the ribbon pA by taking the northeast walk E a i _ 1 N a 2 ~ a i E a 3 - a 2 . . . ( N or E)n~a-. The last step being north when c is odd, and east when c is even. From Lemma 2 .4 .3 , p is symmetric if, and only if, Ap is a symmetric subset. Hence, looking at \PA] for each AC { 2 , 3 , . . . , n - 1} , the nonsymmetric classes \p] will appear exactly twice, for both Ap and A'p, while the symmetric ribbon classes will appear only once. Hence 2A/"(n, c) + <S(n, c) = f n ^ V giving the desired result. | 29 Chapter 3 Coefficients of p\ in X q 3.1 Graphs In this chapter we begin looking at the coefficients of XQ- From Theorem 1.3.2 we have the following expansion for the chromatic symmetric function of a m-vertex graph: * G = £ ( - l ) | F | P A ( ^ , (3.1) FCE where E is the edge set of G and given F C E, X(F) is the partition of m whose parts correspond to the size of the connected components of the spanning subgraph of G with edge set F. It is clear that XQ is homogeneous of degree m. Hence graphs with different number of vertices have different chromatic symmetric functions. We use the notation [ P A ] ^ G to denote the coefficient of p\ in the expansion of XG in terms of the basis {p\\ A h m} of A m . We have \px]XG = £ (-1)1*1. (3.2) FCE A ( F ) = A The only way to obtain a partition of type ( l m ) would be to include no edges of G, so the only contribution to the coefficient of P(im) comes from F = 0. Hence, for every graph G Ip^Xa = 1. (3.3) The only way to obtain a partition of type (2, l m _ 2 ) is to include only one edge of G. Hence the only contributions to the coefficient of P(2,i™-2) comes from the A(F) with | F | = 1. From Equation 3.2 we obtain \PQ,i—*)]XA = -\E\, (3.4) for every graph G. Similarly we see | p ( 3 f c i l — « ) ] * G = ( - l ) V f e ( G ) , (3.5) where Pk{G) is the number of ways of selecting k vertex-disjoint edges in G, that is, the number of matchings in G of size k. Further if m is even, then the number of matchings which use every vertex as an endpoint exactly once, that is the number of perfect matchings p(G), has [ P ( 2 * ) ] * G = ( - ! ) * * * ( < ? ) • (3.6) Chapter 3. Coefficients of p\ in XQ 30 3.2 Trees We now consider the case where our graph G is an m-vertex tree T , for some m > 3. As trees are connected graphs with minimal edge sets, the number of connected components increases by one for each edge that is removed from the tree. Hence to obtain a partition with j parts, we would need to remove exactly j — 1 of the m — 1 edges in E. Hence we are looking at sets F C E with | F | = (m — 1) — (j — 1) = m — j. Thus we find xT = £ ( - i ) | F W ) F<ZE m ' = E E ( - i r - W > J=l F C E *(A(F))=j where the inner sum is over all F C E whose induced partition \{F) has j parts. Collecting terms that share the same partition type A gives \pX]XT = J2 ( - l ) m - ' ( A ) - (3.7) F C E A ( F ) = A If we let !FT,X = {F C E : X(F) = A} be the set of all edge subsets with induced partition of type A we obtain \px}XT = \TTtX\(-l)M-'W. (3.8) Thus we can write XT = E | ^ r , A | ( - l ) m - ' ( A ) P A . (3.9) Corollary 3.2.1 For m-vertex trees T\ and T2, X ^ , = XT2 if, and only if, I ^ T L A I = | ^ T 2 , A | for every A h m. For A = ( l m ) we get J~T,\ = {0}, so as we already saw for general graphs in Equation 3.3, [p(i"»)]AV = 1- Since removing any edge disconnects the tree, for A = (m) we find that !FT,\ = {E}. Hence \P(m)}XT = ( - l ) ™ - 1 . (3.10) In considering the A(F) with exactly two parts, we are looking at those partitions obtained by removing a single edge from T. We use IT to denote this set of partitions, that is 2 T = { A ( B - e ) : e e £ } , (3.11) 3.2. Trees 31 and shall call it the collection of two part partitions of T. We note that 2? is a multiset. We shall use the notation j * to denote t copies of j so that, for example, { l 3 , 3 2 , 4 } denotes the multiset {1,1,1, 3,3,4}. We have Corollary 3.2.2 / / T i and T2 are trees with 2Tl ^ 2T2, then X T L ^ X T I . Proof If X?! = XT2, then I ^ T I . A I = I-^H.AI for each A, in particular, for each A with two parts. Hence 2r, = 2T2 • | Each leaf of T is the endpoint of some edge, and since m > 3 no edge of T has both its endpoints being leaves. Thus we have the same number of leaves in T as the number of edges in T which have a leaf as an endpoint. Removing a single edge with a leaf endpoint from T gives the partition (m — 1,1), and such a removal is the only way to obtain this partition. Hence if L(T) is the number of leaves of T , then we have \p{m-i,i)]XT = ( - l ) m - 2 L ( T ) . (3.12) Thus we obtain Corollary 3.2.3 The chromatic symmetric function distinguishes trees with different number of leaves. If A = (fc, l " ~ f c ) , then the sets FCE with A(F) = A are those edge sets that give graphs with a single connected component of size fc, and have all other connected components of size 1. The component of size fc, being a connected subgraph of a tree, must also be a tree. Further, every fc-vertex subtree shows up in this way. Hence we find \p(KAM-K)}XT = ( - l ^ n , (3.13) where Tk is the number of fc-vertex subtrees of T. From this we obtain the following. Corollary 3.2.4 Letk be a positive integer. The chromatic symmetric function XG distinguishes m-vertex trees which contain a different number of k-vertex subtrees. Given a A h m, we let T\ be the number of partitions of T into disjoint subtrees of size Ai ,X 2 , . . . ,Xj , where j = l(X) is the number of parts of A. Generalizing Corollary 3.2.4 we obtain Theorem 3.2.5 If T is a tree and X is a partition of m, then \px]XT = (-l)m-l^Tx. Chapter 3. Coefficients of p\ in XQ 32 Given two edges of a tree, they are either incident or disjoint. Hence we have k>(2 M~-4)]Xr + |p(3 , im- S ) ]X T = ( ' f ' ) • (3-14) From this we see that knowing one of the coefficients of P(2 2 , i m ~ 4 ) and P( 3 1 m-3) is equivalent to knowing the other. Consequently, when checking which coefficients of X^ and XT2 are the same, we need only check one of the coeffi-cients of P(2 2,l" 1-' 1) o r P(3 , i m - 3 ) -Now consider looking at the sets F C E with | F | = A;. Since these are edge subsets of a tree, each additional edge in F decreases the number of connected components of the spanning subgraph with edge set F by one. Hence, we have l(X(F)) = m — k. Conversely, if we assume that F C E is such that l(\(F)) — m — k, then we must have \F\ = k. Thus, extending Equation 3.14 we find Proposition 3.2.6 Let T be an m-vertex tree and 0 < k < m — 1, then E = ( - i ) f c ( ' * ' ) = l(\)=m-k Proof B y the comments preceeding the proposition, we find E - E Xhm F C E l(X)=m-k \F\=k and by Equation 3.1 we have E &*]*r = E - (-Dfc ( 'f' ) -F C E F C E | F | = fc \F\=k where |F/| = m — 1, since T is a tree. | 3.3 Caterpillar Coefficients via Ribbon Diagrams We take m = n+1 and specialize to the case when the tree T is an (n+1)-vertex caterpillar. B y Proposition 2.1.2 we have an n-box ribbon p with T = G{p). By Corollary 2.2.3, \p] = {p, /?(p), C(p), I(p)} is the set of al l ribbons with T = G(p). From the proof of Proposition 2.1.2 we saw that given a ribbon p, the number of leaves in G(p) is precisely the number of boxes of p which are noncorners. Thus, the number of leaves of G(p) determines the number of corners of p, and vice-versa. Hence from Corollary 3.2.3 we obtain 3.3. Caterpillar Coefficients via Ribbon Diagrams 33 Corollary 3.3.1 The chromatic symmetric function distinguishes ribbons with different numbers of corners. We define cp = \AP\ to be the number of corners of p. For each corner c € Ap, deleting the box c from the diagram p would leave two ribbons with c — 1 and n — c boxes respectively. Hence removing the corresponding edge from G(p) induces the partition A(c) = ( c , n - c + 1). (3.15) Thus, from Equation 3.11 we obtain Proposition 3.3.2 For an n-box ribbon p with set of corners Ap, we find that the collection of two part partitions of the tree G(p) is given by 2 G W = { A ( c ) | c € A p } U { ( n , i r ^ } . For the sake of brevity, we shall henceforth write 2p in place of 2c(py Example For the seven-box ribbon p shown below, we use Equation 3.15 and Proposition 3.3.2 to calculate 2p. We have five boxes in p which are noncorners, so we obtain five copies of (7,1) h 8 in 2P. For the corners of p we use Equa-tion 3.15 with Ap = {2,5} and A'p — {3,6} to obtain the partitions (6,2) and (5, 3) respectively. 5 6 7 3 2 1 5,3 7,17,1 3 4 4 5 7,1 7,1 1 2 7 6 7,1 6,2 Hence 2P = {(7, l ) 5 , (6,2), (5, 3)}. Whenever A is a partition with two parts and T is a caterpillar there is a trivial bound on the coefficients of px, namely Proposition 3.3.3 Let T be an (n + 1)-vertex caterpillar and A have two parts. Then either 1. ( - l ) " - 1 | p A ] X r = L ( T ) , i / A = ( n , l ) , or 2. 0 < ( - l ) n _ 1 [ p A ] X T < 2 otherwise. Chapter 3. Coefficients of p\ in XQ 34 Proof From Equation 3.12, we have \p\]XT = ( - 1 ) U _ 1 L ( T ) in the case A = (n, 1). Any other partition A with two parts may arise as A(c) for some corner c of p. We shall show that any such A can arise at most twice. Consider computing A(c) = (c, n + 1 — c) for each corner c by starting from the bottom left corner and moving along the ribbon in a northeasterly direction. The first component of the pair (c, n + 1 — c) strictly increases and the second strictly decreases as we travel from corner to corner in this direction, hence any partition (c, n + 1 — c) could only appear at most twice, that is if both c and n + 1 - c S Ap. | Recall from the comments at the end of §1.4 we can use the notation Xp in place of XG(P)- From the proof of Proposition 3.3.3 we see that Corollary 3.3.4 If X = (k,n + 1 — k), 1 < k < n, is a partition of n+1 into two parts and p is a n-box ribbon, then \p\]Xp = (—\)n"1\{k,n — k} C\ Ap\. We now return to Equation 3.14, and inspect the coefficients of both P ( 2 2 , i " - 3 ) and P (3 , i "-2) in terms of the ribbon diagram. First, looking at the case of disjoint pairs of edges in T, we find Proposition 3.3.5 We have [ p( 22 , r—3 ) ] X p = J2bePssw(b) = £ fce P s ™ e ( & )> where both sums are over all boxes b in the ribbon p and ssw(b) (sne(p) respec-tively) denotes the number of boxes both strictly south and strictly west (north and east respectively) of b. Proof The coefficient of P(22,in-3) l s added to for each F C E with | F | = 2 and A(F) = (2 2 , l n _ 3 ) . This occurs exactly when F consists of a pair of disjoint edges. Hence we are interested in how many pairs of boxes in our diagram do not share a row or a column. For each 6, all ssw(b) boxes strictly south and strictly west of b are edges that are disjoint from the edge corresponding to b. Conversely, all pairs of disjoint edges correspond to boxes in different rows and columns, and so one is strictly south and west of the other. Hence, each pair of edges wil l be counted exactly once. This shows \p(22,in-3)]Xp = Ylbepssw^- ^ n e ^ a c t t n a t [P(2 2 , i"- 3)]^> = S t e p sne(b), is proved in exactly the same manner. | We now turn to the coefficient of P ( 3 i i " - 2 ) in Xp. Proposition 3.3.6 Let p have o rows and q columns, and let rj (c^ resp.) denote the number of boxes in the j-th row (k-th column resp.) of p. Then 3.4. Composition Classes 35 Proof A pair of edges in T = G(p) are incident if, and only if, the corresponding pair of boxes in p share a row or column in the diagram of p. | Example Consider the ribbon p generated by the walk E N N E . For each box b in p, we highlight the boxes of p which are both strictly north and strictly east of b. 6 4 Proposition 3.3.5 shows that \p^,i"-3)]Xp = 3 + 1 + 1 + 0 + 0 = 5. From Proposition 3.3.6 we have [ p ( 3 ) 1n-2 ) ] X p = 1 + 0+1 + 0 + 3 + 0 = 5 . Additionally, we can check that \pi22iln-3)]Xp + [ p ( 3 ) 1n-2 ) ] X p = 5 + 5 = 10 = ^ 2 ) > as predicted in Equation 3.14. 3.4 Composition Classes Recall that given a composition of n, say a = (a i , a2, a 3 , . . . , ak) \= n, we may associate an n-box ribbon, pa, with k rows by letting the (k + 1 — i)-th row of the diagram have a{ boxes. Conversely, starting with a ribbon diagram p with n boxes, we get a composition of n, ap by counting the number of boxes in a given row, for each row from bottom to top. This gives a bijection between the set of compositions of n and the set of n-box ribbon diagrams. Hence we shall sometimes use a in referring to both the composition and its corresponding ribbon. Thus for a composition a with corresponding ribbon pa, we shall abbreviate the terms cPa, XPa, 2Pa, and APa, by ca, Xa, 2a, and Aa respectively. Since we are only interested in the underlying Ferrers graph, we only care about the various ribbon classes [p] = {p, R(p),C(p), I(p)}. We use the no-tation ar = R(a), a° = C(a), and a1 = 1(a) when we are dealing with compositions as ribbons. Thus we have the corresponding composition classes [a] = {a, ar, a°, a 1 }. We shall call ac the conjugate of a, a1 the inversion of a, and ar the reversal of a. The choice of these names will be made clear in Proposition 3.4.1. Since the ribbon classes partition the set of ribbons, the set of compositions are partitioned by the classes [a] = {a, ar, a°,a 1}. Each composition class represents one of the n-box ribbon classes, and hence one of the caterpillars with (n + 1) vertices. Chapter 3. Coefficients of p\ in XQ 36 Example Let a = (2,1,1,5), then H - {(2,1,1,5), (5,1,1,2), (1,1,1,1,4,1), (1,4,1,1,1,1)}. a a1 Let /3 = (1,2,1,2,1,2,1), which is palindromic, that is, it is its own reversal and [/3] = {(1,2,1,2,1,2,1), (2,3,3,2)}, Let 7 = (2,3, 2,2,1,2,1), which is it own conjugate and [7] = {(2,3,2,2,1,2,1), (1,2,1,2, 2,3,2)}. (3 To calculate the members of the composition classes, we have the following. 3.4. Composition Classes 37 Proposition 3.4.1 If a — (a\, a2,0:3, • • •, oik) is a composition of n into k parts, then ar — (ctk,..., CY3, a2, cti). Now let oiij, a , 2 , o t i 3 , be the subsequence of those parts of a greater than 1. 1. If j = 0, (i.e. a = ( 1 , 1 , . . . , 1)), then ac = (n). 2. If 1 < ii and ij < k (i.e. c*i = c*fc = 1) then ac = (k- ij +1, l a ' ; - 2 , . . . , l Q i "+i - 2 , ih+1 -ih + l, l a i » ~ 2 , l a j i ~ 2 , h). 3. If 1 = i\ (i.e. ct\ > 1) then a>° is the same as the case when 1 < i\ and ik < n, except it ends with ( . . . , l " « > - 2 , i 2 - i i + l . l ^ i - 1 ) . 4- If ij = k (i.e. ctk > 1) then ac is the same as the case when 1 < i\ and ik < n, except it starts with ( l ^ - V . - ^ + U ^ - - 2 . . . ) . Example If a = (4,3,3,1,2), then i\ = 1, i2 = 2, 23 = 3, and i\ = 5. We can use the third and fourth cases of the above proposition to obtain ac = ( i « 5 - i ) 5 _ 3 + i ) i « 3 - 2 ) 3 _ 2 + i ) i « 2 - 2 ) 2 _ i + i i i a i - i ) = ( 1 2 ~ \ 5 - 3 + 1 , 1 3 ~ 2 , 3 - 2 + 1,1 3 ~ 2 ,2 - 1 + 1 ,1 4 _ 1 ) = (1,3,1,2,1,2,1,1,1). Suppose /? = (1,3,1,2,1,5,1). We have i\ = 2, i2 = 4, J3 = 6, and k = 1(0) = 7. This falls into the second case, and we obtain P° = ( f c - 6 + l , l ^ 6 _ 2 , 6 - 4 + l , l ^ - 2 , 4 - 2 + l , l ^ - 2 , 2 ) = ( 7 - 6 + 1, l 5 - 2 , 6 - 4 + 1 , l 2 - 2 , 4 - 2 + 1, l 3 - 2 , 2 ) = (2,1,1,1,3,3,1,2). Proof (of Proposition 3.4.1) It is easy to see that rotating a ribbon reverses the order of the rows, so aT = (ak, • • • ,a3,a2,ai). Part 1 merely states that conjugating a column with n boxes gives a row with n boxes. We now look to proving part 2. In this case, a both begins and ends with a 1, say ~ _ ( 1 * 1 - 1 n . n . -lih+i-ih-l _,. n . -\k-ij\ Chapter 3. Coefficients of p\ in XQ 38 For convenience, we shall let r(c*j) denote the row corresponding to a*. Starting from the single box in r(ax), the ribbon takes ii —1 north steps to arrive in the first box of r(ail). For each h, 1 < h < j, starting at the first box in r(aih), the ribbon takes ctih — 1 steps east to traverse all the boxes in this row. Then, for each 1 < h < j — 1, starting from the last box in r (a j h ) , it takes ih+i — ih — 1 steps north to traverse the ih+i — ih — 1 rows of length one between r(aih) and r(otih+1), and then one more step to arrive in the first box of r(c<ih+1). Thus there are ih+i — ih steps north between the steps east from the rows r{ctih) and r(oiih+1) in the diagram of a. Finally, from the last box of r{aii) the ribbon takes k — ij steps to traverse the k — ij rows of length one that lie above r(aii) in the diagram of a. From this we find the associated ribbon pa = N i l _ 1 E a i l _ 1 . . . E a i f c - 1 N £ ' , + 1 - i ' 1 E Q ! i ' > + 1 - 1 . . . E ^ " 1 ^ " ' ' . Since conjugation switches north with west, and south with east, we have C(pa) = W'^S"*'1 ...Sai*-1Wih+1~ihSai>'+i~1 ...Saii~1Wk~ij = Ek~ijNaii~1.. . N a i ' » + i ~ 1 E i h + 1 - i ' , N Q : i ' > ~ 1 . . . N a i l _ 1 E i l ~ 1 . Rewriting this as a composition by reversing the above procedure, we find ac = (k - y + 1, l a i i - 2 , . . . , l a ' H + i - 2 , - ih + 1 ,1" '* - 2 , . . . , la^-\ix) as desired. We now turn to proving part 3. In this case a has the form n , _ ( ' n , . i t 2 - i i - l i i h + , - i h - l \ In this case we obtain the corresponding ribbon pa = E a ' i _ 1 N * 2 _ ' 1 E a i 2 ~ 1 . . . E Q : i '> - 1 N i ' ' + 1 ~' h E a i ' '+ 1 ~ 1 and obtain C(pa) = S Q i ' _ 1 W i 2 _ i l S a i 2 _ 1 . . . S a i ' ' ~ 1 W i h + 1 " i h S a i ' ' + i " 1 . . . = . . . N a i h + i _ 1 E i ' 1 + 1 ~ i ' ' N a i f c - : 1 . . . N Q i 2 _ 1 E i 2 - i l N a i l _ 1 from which we compute the corresponding composition ac to be ac = (..., lai»+> ~ 2 , ih+1 - ih + 1, la<H - 2 , . . . , 1**2 - 2 , i2 - i x + l , - i ) as desired. 3.4. Composition Classes 39 Now looking at part 4, OL has the form In this case we obtain the corresponding ribbon pa — .. .Eaif*~1'Nih+1~ih'Eaih+1~1... E V i ' ^ r ' i - ' E " ' ) " 1 and obtain C(pa) = . . . S a i h _ 1 W * ' , + 1 - i ' ' S Q ! i ' ' + i _ 1 . . . S a i i - 1 _ 1 W < ' - i ' - 1 S 0 ! i i ~ 1 — N a < * _ 1 E * i _ * 5 ' _ 1 N a , < » - 1 _ 1 . . . N a i ' » + i _ 1 E i ' ' + 1 _ i ' ' N a i ' » _ 1 from which we compute the corresponding composition of to be ac = ( l ^ " 1 , ^ - + 1, l ^ - i ~ 2 , . . . , 1 ^ + 1 " 2 ; W l _ i f c + i , 1 ^ - 2 , . . .) as desired. | We obtain a few straightforward observations from this. For instance, a is palindromic, that is (a\, a2,0:3,..., ak) = (oik, • • •, 0:3, a2, ax), if, and only if, the ribbon pa is .R-symmetric. Since CR — RC, we see that (ar)° = (ac)r. Also, since the number of rows plus the number of columns of a n-box ribbon gives the number of vertices in G(p), we have n + 1 = o + q, (3.16) where o and q are the number of rows and columns of pa. Further, the number of rows (columns resp.) of pa is the number of parts of a (ac resp.), hence n + 1 =l(a)+l(ac). (3.17) Also, as one may have already guessed, we have the following. Proposition 3.4.2 Let a be a composition of n, where n > 2. Then \[a]\ = 2 or 4. Proof We begin by showing we cannot have both a = ar and a = ac. Firstly, if a composition a = (cti, a2,0:3,..., otk) has a = ar then from Proposition 3.4.1 OJI = ak. Now, if a — otc, from the Proposition 3.4.1 e*i > 1 if, and only if, a f c = 1 and ot\ = 1 if, and only if, ak > 1. That is, a = a° gives " i 7^ Otk-Chapter 3. Coefficients of p\ in XQ 40 Therefore we cannot have both a = ar and a = ac. If all four members are distinct, we are done. If a is palindromic, then ar ^ ac, lest both be a, and since ( a c ) r = (ctT)c = ac, a° is also paUndromic. Hence [a] = {a,ac}. Similarly, if a is its own conjugate, then aT ^ ac, lest both be a, and since (ar)c = (ac)r = ar, ar is also its own conjugate, giving [a] — {a, ar}. The cases ar — a1 and ac = a' can be reduced to one of the above cases by rotating or conjugating. The case a = a1, and equivalently the case aT = ac, cannot occur since there are no /-symmetric ribbons for n > 2. Hence the size of the composition classes is always 2 or 4, as desired. | Now, in interest of letting our corner work for ribbons carry over to com-positions, we look to see, given a, how many corners ca does the ribbon pa have? Proposition 3.4.3 If a is a composition with k parts greater than one, then 1. ca = 2k if a both begins and ends in a 1, 2. ca = 2k — 2 if neither the first nor last part of a is a 1, or 3. ca = 2k — 1 otherwise. Proof Every row of pa which has more than one box, besides the first and last, has exactly two corners in it. The first and last row have one corner if they have more than a single box, and none otherwise. Since the numbers of boxes in the rows of pa are just the parts of a, we are done. | From this we obtain the following. Corollary 3.4.4 If we have compositions a and f3, one with exactly one 1 among its first and last parts, while the other has either zero or two, then the corresponding ribbons have a different number of corners. Proof From Proposition 3.4.3, the number of corners of the two ribbons have different parity, and so cannot be equal. | Example Let a = (1,3,2,1,3,1) and 7 = (2,3,2,2,1,2,1), then by Corol-lary 3.4.3, pa has 6 corners while p 7 has 9. B y merely looking at the entries a ! , a 6 , 7 i , and 77, Corollary 3.4.4 shows that Ca c 7-Corollary 3.4.5 Let a and f3 be compositions with k and j parts greater than one respectively. If\k — j\ > 1, then ca cp. 3.4. Composition Classes 41 Proof If 7 is a composition with i parts greater than one, then by Proposi-tion 3.4.3 Oy € {2i, 2i - 1,2i - 2}. For \k - j\ > 2, the sets {2k,2k - l,2k - 2} and {2j,2j — l , 2 j — 2} are disjoint as the largest element of one set is strictly smaller than the smallest of the other. Hence ca =/= cp, as desired. | Example Let a = (1,3,2,1,3,1) and 7 = (2,3,2,1,2,3). Using CoroUary 3.4.5, since 5 — 3 = 2 > l , w e find that pa and p 7 have a different number of corners. In fact by Corollary 3.4.3 we find that ca — 6 while c 7 = 8. If two compositions do have ribbons with the same number of corners, we can still look at what partitions we obtain when we remove those corners. To this end, for a = ( c t i , a2,0:3,... ,afc) with parts a*, ,a, 2 , c t j 3 , . . . , > 1 (not including a t even if a* > 1), we define C(a) = {J>i 1,2, ••• , . /}• i<il Observe c £ C ( a ) 'f, a n d o n r y if, c is a corner of a which appears at the end of a row. Proposition 3.4.6 If a is a composition of n then 2a = {(c, n+l-c):ce Q(a) U C(a r )} U {(n, l ) n " c " } . Proof The set £(a) contains the corners of Aa which occur at the end of a row of a with more than one box, excepting the top row. Similarly the set £(ar) contains the corners of Aa which occur at the beginning of a row of a with more than one box, excepting the bottom row. Applying Proposition 3.3.2, we get the desired result. | Example Consider the composition a = (2,3,1,1,4,1) |= 12. From Proposi-tion 3.4.3 we compute ca — 5. Since only a i , a2, and 0:5 > 1, we have i\ = 1, i2 = 2, and i 3 = 5, and we compute C(a) = {2, 2 + 3, 2 + 3 + l + l + 4 } = { 2 , 5 , l l } . For aT = (1,4,1,1, 3,2), we have i\ = 2, and i2 = 5, (as £ ignores the final part of a) so we obtain C(a r ) = {1 + 4, 1 + 4 + 1 + 1 + 3} = {5,10}. Hence 2a = {(11,2), (8,5), (11,2)} U {(8,5), (10,3)} U {(12, l ) 7 } = {(8,5) 2 , (10,3),(11,2) 2 , (12,1) 7 }. Chapter 3. Coefficients of p\ in XQ 42 Thus, looking at various [PA]-Xc* for l(X) = 2, we have [P(ll,2)]^<* = - 2 , b(10,3)]^"a = - 1 , b ( 9 , 4 ) ] ^ a = 0, \p^5)]Xa = - 2 , \P(7,6)]XA = 0, and b(i2 , i )PQ* = - 7 . When [ai] ^ [a2] but 2 a i = 2a2, we look to other coefficients to distinguish the caterpillars. We have Proposition 3.4.7 If a — (ax, a2% c*3, • • •, c*fc) is a composition of n into k parts with conjugate ac = ( / ? I , / ? 2 J . • • ,/3n-k+i), then I p ^ X a = E ( ? ) + B E 1 ( ? ) -t=l v y i=l x J Proof The lengths of the rows and columns of a viewed as a ribbon are the parts of a and ac viewed as a composition. The result follows from Proposition 3.3.6. I Example Consider the two compositions of 9, a = (1,2,2,1,1,1,1) and (3 = (1,2,1,2,1,1,1). We discover [a] = {(1,2, 2,1,1,1,1), (1,1,1,1,2,2,1), (5,2,2), (2,2,5)}, and [/?] = {(1,2,1,2,1,1,1), (1,1,1,2,1,2,1), (4,3,2), (2,3,4)}, so [a] ^ [/?]. If we compute the two part partitions we find 2a = 2p. However, from Proposition 3.4.7 we find l \ / 5 \ . / 2 \ . / 2 + I 2 j + ^ 2 ) + { 2 J + V 2 = ( 0 + 1 + 1 + 0 + 0 +0) + (0 + 10 + 1 + 1) = 14. Similarly, we compute = (0+ 1 + 0 + 1 + 0 + 0 ) + (0 + 6 + 3 +1) = 12, so that X a Xp. 4 3 Chapter 4 Distinguishing Certain R i b b o n Classes As before we fix m to be the number of vertices in the tree. Since we are only interested in the Ferrers graph of the ribbons p, we shall work with the ribbon classes [p] = {p, R(p), C(p),I(p)}. 4.1 Hooks In this section we treat the case of the ribbons with a single corner. That is those ribbon diagrams which are a hook diagrams. We fix a total of m vertices and label the rows from top to bottom r\, r2, • • •, rQ, and the columns from left to right c i , C 2 , . . . , c q , so that m — o+q. Due to our operations R and C, if p has only one corner we may, up to our operations, assume that the corner is in the position ( r i , c i ) and that o < q. Hence, for two hooks p i and p2 to be distinct, we may assume both o\ < qi and 02 < 92, where o% =fi o2. Hence as partitions, (oi ,qi) ^ (o2,q2). Here we see the hook p with its boxes numbered from southwest to northeast. C i Cq o 1 o + q - l Looking at our corner set we have Ap = {o}. Since 2P is determined by the values A(o) = (o,m - o) = (o, q) and ( O I . Q I ) ± (o2,q2), we have 2Pl 2P2. Hence XPl ^ XP2, that is Proposition 4.1.1 Let p\ and p2 be hook diagrams, then XPl = XP2 if, and only if, [pi] = [ p 2 ] . Chapter 4. Distinguishing Certain Ribbon Classes 44 Moreover, we have the explicit expression for the chromatic symmetric func-tion of a hook diagram: Proposition 4.1.2 / / p is the hook with o rows and q columns, where o < q, then Xp = P ( i ° + « ) 2=1 + ^ ( - ^ ( ( " t - r 2 ) - ^ ! 9 : 1 ) ) ^ - - ' - 1 ) ° + q ~ 1 . / 0 _|_ — 2 \ ° - 1 + e (-1)*( 2-1 ) P ( i + i , i ° + " - i - 1 ) + y ^ c i » P ( ( i + i ) 2 , i ° + " - 2 i - 2 ) i=q ^ ' t = l + E ( - 1 ) J + f c ( c j f c + c f c j ) P 0 - + i , f c + i , i ° + < ' - i - f c - 2 ) l<J<fc<o-l o - l 9-1 + E m( _ 1 ) ' ' + ' i : c J f e Po'+ i , f c+ i , i o + ' '^ - f c - 2 ) ' .7 = 1 fc=o where cjk= ( °~1 ) ( 9" 1 ). Proof As before we can assume the rows are labelled from top to bottom , r 2 , . . . , rQ and the columns are labelled from left to right C\, c 2 , . . . , cq with the corner box in position r\C\. We have E = { n c i } U { r j C i | l < i < o} U { r i C j | l < j < <?}. Let E\ = { r j C i | l < i < o}, E2 = {riCj\l < j < q}, and e = { r j , c i } , so that = {e} U i ^ i U E2. Then e is incident with every edge of G(p), so for each FCE containing e, the edge set F induces a connected component with \F\ +1 vertices, that is X(F) = (\F\ + 1, i ^ - l ^ l - i ) . Hence Xp = £ ( - l ) ^ P A ( F ) F C E = E E ( - i ) | J W ) e G F C E F C E i U E 2 o+9-l = X I E ( - i ) * p ( i + i , i ° + « - i - 1 ) »=1 e € F C E \F\=i + E E H ) l f t U % u « FiCEi F 2 C E 2 4.1. Hooks 45 Thus we find that XP = E ( ° i - 1 ) P^+l,!^*-'- 1 ) i=l ^ ' + E E ( - 1 ) , f l l + | F 2 W l U f t ) - (4-i) FiCEi F2<ZB2 Now, every edge of E\ is incident with every other edge in E\. Thus for each F\ C E\, the only nontrivial component in the subgraph induced by the set of edges in F\ has | F i | + 1 vertices. Simlarly with E2. Further, these components are disjoint in the subgraph induced by the edge set Fi U F2, so A(Fi U F 2 ) = ( | F i | + 1, | F 2 | + 1, l°+*-\Fi\-W-2). Therefore E E ( - D ^ ' ^ W ^ ) = FxCBi F2GE2 = E E E E ( - D ^ ^ ^ W X U ^ 3=0 Fi C B i fe=0 F2 C B 2 I-P-I|=J 1^1=* o - l 9-1 = E E E E ( - i ) j + f c P A o + i , f c + i , i - + " - » - , b - 2 ) j=0 Fx C E i *:=0 F 2 C E 2 \Fi\=j \F2\=k o - l q-1 = EE(-DJ+FC (°7 1 ) (q~k 1 )^+1,fc+1,1—2). j=0fc=0 \ J / \ / Rearranging this last sum while writing cJk = j ^ (^^ ^) g i v e s fe=i ^ ' o~i 9 - 1 + E E(~ 1 ) J + f c c J f c PA(j+i , fc -n , i °+"- j - f c - 2 ) Chapter 4. Distinguishing Certain Ribbon Classes 46 = P(l°+«) + E(-1)' ( ° i 1 ) PHi+l,^"-'-1) i=l ^ ' + q~il ) p A ( i + i , i - + . - ' - i ) i= l \ ' o - l + ^ C j i p A ( ( i + 1 ) 2 | 1 o + , - 2 . - 2 ) i= l + E (- 1 )" 7 + ' S ( c Jfc + c f e j ) P ( j + l , f c + l , l ° + ' - i - f c - 2 ) l<7<fc<o-l o - l g - 1 J=l k=o Substituting this into Equation 4.1 gives the desired result. | 4.2 Two Row Ribbons In this section we consider those ribbon diagrams which have only two rows. More precisely, we consider those ribbon classes [p] which contain a member with two rows. Fixing m as q + 2, and labelling the rows r\ and r2 from top to bottom and the columns Cj, c2,..., cq from left to right, then the only possible ribbons with two rows are the pj, 1 < j < q, shown below. Pi r2 Moreover, we need only consider 1 < j < L^"J since R(p3) = pq+i-j gives fa] = \pq+1_j] for each 1 < j < q. Of these ribbons, pj has two corners except when j = 1, in which case it has only one corner. By Corollary 3.3.1 we have XPl ^ XPj for 2 < j < [^-\. Now consider j and k with 1 < j < k < [^^J- From Proposition 3.3.2, we get at most three distinct partitions of rn = q + 2 into two parts—each obtained by removing a single edge. We obtain a copy of (q + 1,1) from each of the noncorners and one more partition from each of the two corners. In the case of pj (pk resp.) we shall obtain the partitions (j, q — j + 2) and (j + 1, q — j; + 1) (fc resp.) from the corners and the copies of (q + 1,1) from the noncorners. 4.3. Symmetric and Near-Symmetric Ribbons 47 If Xp. = XPk then by Corollary 3.2.2, 2TJ = 2rk- Therefore the partition 0, 9 — J' + 2) must be equal to either (fc, q — k + 2) or (k + 1, q — k + 1). Clearly j < < k + 1 and this, together with k < L ^ y ^ J , gives j < k < 2k-k < q+1-k < q-k + 2. Hence j, being strictly less than each of fc, k + l,q — k + 1, and q — k + 2 makes it impossible for the partition (j, q — j + 2) to be either (k, q — k + 2) or (k + l,q-k + l). We have proven the following. Proposition 4.2.1 The chromatic symmetric function distinguishes the two row ribbon classes. 4.3 Symmetric and Near-Symmetric Ribbons We saw in Lemma 2.4.3 that a given n-box ribbon p was symmetric if, and only if, Ap is symmetric, that is if n + 1 — k S Ap whenever k £ Ap. Further if p is symmetric, then p is C-symmetric if, and only if, G Ap. Given an .R-symmetric n-box ribbon p, we let Ap f l { 2 , 3 , . . . , L 2 ^ ] } = {cj, c 2 , . . . , C j } , where 1 < c\ < c 2 < . . . < Cj < Then Ap = { c i , c 2 , . . . ,Cj} U {n + 1 - c i , . . . , n + 1 - Cj} which gives 2p = { ( c i , n + l - C i ) 2 , ( c 2 , n + l - c 2 ) 2 , . . . , ( c J - , n + l - c J ) 2 } U { ( n , l ) n - 2 j ' } . (4.2) Conversely by Corollary 3.3.4, if a ribbon p satisfies Equation 4.2, then both Ci and n + 1 — Ci £ Ap for each i = 1,2,.. . ,j. Hence Ap — { c i , c 2 , . . . , Cj} U { n + 1 - c i , n + 1 - c 2 , . . . , n+ 1 - Cj}, which shows that p is .R-symmetric. Thus the set 2P distinguishes i?-symmetric ribbons from the ribbons which are not .R-symmetric. Chapter 4. Distinguishing Certain Ribbon Classes 48 Further, since the two part partitions of any symmetric ribbon determines the ribbons corner set we have 2Pl = 2P2 APl = AP2 <s> M / = [P2]r, and hence Xp does distinguish among those ribbon classes (modulo I) that are .R-symmetric. Now if p is a C-symmetric n-box ribbon, then n is odd by Lemma 2.2.4 and =± i e Ap by Lemma 2.4.3. Let Ap D {2, 3 , . . . , ^} = {a, c 2 , . . . , Q , 2 ± i } , where 1 < C l < c 2 < . . . < ct < = ± i . Then A p = { c x , c 2 , . . . , Q } U { ^ ± 1 } U {n + 1 — c i , n H-1 — c 2 , . . . , n + 1 — c;}, which gives 2p = { ( ^ , ^ y 1 ) } U { ( c i , n + 1 - C i ) 2 , . . . , (chn+ 1 - c,) 2} U {(n, l ) " " 1 " 2 ' } . (4.3) Conversely, using Corollary 3.3.4, if a ribbon p satisfies Equation 4.3 with 1 < Ci < r}f-^, then G Ap and both Cj and n + 1 — Cj G Ap for each i = 1,2,.. .1. Hence n + 1 A p = { c i , c 2 , . . . ,a} U { } U { n + l - c i , n + l - c 2 , . . . , n + l - c/}, showing that p is C-symmetric. Hence 2P distinguishes C-symmetric ribbons from the ribbons which are not C-symmetric. Further, it distinguishes among those ribbon classes (modulo / ) that are C-syrnmetric since 2Pl = 2P2 APl = AP2 [pi]/ = [p 2]/. Since [pi]i = [pi]/ implies [pi] = [pi], we have shown the following. Theorem 4.3.1 The chromatic symmetric function distinguishes the symmet-ric ribbon classes from the nonsymmetric ribbon classes. Further, it distin-guishes among the symmetric ribbon classes. The caterpillars whose associated ribbon classes are symmetric can be visu-alized in an easy way. They are those caterpillars for which there is a line of symmetry that splits the spine in half. Example Here we see the Ferrers graph of two symmetric ribbons. 4.3. Symmetric and Near-Symmetric Ribbons 49 B y collecting various results, we find that we have proved the following. Proposition 4.3.2 There are collections Qm of m-vertex graphs such that: 1. l i m m ^ o o \Qm \ = oo, 2. x(Gi,k) = x{G2,k) for every pair of graphs Gi and G2 G Qm, «,nd 3. If Gi and G2 G Qm and XGX = XQ2, then d =G2. Proof We look at the collection Qm of caterpillars corresponding to symmetric ribbons with m — 1 boxes. We have property 1 by Lemma 2.2.4. Since all the caterpillars in Qm have the same number of vertices, we obtain property 2 via Equation 1.2. Finally Theorem 4.3.1 gives property 3. | Unfortunately, the method by which we proved Theorem 4.3.1 fails to distin-guish ribbons that are nonsymmetric, as the implication 2Pl = 2P2 => APl = AP2 fails to hold in this setting. Example The nonsymmetric ribbons pi and p2 shown below both have 2„ = {(5,2) , (4 ,3) , (6 ,1) 4 }, but clearly [px] ^ \p2]. Pi P2 We shall call a nonsymmetric ribbon p near-symmetric if Ap U {i} is a sym-metric subset for some number i G {2, 3 , . . . n— 1}. That is, p is near-symmetric if it is nonsymmetric, yet by changing one of its noncorners into a corner we obtain a symmetric ribbon. Example The ribbon p with ten boxes whose corner set is Ap = {3,4,8} is near-symmetric, as {3,4,7, 8} is a symmetric subset of {2, 3 , . . . , 9}. We can transform p into the symmetric ribbon it is near, by making the seventh box into a corner. This can be done by performing an inversion on the subdiagram of p consisting of the seventh box onward. Chapter 4. Distinguishing Certain Ribbon Classes 50 If p is near-symmetric, then for some % the multiset 2P is given by either 2P = { (c i , n + l - c 1 ) 2 , ( c 2 , n + l - c 2 ) 2 , . . . , ( c j , n + l - c j ) 2 } U { ( i , n + l - i ) } u { ( n , i r 2 i - 1 } when it is near to an .R-symmetric ribbon, or 2P = { ( c i , n + 1 - c i ) 2 , ( c 2 , n + 1 - c 2 ) 2 , . . . , (cj,n + 1 - Cj)2} U { ( ^ > U " + 1 - 0} U {(n, l ) - 2 ^ 2 } when it is near to a C-symmetric ribbon. The first of these two cases has only the two possible corner sets { c i , c 2 , . . . , Cj} U {n + 1 - c i , n + 1 - c 2 , . . . , n + 1 - Cj} U {i}, and { c i , c 2 , . . . ,Cj} U {n + 1 — c i , n + 1 — c 2 , . . . , n + 1 - Cj} U {n + 1 - i}, which are reflections of one another. Conversely, given the above two sets, Lemma 2.4.2 shows they belong to the same ribbon class, which is clearly a near-symmetric ribbon class. The second of these two cases has only the two possible corner sets n + 1 { c i , c 2 , . . . ,Cj} U {n + 1 - C i , n + 1 - c 2 , . . . , n + 1 - c,-}U {i, —— }, and n + 1 { c i , c 2 , . . . , Cj} U { n + 1 - c i , n + 1 - c 2 , . . . , n + 1 - Cj} U {n + 1 - i, —-—}, which again are reflections of one another. Again, given these sets, Lemma 2.4.2 shows they belong to the same ribbon class, which again is near-symmetric. Thus we find: Theorem 4.3.3 The chromatic symmetric function distinguishes the near-symmetric ribbon classes from those ribbon classes which are not near-symmetric. Further, it distinguishes among the near-symmetric ribbon classes. Hence if C is the set of caterpillars, <S is the set of caterpillars whose rib-bons are symmetric, and <S' is the set of caterpillars whose ribbons are near-symmetric, and if C i G C and C 2 € <SU<S', we find that Xd = Xc2 if, and only if, C i =• C 2 . 51 Chapter 5 Conclusions We had set out to study the chromatic symmetric function XQ in the case of G = T a tree, seeing how the chromatic symmetric function relates to the tree in question. The problem inspiring this thesis asked whether the chromatic symmetric function determines the tree it came from. We have been unable to obtain such a result at the present, but have had considerable success in the analogous problem restricted to caterpillars. We summarise our main results. Theorem 5.0.4 1. Let Ti and T2 be trees with XTX = XT2 , then (a) T i and T2 have the same number of edges and the same number of vertices. (b) T i and T2 have the same number of leaves. (c) For any k, T% and T2 have the same number of k-vertex subtrees. (d) For every A = (Ai , X2,..., A&) h m, T\ and T2 have the same number of partitions into disjoint subtrees of sizes A i , \ 2 , . . . , Afc. 2. The map taking [p] to G(p) is a bijection from the set of ribbon classes to the set of caterpillars. This map sends each ribbon class with n boxes and k corners to a caterpillar with n + 1 vertices and k internal edges. 3. For ribbon classes (or caterpillars equivalently), (a) If pi and p2 are ribbon classes with XPl = XP2, then p\ and p2 have the same number of boxes and the same number of corners. (b) Xp distinguishes among the hooks, that is, among those ribbon classes which contain a single corner. (c) Xp distinguishes among those ribbon classes that have two rows. (d) Xp distinguishes the symmetric and near-symmetric ribbon classes from all other ribbon classes, as well as distinguishes among the sym-metric and near-symmetric ribbon classes. (e) The composition classes [a] of n generate the n-box ribbon classes, so we can use these representations to: i. Enumerate the nonisomorphic caterpillars by generating the com-position classes. Chapter 5. Conclusions 52 ii. Explicitly calculate \px]XA for A = (2, l""1), (3, l""2), (22, l n " 3 ) , and every partition A with two parts without resorting to dia-grams of any sort. 4- Additionally, we have used our ribbon representatives to (a) Calculate the number of n-box ribbon classes with c corners. (b) Calculate the number of n-box ribbons that are R- and C-symmetric respectively, and the number of c-cornered n-box ribbons that are R-and C-symmetric respectively. (c) Calculate the number of nonisomorphic caterpillars with n vertices. It has been checked that XG distinguishes all nonisomorphic n-vertex trees for values of n up to 9. Using the composition and ribbon representations of caterpillars, I have checked that that XQ distinguishes all n-vertex caterpillars, for n = 10. It is still unknown whether XG distinguishes all nonisomorphic trees. We invite the reader to help investigate this and other open problems related to the chromatic symmetric function. Bibliography 53 Bibliography [Ehrenborg/van Willigenburg] Richard Ehrenborg and Stephanie van Willigen-burg, "Enumerative Properties of Ferrers Graphs," Discrete and Computa-tional Geometry 32 (2004), 481-492. [Gasharov, 1994] V . Gasharov, "Theory and Applications of Symmetric Func-tions," P h D Thesis, Brandeis University, 1994. [Gebhard/Sagan, 1999] David D . Gebhard and Bruce E . Sagan, " A Chromatic Symmetric Function in Noncommuting Variables," Journal of Algebraic Combinatorics 13 (2001), 227-255. [Gebhard/Sagan, 1999] David D . Gebhard and Bruce E . Sagan, "Sinks in Acyclic Orientations of Graphs," Journal of Combinatorial Theory Series B 80 (2000), 130-146. [Harary/ Schwenk, 1973] Frank Harary and Allen J . Schwenk, "The Number of Caterpillars", Discrete Mathematics 6 (1973), 359-365. [Sagan 2001] Bruce E . Sagan, The Symmetric Group: Representations, Combi-natorial Algorithms, and Symmetric Functions, Springer-Verlag, New York (2001). [Stanley, 1995] Richard P. Stanley, " A Symmetric Function Generalization of a Chromatic Polynomial of a Graph," Advances In Mathematics 111 (1995), 166-194. [Stanley, 1998] Richard P. Stanley, "Graph Colorings and Related Symmetric Functions: Ideas and Applications," Discrete Mathematics 193 (1998), 267-286. [West] Douglas B . West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, N J , (2001).
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Caterpillars, ribbons, and the chromatic symmetric...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Caterpillars, ribbons, and the chromatic symmetric function Morin, Matthew 2005
pdf
Page Metadata
Item Metadata
Title | Caterpillars, ribbons, and the chromatic symmetric function |
Creator |
Morin, Matthew |
Date Issued | 2005 |
Description | For every n-vertex tree T, it is known that the chromatic polynomial x(T, k) is equal to k(k — l )ⁿ⁻¹. It is known that the function in noncommuting variables, Y[sub G](x), distinguishes all simple graphs. In the midground, the question of whether or not the chromatic symmetric function X[sub G](x) distinguishes nonisomorphic trees is still open. We look at Stanley's expansion of X[sub G](x) in terms of the power sum symmetric basis {pλ(x)| λ|-n) of Λⁿ , and identify properties of our trees in various coefficients of the pλ in this expansion for X[sub G](x). By restricting to the case when our tree is a caterpillar C, we shall use a correspondence between ribbons and caterpillars to look at the coefficients of the pλ(x) in the expansion of X[sub C](x) using ribbon classes. Among these ribbon classes we will have special interest in those which are symmetric. We show that the chromatic symmetric function distinguishes these symmetric classes from all other caterpillars. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2009-12-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0079438 |
URI | http://hdl.handle.net/2429/17239 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2005-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2005-0565.pdf [ 2.37MB ]
- Metadata
- JSON: 831-1.0079438.json
- JSON-LD: 831-1.0079438-ld.json
- RDF/XML (Pretty): 831-1.0079438-rdf.xml
- RDF/JSON: 831-1.0079438-rdf.json
- Turtle: 831-1.0079438-turtle.txt
- N-Triples: 831-1.0079438-rdf-ntriples.txt
- Original Record: 831-1.0079438-source.json
- Full Text
- 831-1.0079438-fulltext.txt
- Citation
- 831-1.0079438.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079438/manifest