UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Combinatorial properties of maps on finite posets Chan, Brian Tianyao 2020

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
24-ubc_2020_november_chan_brian.pdf [ 554.63kB ]
Metadata
JSON: 24-1.0392434.json
JSON-LD: 24-1.0392434-ld.json
RDF/XML (Pretty): 24-1.0392434-rdf.xml
RDF/JSON: 24-1.0392434-rdf.json
Turtle: 24-1.0392434-turtle.txt
N-Triples: 24-1.0392434-rdf-ntriples.txt
Original Record: 24-1.0392434-source.json
Full Text
24-1.0392434-fulltext.txt
Citation
24-1.0392434.ris

Full Text

Combinatorial Properties of Maps on Finite PosetsbyBrian Tianyao ChanB. Sc., Pure Mathematics, University of Calgary, 2014M. Sc., Pure Mathematics, University of Calgary, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Mathematics)The University of British Columbia(Vancouver)July 2020c© Brian Tianyao Chan, 2020The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the dissertation entitled:Combinatorial Properties of Maps on Finite Posetssubmitted by Brian Tianyao Chan in partial fulfillment of the requirements forthe degree of Doctor of Philosophyin MathematicsExamining Committee:Stephanie van Willigenburg, Mathematics. SupervisorAndrew Rechnitzer, Mathematics. Supervisory Committee MemberJulia Gordon, Mathematics. University ExaminerBruce Shepherd, Computer Science. University ExaminerAdditional Supervisory Committee Members:Jo´zsef Solymosi, Mathematics. Supervisory Committee MemberiiAbstractIn this thesis, we make progress on the problem of enumerating tableaux on non-classicalshapes by introducing a general family of P-partitions that we call periodic P-partitions.Such a family of P-partitions generalizes the parallelogramic shapes, which were analysedby Lo´pez, Martı´nez, Pe´rez, Pe´rez, Basova, Sun, Tewari, and van Willigenburg, and certaintruncated shifted shapes, where truncated shifted shapes were investigated by Adin, King,Roichman, and Panova. By introducing a separation property for posets and by proving arelationship between this property and P-partitions, we prove that periodic P-partitions canbe enumerated with a homogeneous first-order matrix difference equation.Afterwards, we consider families of finite sets that we call shellable and that have beencharacterized by Chang and by Hirst and Hughes as being the families of sets that admitunique solutions to Hall’s marriage problem. By introducing constructions on families of setsthat satisfy Hall’s Marriage Condition, and by using a combinatorial analogue of a shellingorder, we prove that shellable families can be characterized by using a generalized notionof hook-lengths. Then, we introduce a natural generalization of standard skew tableauxand Edelman and Greene’s balanced tableaux, then prove an existence result about such ageneralization using our characterization of shellable families.iiiLay SummaryIn combinatorics, counting the number of items in a collection, or the number of objectsthat satisfy a certain property, can be very difficult and often represents the limits of what iscurrently known. Such problems pose interesting challenges to researchers. In this thesis,we count the number of ways in which certain objects that exhibit a fixed repeating patterncan be labelled with ordered sequences of numbers.In discrete maths, there are ways of grouping objects so that every group of objects can beassigned a suitable representative. Also, in discrete maths, there are labelled arrangementsof numbers where there are restrictions on where the numbers that fill the arrangement arepositioned. In this thesis, we prove some structural results that give a relationship betweenthe above grouping of objects and the above arrangement of numbers.ivPrefaceChapters 3 to 5 of my thesis originated as a project to generalize enumerative results forcertain tableaux from Tewari and van Willigenburg’s paper [49]. I was successful in accom-plishing the orignal goals relating to this project and generalized them to P-partitions in theabove chapters. I chose this project under the guidance of my supervisor, Stephanie vanWilligenburg. Moreover, I am responsible for all aspects of the above work and I plan tosubmit it for publication.Chapters 6 to 7 of my thesis originated from a suggestion made by my supervisor to furtherdevelop an earlier result that I derived for skew tableaux. I was successful in developing myoriginal result, leading to the above two chapters. Furthermore, I have generalized the resultsin Chapters 6 and 7 and submitted them for publication. I am responsible for all aspects ofthe above work.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1vi2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 The P-partition enumeration problem . . . . . . . . . . . . . . . . . . . . . . 164 Periodic (P,ω)-partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 The matrix difference equation . . . . . . . . . . . . . . . . . . . . . . . . . . 456 Results relating to the marriage condition . . . . . . . . . . . . . . . . . . . . 707 Applications to skew tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 808 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96viiList of FiguresFigure 4.1 A three-dimensional analogue of Example 4.8. Here, X = {(i, j,0) : 1≤i≤ 3 and 1≤ j ≤ 3} and ∆= (1,1,1). . . . . . . . . . . . . . . . . . 37Figure 4.2 A more exotic example of a periodic quadruple system. . . . . . . . . . 43viiiList of Symbolsa∗ term of a sequenced dimensionf ,g,h, f∗,g∗ functionsh∗ hook-lengthi, j,k, `,m, n∗,k∗, `∗ integersn index associated with periodic quadruplesystems, n→ ∞, [n], n!, λ ` np,q, p∗,q∗ elements of a posetr, r∗ element of a sets(·) successor function for Zu,v vectorsv(i) ith entry of column vector vw period of a periodic sequenceA,B,C components of a connected tripleixH∗ hookL labellings of Tb(S,ω)R inverse of LM square matrixM(i, j) entry in the ith row and the jth column of MN |S,ω|, number of rows of a square matrixN set of positive integersN0 set of non-negative integersP,Q,P∗,Q∗ posetsR>0 set of positive real numbersS,S′ subsets of ZT,T∗ elements of Tb(Q,ω)U,U∗ elements of A (Q,ω)X ,Y setsZ countably infinite and locally finite posetZ(X ,∆) certain subposet of ZdA (Q,ω) a set of Q-partitionsF ,F ′ set partitions, families of setsTb(Q,ω) A (Q,ω)/≡Q,ωα translation map on Zθ component of a periodic quadruple systemκ order embedding from [n−1] to [n]λ integer partitionσ , σ∗ permutationsxω , ω∗ poset labellings∆ translation vectorℜ binary relation|Q,ω| cardinality of Tb(Q,ω)[·, ·], [·,∞) intervals within the set of integers∼ is asymptotic to≤, ≤∗ partial orders≡, ≡∗ equivalence relations‖ incomparability relation/0 empty set, empty partitionxiAcknowledgmentsI would like to thank my parents for their enduring and enthusiatic support throughout myjourney.I am also appreciative of Jo´zsef Solymosi and Andrew Rechnitzer for their encouragementand guidance.Moreover, I would like to acknowledge that my research was supported in part by NSERCand UBC fellowships.Lastly, I would like to thank Stephanie van Willigenburg for her mentorship and encourage-ment. Our frequent meetings, her invaluable guidance in my mathematical development, andher unwavering support through the years have all had a very positive impact on me. I amgrateful for her dedication to my academic success.xiiChapter 1IntroductionP-partitions were first considered by MacMahon in [31]. Later on, the theory of P-partitionswas developed by Gessel and Stanley [18, 46]. This theory is known to have applicationsto, for instance, quasisymmetric functions as P-partitions are essential for the theory of qua-sisymmetric functions [18].In this thesis, we investigate the problem of enumerating tableaux on non-classical shapesby introducing a general class of P-partitions that we call periodic P-partitions. We firstintroduce the notion of a connected triple for a poset and prove that periodic P-partitionsgeneralize many known tableau on non-classical shapes considered in the literature. After-wards, we consider the problem of counting the number of periodic P-partitions by definingcollections of numbers that sum to this number. We prove a structural property of connectedtriples to prove that the aforementioned collections of numbers, represented as column vec-tors, can be enumerated with a homogeneous first-order matrix difference equation in whichthe entries of the matrix have natural combinatorial descriptions.1Our approach towards P-partitions does not provide closed-form formulas or product for-mulas for enumeration. On the other hand, our approach with P-partitions is not limited tothe bijective fillings of non-classical shapes that are usually analysed in the literature [1–3, 27, 38, 47, 49]. In Chapter 8, we briefly outline how our results imply that the P-partitionswe are interested in satisfy constant coefficient linear recurrences, generalizing tableau enu-meration results for non-classical shapes from Lo´pez, Martı´nez, Pe´rez, Pe´rez, and Basova[27], from Sun [47], and from Tewari and van Willigenburg [49] that we will describe laterin this section. We now give an overview of the research that our results on P-partitions canbe applied to.Counting the number of P-partitions is a generalization of the problem of counting the num-ber of linear extensions of a poset. Counting the number of linear extensions of a poset is ingeneral an interesting problem. It has been considered ([44], p. 258) to be very importantfor measuring the complexity of a poset. A well-known special case of this is the problemof enumerating standard Young tableaux of various shapes [2]. Among the standard Youngtableaux on non-classical shapes that the results of this thesis applies to are d-dimensionaltableaux of certain shapes for any d ≥ 3, and standard Young tableaux on many of the trun-cated shifted shapes.A class of standard Young tableaux that is of recent interest are standard Young tableauxof truncated shifted shapes. Certain truncated shifted shapes, known as truncated shiftedstaircase shapes, are known to enumerate the number of geodescics between distinguishedpairs of antipodes in the flip graph of triangle-free triangulations [3]. Special cases of enu-merating standard Young tableaux on truncated shifted shapes have been established. Adin,King, and Roichman [1] enumerated such tableaux for shifted staircase shapes truncated bya square, or a square minus a single cell in the south-west corner, and Panova [38] indepen-2dently proved, using different methods, the special case of this problem for shifted staircaseshapes truncated by a single cell.Hardin and Heinz conjectured ([43], A181196) constant coefficient recurrence relations forcounting the number of standard Young tableaux on shifted strips with constant width upto when the width is seven. Standard Young tableaux on shifted strips with constant widthare known to correspond to quasisymmetric functions known as the canonical basis, whichis a newly discovered basis of quasisymmetric functions, via descent sets of standard re-verse composition tableaux and fundamental quasisymmetric functions [49]. These tableauxwere also shown to be connected to the representation theory of the 0-Hecke algebra [49].Moreover, standard Young tableaux on shifted strips with constant width are also known tobe connected to Higman’s conjecture, which is concerned with enumerating the number ofconjugacy classes in the group of upper unitriangular n by n matrices over Fq [27].Later research established that Hardin and Heinz’s conjectures are correct. Tewari andvan Willigenburg [49] proved Hardin and Heinz’s conjecture when the constant width is3, Sun [47] proved Hardin and Heinz’s conjecture when the constant width was 4 and 5, andLo´pez, Martı´nez, Pe´rez, Pe´rez, and Basova proved all of Hardin and Heinz’s recurrences andestablished a generalization of these recurrences when the width k ∈ N is arbitrary [27].Lastly, another class of P-partitions are semistandard tableaux. Semistandard tableaux arefundamental to constructing Schur functions [45] and they are deeply connected to the Spechtmodules of the symmetric group [41]. A very well-known class of numbers are the Kostkanumbers, which are the numbers of semistandard tableaux on partition shapes [41]. However,very little is known about this number [45].The work of this thesis implies that semistandard tableaux on certain shapes, such as the3parallelogramic shapes considered by Lo´pez et.al., Sun, and Tewari and van Willigenburg,can also be enumerated with a matrix difference equation as described at the beginning ofthis section.Hall’s Marriage Theorem is a combinatorial theorem that characterises when a finite familyof sets has a system of distinct representatives, which is also called a transversal. Hall [21]proved that such a family has a system of distinct representatives if and only if this familysatisfies the marriage condition. This theorem is known to be equivalent to at least six othertheorems [40] which include Dilworth’s Theorem, Menger’s Theorem, and the Max-FlowMin-Cut Theorem.Hall Jr. proved [22] that Hall’s Marriage Theorem also holds for arbitrary families of finitesets. Afterwards, Chang [10] noted how Hall Jr.’s work in [22] can be used to characterizemarriage problems with unique solutions. Specifically, the families of sets that admit mar-riage problems with unique solutions were characterized [10]. Later on, Hirst and Hughesproved that such a characterization of marriage problems with unique solutions can be de-rived by only using a subsystem of second order arithmetic known as RCA0 [24], and theyshowed that their work in [24] can also be extended to marriage problems with a fixed finitenumber of solutions [23]. In this thesis, we call the families of finite sets that admit marriageproblems with unique solutions shellable and give a new characterization of these familiesof sets by generalizing the notion of standard Young tableaux and Edelman and Greene’sbalanced tableaux.Standard skew tableaux are well-known and intensively studied in algebraic combinatorics,for example [25, 35, 36, 45]. Moreover, another class of tableaux was introduced by Edelmanand Greene in [13, 14], where they defined balanced tableaux on partition shapes. In investi-gating the number of maximal chains in the weak Bruhat order of the symmetric group, Edel-4man and Greene proved [13, 14] that the number of balanced tableaux of a given partitionshape equals the number of standard Young tableaux of that shape. Since then, connectionsto random sorting networks [5], the Lascoux-Schu¨tzenberger tree [28], and a generalizationof balanced tableaux pertaining to Schubert polynomials [15] have been explored.Lastly, properties of products of hook-lengths have recently enjoyed some attention by Paket.al. [34, 39] and by Swanson [48]. In particular, an inequality between products of hook-lengths and products of dual hook-lengths was derived [34, 39, 48]. We introduce a gen-eralization of standard Young tableaux and balanced tableaux for skew shapes, show, usingour characterization of marriage problems with unique solutions, that the number of suchgeneralizations that can exist is given by a product of hook-lengths, and show, as a conse-quence, that the average number of tableaux that belongs to such a generalization is givenby the hook-length formula. We then discuss extensions and possible applications of ourcharacterization in Chapter 8.This thesis is structured as follows. In Chapter 2, we give an overview of the preliminariesand describe the conventions that we will follow. In Chapter 3, we describe in detail theP-partition enumeration problem we are considering. In Chapter 4, we introduce the no-tion of a connected triple, formally define periodic P-partitions, give illuminating examples,and prove that this definition includes many tableaux on certain d-dimensional non-classicalshapes for all d ≥ 3. In Chapter 5, we consider collections of P-partitions, then prove a struc-tural property of connected triples to prove that these collections satisfy a matrix differenceequation.In Chapter 6, we introduce a stronger form of the marriage condition and characterize it usinggeneralized hook-lengths. Moreover, in Chapter 7, we explain how to apply our results toa generalization of standard Young tableaux and balanced tableaux for skew tableaux and5breifly indicate ways in which we can extend our approach. Lastly, in Chapter 8, we give anoutline of future directions for this research.6Chapter 2PreliminariesIn this chapter, we give the preliminaries that will be needed for this thesis. Throughoutthis thesis, let N denote the set of positive integers and let N0 denote the set of non-negativeintegers.For all positive integers n, define [n] = {1,2, . . . ,n}. Moreover, for all positive integers n1and n2 such that n1 ≤ n2, define [n1,n2] = {k ∈ N : n1 ≤ k ≤ n2}. In particular, [n,n] = {n},[n,n+ 1] = {n,n+ 1}, [n,n+ 2] = {n,n+ 1,n+ 2}, and so on. Furthermore, for all n ∈ Z,define [n,∞) = {k ∈ Z : k ≥ n}.Let X and Y be sets. Define X \Y = {r ∈ X : r /∈ Y}. If X is a subset of Y , then write X ⊆ Y .Moreover, if X is a proper subset of Y , then write X ⊂ Y . Lastly, if X is not a subset ofY , then write X * Y . If n ∈ N and if X1, X2, . . . , Xn are sets, then the Cartesian productX1×X2×·· ·×Xn of X1, X2, . . . , and Xn is the set of ordered n-tuples {(r1,r2, . . . ,rn) : ∀i ∈[n],ri ∈ Xi}. If X1 = X2 = · · · = Xn and X = X1, then write Xn = X1×X2×·· ·×Xn. We letZd denote Xn if X = Z and d = n. Moreover, let /0 denote the empty set. Furthermore, if X7is a set, then let |X | denote the cardinality of X .We denote any sequence a1, a2, . . . by (an)n=1,2,.... Lastly, let w∈N. A sequence (an)n=1,2,...is periodic with period w if an = an+w for all n ∈ N.A binary relation on a set X is a subset ℜ of X ×X . We write r1 ℜ r2 if (r1,r2) ∈ ℜ. Abinary relation ℜ on X is reflexive if r ℜ r for all r ∈ X , symmetric if, for all r1,r2 ∈ X ,r1 ℜ r2 implies that r2 ℜ r1, antisymmetric if, for all r1,r2 ∈ X , r1 ℜ r2 and r2 ℜ r1 impliesthat r1 = r2, and transitive if, for all r1,r2,r3 ∈ X , r1 ℜ r2 and r2 ℜ r3 implies that r1 ℜ r3.An equivalence relation ≡ on X is a binary relation on X that is reflexive, symmetric andtransitive. Moreover, a partial order ≤ on X is a binary relation on X that is reflexive,antisymmetric, and transitive.Let X be a set, and let≡ be an equivalence relation on X . Then for all r ∈ X , the equivalenceclass of r in X with respect to ≡ is the set {r1 ∈ X : r ≡ r1}. An equivalence class in X withrespect to ≡ is an equivalence class of r in X with respect to ≡ for some r ∈ X . Lastly, letX/≡ denote the set of all equivalence classes in X with respect to ≡.Example 2.1. Let X = {1,2,3}, and let≡ be the set {(1,1),(2,2),(3,3),(1,2),(2,1)}. Then1 ≡ 1, 2 ≡ 2, 3 ≡ 3, 1 ≡ 2, and 2 ≡ 1. Moreover, the equivalence classes of X with respectto ≡ are {1,2} and {3}. Hence, X/≡ equals {{1,2},{3}}.In order to clarify the conventions that we will follow when describing posets, we brieflyintroduce posets and related notions below. More details can be found in [12, 42, 44]. A setP equipped with a partial order ≤ on P is called a poset.When describing posets, we will usually say “let P be a poset”, “if P is a poset”, etc. withoutexplicitly mentioning the partial order ≤ on P. Moreover, an element p of a poset P with8partial order≤ is an element of the set P and we write p ∈ P. Similarly, a subset X of a posetP with partial order ≤ is a subset of the set P and we write X ⊆ P. In particular, P⊆ P. Wewill also write p ≥ q if q ≤ p, p < q if p ≤ q and p 6= q, p > q if q < p, p  q if p ≤ q isfalse, p q if q p, p≮ q if p< q is false, and p≯ q if q≮ p. Moreover, if P is a poset withpartial order ≤ and if p,q ∈ P, then we write p ‖ q, and say that p and q are incomparable,if p  q and q  p. A partial order ≤ on a poset P is a total order on P if, for all p,q ∈ P,p≤ q or q≤ p.We will indicate which poset we are referring to if we want to clarify which partial order weare using. For instance, we will say “x ≤ y in P” to mean that x ≤ y, where x,y ∈ P and ≤is the partial order on P, “x > y > z in P” to mean that z ≤ y, y ≤ x, x 6= y, and y 6= z wherex,y,z ∈ P and ≤ is the partial order on P, and “x ‖ y in P” to mean that x ≤ y is false andy≤ x is false, where x,y ∈ P and ≤ is the partial order on P.We will assume the following when describing subsets of posets. In this paragraph, we willuse subscripts to indicate which partial order we are referring to. Let P be a poset with partialorder ≤P. Then a subposet of P is a subset Q of P equipped with the partial order ≤Q onQ defined, for all p,q ∈ Q, by p ≤Q q if p ≤P q. In particular, all subposets are posets. Forconvenience, we will regard a subset of a poset P as the subposet of P that corresponds tothat subset, and we will regard a subposet of a poset P as the subset of P that corresponds tothat subposet. For instance, if P is a poset and if Q is a subset of P, then when we say thingssuch as “Q is order isomorphic to a five element poset”, we are assuming that Q is a subposetof P in the above sense. Moreover, we will, when defining subposets Q of posets P, say “letQ be a subset of a poset P”, “let P be a poset and let Q⊆ P”, and so on.Definition 2.2 (Folklore, cf. [2]). We will regard Z as a poset with total order defined by· · ·<−1< 0< 1< · · · . Moreover, for any d ∈ N, we will regard Zd as a poset with partial9order defined by (k1,k2, . . . ,kd)≤ (`1, `2, . . . , `d) if ki ≤ `i for all 1≤ i≤ d.If d ∈ N and if X ⊆ Zd , then, as explained in the paragraph above Definition 2.2, X is asubposet of Zd . Furthermore, if u,v ∈ Zd , u = (k1,k2, . . . ,kd), and v = (`1, `2, . . . , `d), thenwrite u+ v = (k1+ `1,k2+ `2, . . . ,kd + `d), write ku = (k k1,k k2, . . . ,k kd) for all k ∈ Z, andwrite v−u= v+ku if k =−1. Lastly, for any X ⊆ Zd and u ∈ Zd , write X +u= {v+u : v ∈X} and write X−u = {v−u : v ∈ X}.If P is a poset, then an element p ∈ P is a minimal element of P if for all q ∈ P, q ≥ p inP or q ‖ p in P. Moreover, a subset X ⊆ P is an antichain of P if, for all p,q ∈ X , p ‖ q inP. A poset P is finite if P has a finite number of elements; that is, if |P| is finite. Similarly,a poset P is countable if |P| is countable, and countably infinite if |P| is countably infinite.Moreover, a poset P is locally finite if for all p,q∈ P such that p≤ q, the number of elementsp1 ∈ P such that p≤ p1 ≤ q in P is finite.We use the terms function and map interchangeably. Moreover, we define functions on posetsas follows. Assume that R1 and R2 are such that R1 and R2 are posets, R1 is a poset and R2 isa set, or R1 is a set and R2 is a poset. Then a function f : R1→ R2 from R1 to R2 is a functionf0 from the set of elements of R1 to the set of elements of R2 and we write f (r) = f0(r) forall r ∈ R1. Let f and f0 be as in the previous sentence. Then f is injective if f0 is injective,f is surjective if f0 is surjective, and f is bijective if f0 is bijective. We also call a functionf : R1→ R2 a map from R1 to R2.If R1 and R2 are such that R1 and R2 are sets, R1 and R2 are posets, R1 is a poset and R2 is aset, or R1 is a set and R2 is a poset, then define the following. Let f : R1→ R2 be a function.Then for all X ⊆ R1, let f (X) = { f (r) : r ∈ X}, and, for all Y ⊆ R2, let f−1(Y ) = {r ∈ R1 :f (r) ∈ Y}. If f is injective, then write f−1(r) = f−1({r}) for all r ∈ f (R1). For all X ⊆ R1,10let the restriction of f to X , which we denote by f |X , be the function g : X → R2 definedby g(r) = f (r) for all r ∈ X . Moreover, assume that R3 is a set or a poset. If f : R1→ R2and g : R2 → R3 are functions, then let g ◦ f denote the function h : R1 → R3 defined byh(r) = g( f (r)) for all r ∈ R1. Moreover, if f : R1→ R1 is a function, then write f 1 = f and,for all n ∈ N, write f n+1 = f ◦ f n. Furthermore, if f : R1→ R1 is a bijection, then let f 0 bethe identity map on X and, for all n ∈ Z, let f n+1 = f ◦ f n.Let P and Q be posets and let f : P→ Q be a function. Then f is order preserving if for allp,q∈ P, p≤ q implies that f (p)≤ f (q), order reversing if for all p,q∈ P, p≤ q implies thatf (p) ≥ f (q), an order embedding if f is injective and if, for all p,q ∈ P, p ≤ q if and onlyif f (p)≤ f (q), and an order isomorphism if f is a surjective order embedding. Moreover, ifP is a poset and if f : P→ P is a function, then f is an order automorphism if f is an orderisomorphism.We will define Young diagrams in the following way (cf. [2], also cf. [30, 41, 44, 45].)A Young diagram is the empty set or a finite subset X of N2 such that for some i, j ∈ N,(1, j) ∈ X and (i,1) ∈ X . We call the elements of a Young diagram X the cells of X . Lastly,given a Young diagram X , define, for all i ∈ N, row i of X to be the following subset of cells{r ∈ X : ∃ j ∈ N such that r = (i, j)}and, for all j ∈ N, define column j of X to be the following subset of cells{r ∈ X : ∃i ∈ N such that r = (i, j)}.Sometimes, when we mention a cell r = (i, j) in a Young diagram, we write (i, j) instead ofr.11In order for us to follow the conventions used in the literature [2, 30, 41, 44, 45], we willalways depict Young diagrams by using an array of boxes where each such box has unitarea and where each such box contains an element of N2 at its centre. Moreover, we alsofollow conventions in the literature by doing the following. We will, when depicting a Youngdiagram X , always draw row i+1 of X beneath row i and we will always draw column j+1to the right of column j.Example 2.3. If X1 = {(1,1),(1,2),(1,3)}, X2 = {(1,1),(1,3),(1,6),(1,7)}, and X3 ={(1,1),(1,3),(2,2),(3,1),(3,3)}, then the Young diagram X1 is depicted by,the Young diagram X2 is depicted by,and the Young diagram X3 is depicted by.Moreover, row 1 of X1 is X1, column j of X1, where 1≤ j ≤ 3, is {(1, j)}, row 1 of X2 is X2,column j of X2, where j ∈ {1,3,6,7}, is {(1, j)}, row 1 of X3 is {(1,1),(1,3)}, row 2 of X3is {(2,2)}, row 3 of X3 is {(3,1),(3,3)}, column 1 of X3 is {(1,1),(3,1)}, column 2 of X3 is{(2,2)}, and column 3 of X3 is {(1,3),(3,3)}.Let P be a poset, and let p,q ∈ P. Then q covers p, or p is covered by q, if p< q in P and noelement p′ ∈ P satisfies p< p′ < q in P. If P is a finite poset, then a Hasse diagram of P is a12visual representation of P such that the elements of P are denoted by small non-intersectingcircles and, for all p,q∈P such that q covers p, q is drawn above p and a line segment, or arc,is drawn between p to q. We call the non-intersecting circles nodes. Sometimes, when wewant to emphasize certain elements in a finite poset, we will replace the nodes correspondingto those elements with the elements themselves.Example 2.4. Let P be the finite poset with elements p1, p2, p3, p4 and partial order on Pdefined by p1 < p2, p2 > p3, and p3 < p4. Then a Hasse diagram of P is depicted below.◦◦◦◦If we want to emphasize the elements of P, then we writep1p2p3p4.We will depict posets using Hasse diagrams. Moreover, if X is a Young diagram, then, asX ⊂ Z2, we will interpret X as a poset with partial order as described earlier in this chapter.So if P is a finite poset that is order isomorphic to a poset Q such that Q is a Young diagram,then we will sometimes depict P with the Young diagram Q. The orientation of the elementsdepicted in a Young diagram is different from the orientation of elements depicted in a Hassediagram. In a Hasse diagram, p < q implies that q is positioned above p, but in a Youngdiagram, p< q implies that q cannot be positioned to the left of p and q cannot be positionedabove p. We illustrate this with an example.Example 2.5. If P is the poset depicted by the following Hasse diagram13◦◦◦◦ ◦◦◦ ,then any of the Young diagrams shown below can also be used to depict P.If M is a matrix, then let M(i, j) denote the entry in the ith row and jth column of M. Acolumn vector is a matrix with one column, and a row rector is a matrix with one row. An n1by n2 matrix is a matrix with n1 rows and n2 columns. If v is a column vector with N rows,then for all 1≤ i≤ N, let v(i) denote the entry in the ith row of v.Consider the finite set [n]. A set partition of [n] is a set F of non-empty subsets of [n] suchthat every element of [n] is contained in exactly one element of F . A family F of sets is asurjective function h : I→ X where I and X are sets and where every element of X is a set.A subfamily F ′ of a family F of sets is the restricion of a family h : I→ X to some subsetI′ of I.LetF be a family h : I→ X of sets. Then we define a member F ofF to be an ordered pair(i,h(i)) where i∈ I. When we use subscripts to describe the members F of a family h : I→ Xof sets, the subscripts do not necessarily have to be elements of I. If we want to indicate thatF is a member of F , then we write F ∈F . We write F1,F2, · · · ∈F if Fk ∈F for all k.14Moreover, two members F1 = (i1,h(i1)) and F2 = (i2,h(i2)) of F are different if i1 6= i2. IfF = (i,h(i)) is a member of F , then we write r ∈ F if r ∈ h(i). We write r1,r2, · · · ∈ F ifrk ∈ F for all k. For any set Y , define a function f :F → Y from F to Y to be a functiong : I→ Y , and for all members F ∈F , write f (F) = g(i) if i ∈ I satisfies F = (i,h(i)). Wealso call f :F →Y a map fromF to Y . Such a function f :F →Y is injective if F1,F2 ∈Fand f (F1) = f (F2) implies that F1 and F2 are not different.Let F be a family h : I → X of sets. When describing the members F = (i,h(i)) of suchfamilies, we will write h(i) instead of the ordered pair (i,h(i)). We will also use set-theoreticnotation to describe families of sets by writing F = {F : F ∈ F}. For instance, if F isthe family of sets defined by h : {1,2} → {{1}}, then we write F = {{1},{1}}, where themembers (1,{1}) and (2,{1}) ofF are both denoted by {1}. Moreover, we write |F |= |I|,and say that |F | is the number of members ofF . A familyF of sets is finite if |F | is finite.Lastly, ifF is a family h : I→ X of sets, then write ⋃F∈F F =⋃r∈I h(r).For all n ∈ N, a partition λ of n, written λ ` n, is a weakly decreasing sequence of positiveintegers whose sum is n. We write λ = (λ1,λ2, . . . ,λ`) to denote such a partition, whereλi ∈ N for all 1 ≤ i ≤ ` and λ1 +λ2 + · · ·+λ` = n. For instance, (3,2,2) is a partition of 7and (3,2,1) is a partition of 6. We also let /0 denote the empty partition, which we defineto be the only partition of 0. Whether the symbol /0 refers to the empty set or to the emptypartition can be easily determined from context.15Chapter 3The P-partition enumeration problemIn this chapter, we define some essential terminology and describe the notation that we willuse. Afterwards, we describe the P-partition enumeration problem that we will be focusingon in this thesis.If X is a finite set, then a labelling of X is a bijection f : X → [k] where k = |X |. Next,we introduce terminology for (P,ω)-partitions from [44], but extend labellings to countablyinfinite posets and define A (Q,ω) in a non-standard way. If P is a finite poset, then alabelling of P is a bijection ω : P→ [k] where k = |P|. Moreover, if P is a countably infiniteposet, then a labelling of P is a bijection ω : P→Z. Recall from Chapter 2 that a map f : P→Q, where P and Q are posets, is order-reversing if p1 ≤ p2 in P implies f (p2)≤ f (p1) in Q.If P is a countable poset, then a labelling ω of P is natural if ω is an order preserving mapand dual natural if ω is an order reversing map. If P is a finite poset and if ω is a labellingof P, then a (P,ω)-partition is an order-reversing map f : P→ N0 such that f (x) > f (y) ifx < y and ω(x)> ω(y). We sometimes call a (P,ω)-partition a P-partition. Lastly, if P is a16countable poset, if Q is a finite poset such that Q ⊆ P, and if ω is a labelling of P, then letA (Q,ω) denote the set of order-reversing maps U : Q→ N0 such that U(x)>U(y) if x< yand ω(x)>ω(y). If Q1 ⊆Q, then we let U |Q1 denote the restriction of the function U to Q1.If P is a poset, then we will depict a labelling or an order-reversing map on P with a Hassediagram (or a Young diagram) whose nodes (or cells) are filled with integers. Specifically, ifP is a poset, if p ∈ P, if X ⊆ Z, and if f : P→ X satisfies f (p) = k, then, when depicting fwith a diagram, replace the node (or fill in the cell) corresponding to p with k.Example 3.1. If (P,≤) is the poset depicted by the left-most diagram shown below, whereP = {p1, p2, p3, p4}, and if f : P→ Z is a function such that f (p1) = 4, f (p2) = 2, f (p3) =−1, and f (p4) = 3, then we will depict f with the right-most diagram shown below.p4p1 p2 p334 2 −1Example 3.2. If (P,≤) is the poset depicted by the left-most diagram shown below, whereP = {p1, p2, p3}, and if f : P→ {1,2,3} is a function such that f (p1) = 3, f (p2) = 2, andf (p3) = 2, then we will depict f with the right-most diagram shown below.p1p2 p332 2If P is a finite poset and if ω is a labelling of P, then we would like to say that two elementsU1,U2 ∈A (P,ω) are the same if the relative orderings of their entries are the same. Hence,we define the following equivalence relation on order preserving maps.Definition 3.3. Let P be a poset, let S1 and S2 be subsets of Z, and let f1 : P→ S1 andf2 : P→ S2 be maps. Then f1 is order equivalent to f2 if there exists an order isomorphism17g : f1(P)→ f2(P) such that f2 = g◦ f1. Lastly, we write f1 ≡ f2 if f1 is order equivalent tof2.Example 3.4. Let f1 : P→ Z and f2 : P→ Z be depicted by5 2 26 7and 8 −1−19 15respectively. Then f1(P) = {2,5,6,7}, f2(P) = {−1,8,9,15}, and g : f1(P) → f2(P) isdefined by g(2) = −1, g(5) = 8, g(6) = 9, and g(7) = 15. Since f2 = g ◦ f1, and since g isan order isomorphism, f1 is order equivalent to f2.Remark 3.5. The definition ofA (Q,ω) we are using is essentially the same as the standarddefinition of A (Q,ω) given in [44]. Let P and Q be posets such that Q ⊆ P, and let ωbe a labelling of P. Moreover, let ωQ be the labelling of Q such that ωQ ≡ ω|Q. Then,A (Q,ω) =A (Q,ωQ).We now formally define the (P,ω)-partitions that we will count in this thesis.Definition 3.6. Let P and Q be posets such that Q is finite and Q⊆ P. Moreover, let ω be alabelling of P and let≡Q,ω denote the equivalence relation onA (Q,ω) defined by f ≡Q,ω gif f is order equivalent to g. Then defineTb(Q,ω) =A (Q,ω)/≡Q,ωand define|Q,ω|= |Tb(Q,ω)|.Moreover, if Q1 ⊆Q and if T ∈ Tb(Q,ω), then let T |Q1 be the element T ′ of Tb(Q1,ω) suchthat, for all U ∈A (Q,ω) satisfying U ∈ T , U |Q1 ∈ T ′.18Example 3.7. Let P be depicted by the left-most six cell diagram shown below, let Q ⊆ Pconsist of the cells of the left-most diagram that are filled with bullets, and let ω : P→{1,2,3,4,5,6} be depicted by the right-most diagram shown below.• • •• •2 1 36 4 5For all 1 ≤ k ≤ 6, let pk = ω−1(k). Then A (P,ω) consists of the order-preserving mapsf : P→N0 such that f (p2)> f (p1), f (p1)≥ f (p3), f (p1)≥ f (p6), f (p3)≥ f (p4), f (p6)>f (p4), and f (p4)≥ f (p5). Three of the elements in A (Q,ω) are depicted as follows.3 2 22 15 4 32 110 9 99 7The element of A (Q,ω) depicted by the left-most diagram shown above is order equivalentto the element of A (Q,ω) depicted by the right-most diagram shown above. However, theelement of A (Q,ω) depicted by the middle diagram shown above is not order equivalent toeither of the other two elements just mentioned.An example of an element of Tb(Q,ω) is the following subset of A (Q,ω).3 2 22 1, 8 5 55 4, 10 1 11 0, . . .Remark 3.8. If T ∈ Tb(Q,ω), then we will depict T with one of the elements of T . Forexample, if T is the element of Tb(Q,ω) whose elements are depicted below3 2 22 1, 8 5 55 4, 10 1 11 0, . . .then we will simply depict T with any one of the above diagrams. For instance, we may say19that T is depicted by8 5 55 4.20Chapter 4Periodic (P,ω)-partitionsIn this chapter, we define periodic P-partitions and investigate classes of periodic P-partitionsthat exist as follows. We first explain why periodic P-partitions include parallelogramicshapes and certain truncated shifted shapes. Then, we prove that periodic P-partitions alsoinclude certain d-dimensional, for d ≥ 3, analogues of parallelogramic shapes. Lastly, weconstruct an example that differs very much from a parallelogramic shape or a truncatedshifted shape.In this thesis, we will count the quantity |P,ω| by defining a notion of separation for the posetP.Definition 4.1. Let P be a poset. Then a connected triple (A,B,C) of P is an ordered triple(A,B,C) that satisfies the following two properties.1. A, B, and C are non-empty subsets of P, A∪B∪C = P, and A∩B= B∩C = A∩C = /0.2. For all p1 ∈ A and for all p2 ∈C, there exists an element p ∈ B such that p1 < p< p221in P.Moreover, if B is a non-empty subset of P, then B connects P if there exist non-empty subsetsA and C of P such that (A,B,C) is a connected triple of P.Example 4.2. A parallelogramic shape [27] is a Young diagram X such that for some n,k ∈N,X =n⋃i=1k⋃j=1{(i, j+ i−1)}.For instance, if n = 3 and k = 5, then the corresponding parallelogramic shape X is thefollowing.Such shapes are also called shifted strips where the parameter k is called the width of such astrip [47], and they were investigated in [27], [47], and [49]. In this thesis, we will interpretsuch shapes as posets in the way specified in Chapter 2.We make the following observation which can be generalized to any parallelogramic shape.If P is the poset corresponding to the parallelogramic shape with k = 4 and n = 4 depictedbelow, then if A is the subset of P that is depicted by the blank cells, if B is the the subset ofP that is depicted by the cells filled with bullets, and if C is the subset of P that is depictedby the cells filled with asterisks, then (A,B,C) is a connected triple of P.•• • •∗ ∗ ∗ ∗We extend the usual definition of the successor function from the natural numbers to the22integers. Namely, let s : Z→ Z be the successor function defined bys(n) = n+1for all n ∈ Z. With this function, we define periodic quadruple systems.Definition 4.3. Let Z be a countably infinite poset, and let ω be a labelling of Z. Moreover,let pi : Z→ Z be a surjective order preserving map, and let θ : Z→ Z be an order automor-phism on Z. Then the ordered quadruple (Z,ω,pi,θ) is a periodic quadruple system if thefollowing three properties hold.1. There exists an order automorphism α : Z→ Z such that the following diagram com-mutes.ZZZZZZωpiωpiαθs2. For all n ∈ Z, pi−1({n}) is finite.3. There exists a finite subset S of Z such that S connects Z.Remark 4.4. A map α : Z→ Z is an order automorphism on Z if and only if there exists aninteger w∈Z such that α(n)= n+w for all n∈Z. So in the rest of the thesis, we will describethe order automorphism α : Z→ Z as a map on Z defined by α(n) = n+w. Moreover, inthis thesis, we will use the notational conventions for functions that we described in Chapter2 for the functions ω , pi , and θ in Definition 4.3 and for similarly defined functions.23Remark 4.5. In Definition 4.3, pi−1({n}) can be informally thought of as the subposet ofZ that is the nth copy of the subposet pi−1({0}) of Z because pi−1({n}) = θ n(pi−1({0})) byProperty 1 of Definition 4.3, and because θ is an order automorphism on Z. By Property 2of Definition 4.3, pi−1({0}) is a finite poset and Z is locally finite. Moreover, by Property1 of Definition 4.3, Z is the pairwise disjoint union of the copies of the subposet pi−1({0})in Z. Hence, we will depict Z with a Hasse diagram of pi−1([n1,n2]), where n1,n2 ∈ Z andn2−n1 is sufficiently large, and visually indicate how this Hasse diagram is contained in Z.Example 4.6. Let Z be the poset depicted by the left-most diagram shown below, and letω be the labelling depicted by the right-most diagram shown below. The labelling ω is adual natural labelling of Z. Define pi : Z→ Z so that ω−1({−10,−8,−5,−3}) = pi−1({1}),ω−1({−6,−4,−1,1}) = pi−1({0}), ω−1({−2,0,3,5}) = pi−1({−1}), ω−1({2,4, 7,9}) =pi−1({−2}), and so on. Furthermore, let θ : Z → Z be the order automorphism on Z suchthat for all n ∈ Z, θ(ω−1(n)) = ω−1(n−4).◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦......−3−5−8−101−1−4−6530−29742......To see that (Z,ω,pi,θ) satisfies Property 1 of Definition 4.3, let α : Z → Z be definedby α(n) = n− 4 for all n ∈ Z. Then for all p ∈ Z, s(pi(p)) = pi(θ(p)) and α(ω(p)) =24ω(θ(p)). For instance, if p = ω−1(3), then s(pi(p)) = s(−1) = 0, pi(θ(p)) = 0, α(ω(p)) =α(3) =−1, and ω(θ(p)) =−1, implying that s(pi(p)) = 0= pi(θ(p)) and α(ω(p)) =−1=ω(θ(p)). Moreover, by how pi is defined in this example, |pi−1(n)| = 4 for all n ∈ Z. So(Z,ω,pi,θ) satisfies Property 2 of Definition 4.3. To see that (Z,ω,pi,θ) satisfies Property3 of Definition 4.3, let S ⊂ Z be defined by S = ω−1({−6,−4,−2,−1}). The set S is finite,and S connects Z. Hence, (Z,ω,pi,θ) is a periodic quadruple system.Remark 4.7. In Example 4.6, removing ω−1(−2) from the index shape S = ω−1({−6,−4,−2,−1}) results in a subsetS′ = ω−1({−6,−4,−1})of Z that does not connect Z. To see this, suppose that (A,S′,C) is a connected triple of Z forsome subsets A⊂ Z and C ⊂ Z. We first make the following observation.For all p ∈ S′, pi(p) = 0. Moreover, pi is order preserving. Hence, Definition 4.1 implies that{p ∈ Z : pi(p)< 0} ⊆ A and {p ∈ Z : pi(p)> 0} ⊆Cfor the following reason. Suppose without loss of generality that for some p ∈ Z satisfyingpi(p)> 0, p ∈ A. By Property 1 of Definition 4.1, C is non-empty. So there exists an elementq ∈C. By Property 2 of Definition 4.1, there exists an element p′ ∈ S′ such that p < p′ < qin Z. But then, as pi is order preserving,0< pi(p)< pi(p′) = 0which is impossible.With this observation, we continue as follows. Let p0 = ω−1(−2) and let q0 = ω−1(−3).25Since pi(p0) =−1 and pi(q0) = 1, the above observation implies that p0 ∈ A and q0 ∈C. Butthen, by Property 2 of Definition 4.1, there exists an element p′ ∈ S′ such that p0 < p′ < q0in Z. But that is impossible because p0 ‖ q0 in Z. Hence, S′ does not connect Z.Example 4.8. Let Z be the poset depicted by the left-most diagram shown below, and let ω bethe labelling depicted by the right-most diagram shown below. The labelling ω is an infiniteanalogue of certain labellings on skew shapes that are known as Schur labellings [45]. De-fine pi : Z→ Z so that ω−1({−5,0,5,10}) = pi−1({1}), ω−1({−9,−4,1,6}) = pi−1({0}),ω−1({−13,−8,−3,2}) = pi−1({−1}), ω−1({−17,−12,−7,−2}) = pi−1({−2}), and soon. Furthermore, let θ : Z → Z be the order automorphism on Z defined by θ(ω−1(n)) =ω−1(n+4).◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦......−50510−9−416−13−8−32−17−12−7−2......To see that (Z,ω,pi,θ) satisfies Property 1 of Definition 4.3, let α : Z→ Z be defined byα(n) = n+4 for all n ∈Z. Then for all p ∈ Z, s(pi(p)) = pi(θ(p)) and α(ω(p)) =ω(θ(p)).For instance, if p=ω−1(−8), then s(pi(p))= s(−1)= 0, pi(θ(p))= 0, α(ω(p))=α(−8)=−4, and ω(θ(p)) =−4. So s(pi(p)) = 0 = pi(θ(p)) and α(ω(p)) =−4 = ω(θ(p)). More-over, by how pi is defined in this example, |pi−1(n)|= 4 for all n ∈ Z. So (Z,ω,pi,θ) satisfies26Property 2 of Definition 4.3. To see that (Z,ω,pi,θ) satisfies Property 3 of Definition 4.3,let S⊂ Z be defined by S = ω−1({−4,1,2,6}). The set S is finite, and S connects Z. Hence,(Z,ω,pi,θ) is a periodic quadruple system.We now formally define the P-partitions that we have informally been calling the P-partitionsthat exhibit a certain repeating pattern.Definition 4.9. Let (Z,ω,pi,θ) be a periodic quadruple system and let n ∈N. Then a lengthn periodic (P,ω)-partition derived from (Z,ω,pi,θ) is a (P,ω)-partition (P,ω) such thatP = pi−1([n]) and ω ≡ ω|P. Moreover, a periodic (P,ω)-partition derived from (Z,ω,pi,θ)is a length n periodic (P,ω)-partition derived from (Z,ω,pi,θ) for some n ∈ N.Remark 4.10. Since P = pi−1([n]) =⋃nk=1pi−1({k}), P can be informally thought of as theposet that results from pasting together n copies pi−1({1}), pi−1({2}), . . . , and pi−1({n})of the poset pi−1({0}) where the pasting is determined by the periodic quadruple system(Z,ω,pi,θ).Enumeration formulas for counting certain combinatorial objects that we now describe wasestablished in [27] with special cases being established in [47, 49]. Let X be a parallel-ogramic shape with n rows and k cells in each row as described in Example 4.2. Thena standard Young tableau of shape X is a bijective filling of the cells of X with integersfrom [nk] such that the entries increase along every row from left to right and the entriesincrease along every column from top to bottom, and we call such a standard Young tableaua standard Young tableau of parallelogramic shape. For instance, the following is a standardYoung tableau of parallelogramic shape1 2 4 63 5 7 108 9 11 1227as the entries 3, 5, 7, and 10 increase from left to right along row 2 of the above Youngdiagram, the entries 4, 5, and 8 increase from top to bottom along column 3 of the aboveYoung diagram, and so on.Our analysis of P-partitions applies the above paragraph for the following reason. Con-sider a periodic quadruple system (Z,ω,pi,θ). The problem of enumerating the sequence(|Pn,ω|)n=1,2,..., where Pn = pi−1([n]) for all n, generalizes the problem of counting the num-ber of standard Young tableaux on parallelogramic shape, with n rows and k cells in eachrow, when k is fixed. The case when k = 4 is detailed in the following example.Example 4.11. Let Z, ω , pi , and θ be as in Example 4.6. Then the length n periodic (P,ω)-partitions derived from (Z,ω,pi,θ) correspond to the standard Young tableaux of parallelo-gramic shape with n rows and four cells in each row. For instance, three length 3 periodic(P,ω)-partitions derived from (Z,ω,pi,θ) are as follows, where the left-most and the middle(P,ω)-partitions depicted below are order equivalent.12 11 9 810 7 6 54 3 2 113 12 10 911 8 7 65 4 3 213 12 11 710 9 6 58 4 3 2In particular, replacing every entry k in the left-most diagram depicted above with 12−k+1 gives an example of standard Young tableaux of parallelogramic shape, and replacingevery entry k in the middle or right-most diagram depicted above with 12− k+2 gives twoexamples of standard Young tableaux of parallelogramic shape.Next, we explain how we can also apply our results to semistandard tableaux. If X is aparallelogramic shape, then define a semistandard tableau of shape X to be a function f :X→ Z where f (i1, j)< f (i2, j) if (i1, j),(i2, j) ∈ X and i1 < i2, and where f (i, j1)≤ f (i, j2)28if (i, j1),(i, j2) ∈ X and j1 < j2. That is, fill the cells of X so that the entries weakly increasealong every row from left to right, and the entries increase along every column from topto bottom. Moreover, if f is a semistandard tableau of shape X , then define a semistandardtableau class on X to be the set F of semistandard tableau of shape X that are order equivalentto f . For example, if X is a parallelogramic shape with n = 3 and k = 4, then a semistandardtableau class on X can be depicted by1 1 2 22 3 5 55 6 7 7.The periodic P-partitions that we introduced in Definition 4.9 can be regarded as a general-ization of the semistandard tableau of parallelogramic shape X if the number of cells in eachrow of X is fixed. This is explained in the following example when the number of cells ineach row is four.Example 4.12. Let Z, ω , pi , and θ be as in Example 4.8. Then the length n periodic (P,ω)-partitions derived from (Z,ω,pi,θ) correspond to the semistandard tableaux of parallelo-gramic shape with n rows and four cells in each row. For instance, three length 3 periodic(P,ω)-partitions derived from (Z,ω,pi,θ) are as follows, where the left-most and the middle(P,ω)-partitions depicted below are order equivalent.6 6 6 65 4 3 23 2 1 19 9 9 98 7 6 36 3 2 29 9 8 87 6 6 65 5 5 5In particular, replacing every entry k in each of the three diagrams depicted above with12−k+1 gives depictions of three semistandard tableaux of shape X, where X is the paral-lelogramic shape with 3 rows and 4 cells in each row.29Truncated shifted shapes are non-classical shapes that are a generalization of the parallelo-gramic shapes. For the following definition, note that if X1, X2, . . . is a sequence of sets andif n1,n2 ∈ N are such that n2 < n1, then ⋃n2i=n1 Xi = /0.Definition 4.13. (cf. [2, 49]) Let n∈N and let k1,k2, . . . ,kn be a sequence of positive integerssuch that for some i∈ [n], k1≤ k2≤ ·· · ≤ ki and ki≥ ki+1≥ ·· · ≥ kn. Then a truncated shiftedshape is the Young diagram X defined byX =n⋃i=1ki⋃j=i{(i, j)}.Remark 4.14. In Definition 4.13, if i = 1, then k1 ≥ k2 ≥ ·· · ≥ kn, and if i = n, then k1 ≤k2 ≤ ·· · ≤ kn.Example 4.15. Let n = 3, let k1 = 3, let k2 = 4, and let k3 = 3. By setting i = 2, we seethat k1 ≤ k2 ≤ ·· · ≤ ki and ki ≥ ki+1 ≥ ·· · ≥ kn because k1 ≤ k2 and k2 ≥ k3. Moreover, thetruncated shifted shape⋃ni=1⋃kij=i{(i, j)} is depicted below.Definition 4.16. (cf. [2, 49]) Let X be a truncated shifted shape that consists of n cells. Thena standard Young tableau of shape X is a bijective filling of the cells of X with the elementsof [n] such that entries increase from left to right along every row of X and entries increasefrom top to bottom along every column of X.Example 4.17. Consider the truncated shifted shape X in Example 4.15. The four standardYoung tableaux of shape X are depicted below.1 2 34 5 671 2 34 5 761 2 43 5 671 2 43 5 7630Periodic P-partitions can also be regarded as a generalization of the standard Young tableauxon certain truncated shifted shapes. Fix a number w ∈ N, assume that (an)n=1,2,... is a se-quence of positive integers that is periodic with period w, and assume that an ≥ 2 for alln ∈ N. For all m ∈ N, let Ym be a truncated shifted shape with mw rows such that forall 1 ≤ i ≤ mw, row i of Ym consists of ai cells. Consider a periodic quadruple system(Z,ω,pi,θ). The problem of enumerating the sequence (|Pn,ω|)n=1,2,..., where Pn = pi−1([n])for all n, is a generalization of the problem of counting the number of standard Youngtableaux of shape Ym, where the sequence (Ym)m=1,2,... is a defined above. This is illustratedin the following example.Example 4.18. Let (an)n=1,2,... be a periodic sequence, with period w = 2, that is defined by4, 5, 4, 5, . . . . Then the sequence of truncated shifted shapes corresponding to this periodicsequence is depicted below, , · · ·A periodic quadruple system (Z,ω,pi,θ) that we can use to enumerate the number of stan-dard Young tableaux on the above shapes is as follows. Let Z be depicted by the left-mostdiagram shown below, and let ω be depicted by the right-most diagram shown below.31◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦......−5−4−6−7−80−1−2−3453219876......Next, letpi−1({0}) = ω−1([9]) = ω−1({1,2,3,4,5,6,7,8,9}),letpi−1({1}) = ω−1([−8,0]) = ω−1({−8,−7,−6,−5,−4,−3,−2,−1,0}),and so on. Moreover, let θ : Z → Z be defined by θ(ω−1(n)) = ω−1(n− 9) for all n ∈ Z.Then the map α : Z→ Z defined by α(n) = n−9 for all n ∈ Z satisfies α(ω(p)) = ω(θ(p))for all p∈ Z. Moreover, for all p∈ Z, s(pi(p)) = pi(θ(p)). Hence, the quadruple (Z,ω,pi,θ)satisfies Property 1 of Definition 4.3. Moreover, ω−1({2,3,4,6,7,8}) is a finite subset of Zthat connects Z. So (Z,ω,pi,θ) also satisfies Property 2 of Definition 4.3. It follows that thequadruple defined is a periodic quadruple system.A natural question is to ask whether there exist periodic quadruple systems that are d-dimensional analogues of the periodic quadruple systems considered in Example 4.11, Ex-ample 4.12, and Example 4.18 for d ≥ 3. To that end, we prove that, for d ≥ 3, there exist32periodic quadruple systems that are d-dimensional analogues of Example 4.6 and Example4.8.We construct a family of periodic quadruple systems (Z,ω,pi,θ), which generalize Example4.8 and Example 4.6, such that Z is a subposet of Zd .Definition 4.19. Fix a positive integer d ≥ 2, and consider Zd . Then let n1,n2, . . . ,nd−1 ∈Nand n′1,n′2, . . . ,n′d−1 ∈ N satisfy ni > n′i for all 1≤ i≤ d−1. Next, let X ⊂ Zd be defined byX = [n1]× [n2]×·· ·× [nd−1]×{0},and define ∆ ∈ Zd by∆= (n′1,n′2, . . . ,n′d−1,1),where 0< n′i < ni for all 1≤ i≤ d−1. Lastly, defineZ(X ,∆) =⋃n∈Z(X +n∆).Informally, Z(X ,∆) is a union of translates of a (d−1)-dimensional parallelogram where Xis the parallelogram and ∆ is the translate. Moreover, recall that we will regard Zd as a posetas described in Definition 2.2. So as Z(X ,∆) ⊂ Zd we will regard Z(X ,∆) as a subposet ofZd . Because Zd is a countably infinite and locally finite poset, Z(X ,∆) is a countably infiniteand locally finite poset. An example of such a poset Z(X ,∆) when d = 3, n1 = n2 = 3, andn′1 = n′2 = 1 is depicted in the left-most diagram of Figure 4.1. Moreover, the poset Z inExample 4.8 and Example 4.6 satisfies Z = Z(X ,∆) where X = {(1,0),(2,0),(3,0),(4,0)}and ∆= (1,1).Informally, we can think of Z = Z(X ,∆) as a pair consisting of a set of points and a shift.33Definition 4.20. Let Z(X ,∆) be as described in Definition 4.19. Then define pi∆X : Z(X ,∆)→Z by pi(p) = n for all n ∈ Z and for all p ∈ X +n∆, and define θ∆X : Z(X ,∆)→ Z by θ(p) =p+∆ for all p ∈ Z(X ,∆).Informally, pi∆X indicates which copy of X we have, and θ∆X indicates where the next copy ofa point is.Example 4.21. Let d = 2, X = {(1,0),(2,0)}, and let ∆=(1,1). Moreover, let (Z1,ω1,pi1,θ1)be the periodic quadruple system from Example 4.6 and let (Z1,ω2,pi2,θ2) be the periodicquadruple system from Example 4.8. ThenZ1 = Z2 = Z(X ,∆), pi1 = pi2 = pi∆X , and θ1 = θ2 = θ∆X .Example 4.22. Consider the labelling ω of Z(X ,∆) depicted by the right-most diagram inFigure 4.1, and assume that ω(X) = [−1,7]. Then pi∆X ({[−10,−2]}) =−1, pi∆X ([−1,7]) = 0,pi∆X ([8,16]) = 1, and so on. Moreover, θ∆X (ω−1(5)) = ω−1(14), θ∆X (ω−1(−7)) = ω−1(2),and so on.The dual natural labelling ω in Example 4.6 can be generalized. For we can let ω be a dualnatural labelling of Z(X ,∆) such that ω(p) > ω(q) for all p,q ∈ Z(X ,∆) and ω(p′+∆) =ω(p′)− |X | for all p′ ∈ Z(X ,∆). Moreover, note that such a natural labelling ω has theproperty that (Z(X ,∆),ω,pi∆X ,θ∆X ) satisfies Property 1 of Definition 4.3.Define the following family of hyperplanes of Zd . For all i ∈ [d] and k ∈ Z, letHi,k = {(k1,k2, . . . ,kd) ∈ Zd : ki = k}.Informally, Hi,k is the hyperplane of Zd that consists of all points whose ith coordinate equalsto k.34Moreover, for brevity, call a subset S ⊆ Z(X ,∆) a 0-subset of Z(X ,∆) if S = Z(X ,∆), and, ifk ∈ [d], define a k-subset of Z(X ,∆) to be a proper subset S⊂ Z(X ,∆) such that S 6= /0 andS = Z(X ,∆) ∩k⋂i=1Hd−i+1,nifor some n1,n2, . . . ,nk ∈ Z. Because Z(X ,∆)∩Hd,n = X +n∆ for all n ∈ Z, any 1-subset ofZ(X ,∆) is finite. It follows that if k ≥ 1, then any k-subset of Z(X ,∆) is finite.Example 4.23. Consider the set X, the poset Z(X ,∆), and the labelling ω of Z(X ,∆) inExample 4.22. Moreover, refer to Figure 4.1. An example of a 1-subset of Z(X ,∆) is X,which satisfies ω(X) = [−1,7]. This is because, by letting n3 = 0, we haveX = Z(X ,∆)∩H3,0.An example of a 2-subset of Z(X ,∆) is the subset S(2) of X satisfying ω(S(2)) = {5,6,7}.This is because, by letting n3 = 0 and n2 = 0, we haveS(2) = Z(X ,∆)∩H3,0∩H2,0.Lastly, an example of a 3-subset of Z(X ,∆) is the subset S(3) of S(2) satisfying ω(S(3)) = {6}.This is because, by letting n3 = 0, n2 = 0, and n1 = 1, we haveS(3) = Z(X ,∆)∩H3,0∩H2,0∩H1,1.With the notion of a k-subset, we can define a generalization of Schur labellings as follows.Definition 4.24. For all k ∈ [d− 1], let uk be the element of Zd such that for all 1 ≤ i ≤ d,the ith coordinate of uk is 0 if i 6= k and 1 if i = k. Moreover, define ud = ∆. Then ω∆X is the35labelling of Z(X ,∆) such that 0 ∈ ω∆X (X) and the following holds. If 1≤ k≤ d, p ∈ Z(X ,∆),and S is the (d− k+1)-subset of Z(X ,∆) that contains p, thenω∆X (p+uk) = ω∆X (p)+(−1)k−1|S|.Example 4.25. Consider the set X, the poset Z(X ,∆), and the labelling ω of Z(X ,∆) inExample 4.22. Moreover, refer to Figure 4.1. The labelling ω equals to ω∆X . Firstly, bythe definition of ω in Example 4.22, 0 ∈ ω(X). Secondly, to illustrate how ω satisfies allconditions of Definition 4.24, let p ∈ Z(X ,∆) be defined by p= ω−1(6). Since u1 = (1,0,0),u2 = (0,1,0), and u3 = ∆ = (1,1,1), we have that p+u1 = ω−1(7), p+u2 = ω−1(3), andp+u3 = ω−1(15). Moreover, let S(1) = X, let S(2) be as in Example 4.23, and let S(3) be asin Example 4.23. These three sets are such that S(1) is the 1-subset of Z(X ,∆) that containsp, S(2) is the 2-subset of Z(X ,∆) that contains p, and S(3) is the 3-subset of Z(X ,∆) thatcontains p. Moreover, |S(1)|= |X |= 9, |S(2)|= 3, and |S(3)|= 1. Hence,ω(p+u1) = 7 = 6+1 = ω(p)+(−1)0 ·1 = ω(p)+(−1)0|S(3)|,ω(p+u2) = 3 = 6−3 = ω(p)+(−1)1 ·3 = ω(p)+(−1)1|S(2)|,and ω(p+u3) = 15 = 6+9 = ω(p)+(−1)2 ·9 = ω(p)+(−1)2|S(1)|.The generalized Schur labelling ω∆X of Z(X ,∆) satisfiesω∆X (p+∆) = ω∆X (p)+(−1)d−1 |X |for all p∈ Z(X ,∆). So, from the above definitions of pi∆X and θ∆X , the quadruple (Z(X ,∆),ω∆X ,pi∆X ,θ∆X ) satisfies Property 1 of Definition 4.3.36◦◦ ◦◦ ◦ ◦◦ ◦◦◦◦ ◦◦ ◦ ◦◦ ◦◦◦◦ ◦◦ ◦ ◦◦ ◦◦◦◦......109 138 12 1611 151410 4−1 3 72 65−8−9 −5−10 −6 −2−7 −3−4−1723......Figure 4.1: A three-dimensional analogue of Example 4.8. Here, X = {(i, j,0) : 1 ≤i≤ 3 and 1≤ j ≤ 3} and ∆= (1,1,1).Let ω be a labelling of Z(X ,∆) such that (Z(X ,∆),ω,pi∆X ,θ∆X ) satisfies Property 1 of Defini-tion 4.3. Because X is finite, we see that (Z(X ,∆),ω,pi∆X ,θ∆X ) satisfies Property 2 of Defini-tion 4.3. We show that (Z(X ,∆),ω,pi∆X ,θ∆X ) also satisfies Property 3 of Definition 4.3.Recall that, informally, Z(X ,∆) is a union of translates of a (d− 1)-dimensional parallelo-gram where X is the parallelogram and ∆ is the translate. Moreover, recall that, informally,Hi,k is the hyperplane of Zd that consists of all points whose ith coordinate equals k.Theorem 4.26. Let Z(X ,∆) be as described in Definition 4.19, and let pi∆X , and θ∆X be37as described in Definition 4.20. If ω is a labelling of Z(X ,∆) such that the quadruple(Z(X ,∆),ω,pi∆X ,θ∆X ) satisfies Property 1 of Definition 4.3, then (Z(X ,∆),ω,pi∆X ,θ∆X ) is a pe-riodic quadruple system. In particular, the quadruple (Z(X ,∆),ω∆X ,pi∆X ,θ∆X ) is a periodicquadruple system, there are periodic quadruple systems (Z(X ,∆),ω,pi∆X ,θ∆X ) where ω isnatural, and there are periodic quadruple systems (Z(X ,∆),ω,pi∆X ,θ∆X ) where ω is dual nat-ural.We roughly indicate how we will prove Theorem 4.26 in the following example.Example 4.27. Consider the poset Z(X ,∆) where X is{(1,1,0),(1,2,0),(1,3,0),(2,1,0),(2,2,0),(2,3,0),(3,1,0),(3,2,0),(3,3,0)}and where ∆ = (1,1,1). Moreover, let pi = pi∆X , where pi∆X is as described in Definition 4.20.In each of the three diagrams in this example, the point (1,1,0) is highlighted in blue, thepoint (1,2,0) is highlighted in red, and the point (1,3,0) is highlighted in green.The intersection H1,2∩Z(X ,∆) consists of nine elements and is depicted by the nine elementsin the left-most diagram shown below that are filled with bullets. Moreover, the intersectionH2,2∩Z(X ,∆) consists of nine elements and is depicted by the nine elements in the right-mostdiagram shown below that are filled with bullets or that are highlighted in red.38◦◦ ◦• ◦ ◦• ◦•◦• ◦• • ◦• •••◦ •◦ ◦ •◦ ◦◦◦◦......◦◦ ◦◦ ◦ •◦ ••◦◦ •• • ◦• ◦••• ◦• ◦ ◦◦ ◦◦◦◦......Lastly, the intersection H3,0∩Z(X ,∆) consists of the nine elements depicted below that arefilled with bullets, highlighted in blue, highlighted in red, or highlighted in green.39◦◦ ◦◦ ◦ ◦◦ ◦◦•• •• • •• ••◦◦ ◦◦ ◦ ◦◦ ◦◦◦◦......From the depictions of H1,2∩Z(X ,∆), H2,2∩Z(X ,∆), and H3,0∩Z(X ,∆), we see that for allp′,q ∈ Z(X ,∆) such that pi(q) ≥ 2 and pi(p′) = −2, p′ < q because H1,2 lies in between p′and q, H2,2 lies in between p′ and q, and H3,0 lies in between p′ and q. Similarly, we see thatfor all p, p′ ∈ Z(X ,∆) such that pi(p′) = −2 and pi(p) ≤ −6, p < p′. Hence, the finite setpi−1([−5,1]), which has 7 ·9 = 63 elements, connects Z(X ,∆).Now, we prove Theorem 4.26.Proof. If ω is a labelling of Z(X ,∆) such that the quadruple (Z(X ,∆),ω,pi∆X ,θ∆X ) satisfiesProperty 1 of Definition 4.3, then the following can be said. Assume that there is a finite40subset S of Z(X ,∆) such that S connects Z(X ,∆), then the quadruple (Z(X ,∆),ω,pi∆X ,θ∆X )satisfies Property 3 of Definition 4.3. Moreover, by Definition 4.19 and Definition 4.20,(Z(X ,∆),ω,pi∆X ,θ∆X ) satisfies Property 2 of Definition 4.3. This implies, by Definition 4.3,that the quadruple (Z(X ,∆),ω,pi∆X ,θ∆X ) is a periodic quadruple system.Hence, to prove the theorem it is enough to prove that there is a finite subset S of Z(X ,∆)such that S connects Z(X ,∆). Let pi = pi∆X , and let d be the positive integer corresponding toX , ∆, and Z(X ,∆) as described in Definition 4.19.We first show that for all i∈ [d] and k ∈Z, Z(X ,∆)∩Hi,k is finite. Suppose that Z(X ,∆)∩Hi,kis infinite for some i ∈ [d] and k ∈ Z. Then consider the subsets (X +n∆)∩Hi,k for all n ∈ Z.Since Z(X ,∆)∩Hi,k is infinite, since X +n∆ is finite for all n ∈ Z, and sinceZ(X ,∆) =⋃n∈ZX +n∆,there is an infinite subset Y ⊆ Z such that (X + n∆)∩Hi,k 6= /0 for all n ∈ Y . Recall that∆= (n′1,n′2, . . . ,n′d−1,1), and write n′d = 1. Since n′j > 0 for all j ∈ [d], the definition of Hi,kimplies that the following holds for all p ∈ X|{p+n∆ : n ∈ Z}∩Hi,k| ≤ 1.So for all distinct n1,n2 ∈ Y ,{p ∈ X : p+n1∆ ∈ Hi,k}∩{p ∈ X : p+n2∆ ∈ Hi,k}= /0.41But then, as Y is infinite and as⋃n∈Y{p ∈ X : p+n∆ ∈ Hi,k} ⊆ X ,it follows that X is infinite, contradicting the assumption that X is finite. So Z(X ,∆)∩Hi,k isfinite for all i ∈ [d] and k ∈ Z.Since ∆ = (n′1,n′2, . . . ,n′d) and, for all j ∈ [d], n′j > 0, it follows from the definition of Hi,kthat for all i ∈ [d] and k ∈ Z,Hi,k∩Z(X ,∆) 6= /0.Hence, as Z(X ,∆)∩Hi,k is finite for all i ∈ [d] and k ∈ Z, there is a positive integer m and asequence of integers k∗1,k∗2, . . . ,k∗d , such that Z∩Hi,k∗i 6= /0 and Z(X ,∆)∩Hi,k∗i ⊆ pi−1([m]) forall i ∈ [d]. Now, observe that the definition of the partial order on Zd implies the following.If v1,v2 ∈ Zd , and if, for all i ∈ [d], there are integers n′i,n′′i ∈ Z such that n′i < n′′i , v1 ∈ Hi,n′i ,and v2 ∈ Hi,k′′i , then v1 < v2 in Zd . Hence, if p,q ∈ Z(X ,∆) are such that pi(p) < 1 andpi(q)> m, then p < q in Z(X ,∆). Repeating this argument for pi−1([m+2,2m+1]) insteadof pi−1([m]), we see that if p,q ∈ Z(X ,∆) are such that pi(p) < 1 and pi(q) > 2m+ 1, thenthere is an element p′ ∈ pi−1({m+1}) such that p< p′ < q in Z(X ,∆). Therefore, the finitesubset S ⊂ Z(X ,∆) defined by S = pi−1([2m+1]) connects Z(X ,∆). From this, the theoremfollows.Hence, there are d-dimensional analogues of Example 4.8 and Example 4.6 for all d ≥ 3.Remark 4.28. The proof of Theorem 4.26 can be used to generalize Theorem 4.26 to includeexamples such as Example 4.18. This is based on the fact that the proof of Theorem 4.26 does42◦◦◦◦◦◦◦q1◦p1◦q0◦p0◦q−1◦p−1◦◦◦◦◦◦.... . .Figure 4.2: A more exotic example of a periodic quadruple system.not entirely depend on Definition 4.19.Periodic quadruple systems, and their corresponding periodic (P,ω)-partitions, can be verydifferent from the examples we have considered so far. The following is a simple exampleof such a system.Example 4.29. Let Z be the poset depicted in Figure 4.2. And let p1, q1, p0, q0, p−1, andq−1 be the six elements of Z that are as specified in Figure 4.2. Let ω : Z → Z be definedby ω(p0) = 0, ω(q0) = 1, and, for all p ∈ Z, ω(θ(p)) = ω(p)+ 2, let pi : Z → Z satisfypi(p1)= pi(q1)= 1, pi(p0)= pi(q0)= 0, pi(p−1)= pi(q−1)=−1, and so on, and let θ : Z→ Z43satisfy θ(p−1) = p0, θ(q−1) = q0, θ(p0) = p1, θ(q0) = q1, and so on. To check that thequadruple (Z,ω,pi,θ) satisfies Property 1 of Definition 4.3, let α : Z→ Z be defined byα(n) = n+2 for all n ∈Z. Then for all p ∈ Z, s(pi(p)) = pi(θ(p)) and α(ω(p)) =ω(θ(p)).To see that (Z,ω,pi,θ) satisfies Property 3 of Definition 4.3, let Pn = pi−1([n]) for all n ∈ N.We show that P15 connects Z. Consider the element q0 ∈ Z. We have the inequalities,q0 < θ 4(p0)< θ 7(p0)< θ 10(p0)< θ 13(p0),q0 < θ 4(p0)< θ 4(q0)< θ 8(p0)< θ 11(p0)< θ 14(p0),andq0 < θ 4(p0)< θ 4(q0)< θ 8(p0)< θ 8(q0)< θ 12(p0).Moreover, {θ 14(p0),θ 13(p0),θ 12(p0)} is the set of minimal elements of pi−1([12, ∞)). So as{θ 14(p0),θ 13(p0),θ 12(p0)} ⊂ P15, it follows that for all p ∈ Z satisfying pi(p) ≥ 16, thereis an element q ∈ P15 such that q0 < q < p. Since θ is an order automorphism on Z, thesame conclusions also hold for θ−1(q0) and θ−1(P15) = pi−1([0,14]), and for θ−2(q0) andθ−2(P15) = pi−1([−1,13]). So as {q0,θ−1(q0),θ−2(q0)} is the set of maximal elements ofpi−1(Z\N), it follows that P15 connects Z. Hence, (Z,ω,pi,θ) is a periodic quadruple system.44Chapter 5The matrix difference equationIn this chapter, we enumerate the number of periodic P-partitions as follows. We definecollections of numbers that sum to the number we are interested in. Each member of thiscollection counts periodic P-partitions that satisfy certain additional restrictions. Afterwards,we introduce tableau transfer matrices, whose entries count certain P-partitions, and provethe following. We first prove a structural property of the connected triples we introduced inthe previous chapter. Then, using this structural property, we prove that the aforementionedcollections of numbers, represented as column vectors, can be enumerated with a homoge-neous first-order matrix difference equation in which the matrix is a tableau transfer matrix.Building from the previous chapter, we define the following notion.Definition 5.1. Let (Z,ω,pi,θ) be a periodic quadruple system. Then an index shape of(Z,ω,pi,θ) is a finite subset S of pi−1(Z\N) that satisfies the following two properties.1. (pi−1(Z\N)\S , S , pi−1(N)) is a connected triple of Z.452. θ(S)⊆ S∪pi−1({1}).Remark 5.2. If S is an index shape of a periodic quadruple system (Z,ω,pi,θ), then Sconnects Z. This fact, and the fact that S is finite, will become important later on in thischapter.Using Example 4.6 as a guide, we start our running example.Example 5.3. Let (Z,ω,pi,θ) and S be as defined in Example 4.6. Since in Example 4.6 wesaw θ(ω−1(n)) = ω−1(n−4),S = ω−1({−6,−4,−2,−1}),(pi−1(Z\N)\S,S,pi−1(N)) is a connected triple of Z. Hence, S satisfies Property 1 of Defi-nition 5.1. Sinceθ(S) = ω−1({−10,−8,−6, −5}) and pi−1({1}) = ω−1({−10,−8,−5,−3}),θ(S) = ω−1({−10,−8,−6,−5})⊆ ω−1({−10,−8,−6,−5,−4,−3,−2,−1}) = S∪pi−1({1}).Hence, θ(S)⊆ S∪pi−1({1}), implying that S satisfies Property 2 of Definition 5.1. It followsthat S is an index shape of (Z,ω,pi,θ).The following definition is an analogue of the notion of order equivalence that depends onthe order automorphism θ on Z in a periodic quadruple system.Definition 5.4. Let (Z,ω,pi,θ) be a periodic quadruple system, and let S1 and S2 be subsetsof Z. And assume that S2 = θ k(S1) for some k ∈ Z. Then for all T1 ∈ Tb(S1,ω) and T2 ∈46Tb(S2,ω), write T1 ≡θ T2 if for all U1 ∈ T1 and U2 ∈ T2, there is an order isomorphismg : U1(S1)→U2(S2) such that g◦U1 =U2 ◦θ k.Informally, the above definition says that T1 ≡θ T2 if the relative ordering of the entries in T1is the same as the relative ordering of the entries in T2.Example 5.5. Let (Z,ω,pi,θ) and S be as described in Example 5.3. First note fromExample 5.3 that since θ(ω−1(n)) = ω−1(n− 4), θ−1(ω−1(n)) = ω−1(n+ 4). The sub-poset S of Z can be depicted using the left-most Young diagram shown below, the subposetS ∪ θ−1(S) ∪ pi−1({0}) of Z can be depicted using the right-most Young diagram shown be-low that consists of eight cells. In the right-most Young diagram, the cells filled with circlesor asterisks represents θ−1(S) and the cells filled with asterisks or bullets represents S.◦◦ ◦ ∗• • •Let T be the element of Tb(S ∪ θ−1(S) ∪ pi−1({0}) , ω) that is depicted by the left-mostdiagram shown below.78 6 35 4 2 178 6 334 2 1Now, let S1 = θ−1(S), let S2 = S, let T1 = T |S1 , let T2 = T |S2 , and let k = 1. Firstly, S2 =θ k(S1). Secondly, for all U1 ∈ T1 and U2 ∈ T2, there is an order isomorphism g : U1(S1)→U2(S2) such that g ◦U1 = U2 ◦ θ k. For instance, if U1 is depicted by the middle diagramshown above and if U2 is depicted by the right-most diagram shown above, then define g :{3,6,7,8} → {1,2,3,4} by g(3) = 1, g(6) = 2, g(7) = 3, and g(8) = 4. The map g is an47order isomorphism from {3,6,7,8} to {1,2,3,4} and g satisfies g◦U1 =U2 ◦θ k. From this,we see that T1 ≡θ T2.We now use index shapes to define the following family of square matrices. Informally, weare defining matrices that are built from index shapes and that allow us to enumerate manydifferent (P,ω)-partitions at once. Recall that we write M(i, j) to denote the entry in row iand column j of a matrix M. Lastly, in the following definition, note thatS⊆ θ−1(S)∪pi−1({0})due to Property 2 of Definition 5.1.Definition 5.6. Let (Z,ω,pi,θ) be a periodic quadruple system, and let S be an index shapeof (Z,ω,pi,θ). Moreover, let L be an indexing of Tb(S,ω), let N = |S,ω|, and let R : [N]→Tb(S,ω) be the inverse of L. Then the tableau transfer matrix M derived from (Z,ω,pi,θ),S, and L is the N by N matrix M such that for all 1 ≤ i ≤ N and 1 ≤ j ≤ N, M(i, j) is thenumber of elements T ofTb(θ−1(S)∪pi−1({0}),ω)such thatT |S ≡θ R(i) and T |θ−1(S) ≡θ R( j).When S and L are not specified, we will call M a tableau transfer matrix derived from(Z,ω,pi,θ).Example 5.7. Consider the periodic quadruple system (Z,ω,pi,θ) and the index shape Sfrom Example 5.5. There are two elements of Tb(S,ω), and they are depicted by the belowdiagrams.4843 2 134 2 1In particular, N = 2. Next, define L : Tb(S,ω)→ {1,2} so that L sends the element ofTb(S,ω) depicted by the left-most diagram shown above to 1 and L sends the element ofTb(S,ω) depicted by the right-most diagram shown above to 2. Lastly, let R = L−1 be theinverse of L so thatR(1) = 43 2 1and R(2) = 34 2 1.The tableau transfer matrix M derived from (Z,ω,pi,θ), S, and L is equal to3 42 3 .To see how to construct M, we calculate M(2,1). The number M(2,1) is the number ofelements T ∈ Tb(S ∪ θ−1(S) ∪ pi−1({0}) , ω) such that T |S = R(2) and T |θ−1(S) ≡θ R(1).Consider the below diagram, which depicts S as the set of cells filled with bullets or asterisks,which depicts θ−1(S) as the set of cells filled with circles or asterisks, and which depictspi−1({0}) as the set of cells filled with bullets or are empty.◦◦ ◦ ∗• • •By an exhaustive search in which we use the left-most diagram shown below as a reference,it can be checked that the two elements T of Tb(S ∪ θ−1(S) ∪ pi−1({0}) , ω) such thatT |S = R(2) and T |θ−1(S) ≡θ R(1) are the elements that are depicted by the left-most diagramshown below or the right-most diagram shown below.4987 6 35 4 2 187 5 36 4 2 1To complement Definition 5.6, we define the following. Informally, we are defining thecolumn vectors that correspond to the tableau transfer matrices. Recall that we write v(i) todenote the entry in row i of a column vector v.Definition 5.8. Let (Z,ω,pi,θ) be a periodic quadruple system, let S be an index shape of(Z,ω,pi,θ), and let L be an indexing of Tb(S,ω). Moreover, let R = L−1 be the inverseof L. Then an admissible number for (Z,ω,pi,θ) and S is an integer n′ such that n′ ≤0 and S ⊆ pi−1([n′,0]). Next, let n′ be an admissible number for (Z,ω,pi,θ) and S, letT0 ∈ Tb(pi−1([n′,0]),ω), let n ∈ N, let Qn = pi−1([n′,n]), let Pn = pi−1([n]), and let P′ =pi−1([n′,0]).Define the nth set derived from (Z,ω,pi,θ), S, and T0 to be the set Xn(T0) of elements T ∈Tb(Qn,ω) such that T |P′ = T0 and the following condition holds. If U ∈ T , p ∈ P′, andq ∈ Pn, then U(p)>U(q).Moreover, for all 1 ≤ i ≤ |S,ω|, let the ith part of the nth set derived from (Z,ω,pi,θ), S, L,and T0 be the set Xn,i(T0) of elements T ∈ Xn(T0) such that T |θn(S) ≡θ R(i). Lastly, definethe nth vector derived from (Z,ω,pi,θ), S, L, and T0 to be the column vector vn with |S,ω|entries such that, for all 1≤ i≤ |S,ω|, vn(i) = |Xn,i(T0)|.Informally, the above definition describes the following. The nth sets as given in the abovedefinition are a collection of modified periodic (P,ω)-partitions that will allow us to enumer-ate the periodic (P,ω)-partitions themselves. Moreover, the ith parts of such sets, as given inthe above definition, provides us with a set partition of such collections of modified periodic50(P,ω)-partitions that we will use later on in the chapter, and the nth vectors give the cardinal-ities of these ith parts. Lastly, admissible numbers enable us to effectively use such modifiedperiodic (P,ω)-partitions.Example 5.9. Let (Z,ω,pi,θ), S, and L be as in Example 5.7, and let R= L−1 be the inverseof L. In particular, from Example 5.7, S = ω−1({−6,−4,−2,−1}). The number n′ =−1 isan admissible number for (Z,ω,pi,θ) and S becauseS⊆ pi−1([−1,0]),and from Example 4.6,pi−1({0}) = ω−1({−6,−4,−1,1}) and pi−1({−1}) = ω−1({−2,0,3,5}).This is depicted below where the eight cells represent pi−1([−1,0]) and the cells filled withbullets represent S.•• • •In particular, as n′ =−1, P′ = pi−1([−1,0]) and Tb(pi−1([n′,0]),ω) = Tb(pi−1([−1,0]),ω).Depicted below are the first three terms of (Qn)n=1,2,.... The first three terms of (Pn)n=1,2,...are depicted by the cells filled will bullets (note that Pn ⊆ Qn for all n = 1,2, . . . ). Moreover,in each of the three diagrams, the eight blank cells depict P′ = pi−1([−1,0]).• • • •,• • • •• • • •,• • • •• • • •• • • •, . . .51Next, assume that T0 is the following element of Tb(pi−1([−1,0]),ω).8 7 6 45 3 2 1We illustrate Xn(T0), Xn,i(T0), and vn when n= 1. As described in Example 5.7, Tb(S,ω) hastwo elements. Hence, by Definition 3.6, |S,ω|= 2 and it follows that the range for the indexi is 1 ≤ i ≤ 2. The 1st set X1(T0) derived from (Z,ω,pi,θ), S, and T0 can be determined asfollows.Consider the element T ∈ Tb(pi−1([−1,1]),ω) defined by12 11 10 89 7 6 54 3 2 1.To see that T ∈ X1(T0), we note the following. Since T |P′ is depicted below,12 11 10 89 7 6 5,T |P′ = T0 by definition. Lastly, note that for all U ∈ T , p ∈ P′, and q ∈ P1, U(p)>U(q). Forinstance, let U ∈ T be defined by22 21 20 1112 8 7 64 3 1 0,let p ∈ P′ be depicted below by the cell filled with a circle, and let q ∈ P1 be depicted belowby the cell filled with a bullet.52◦•Then,U(p) = 11> 4 =U(q).Any element T ′ of Tb(pi−1([−1,1],ω) that is not T does not satisfy the condition T ′|P′ = T0or does not satisfy the condition U(p)>U(q) for some U ∈ T ′, p ∈ P′, and q ∈ P1. Hence,the 1st set X1(T0) derived from (Z,ω,pi,θ), S, and T0 isX1(T0) = {T}.Let T be the element of X1(T0). Since θ(S) is depicted by the four cells filled with bullets,where the twelve cell diagram below depicts Q1•• • •,it follows that T |θ(S) is depicted by the following from the definition of T on the previouspage.53 2 1It follows that T |θ(S) ≡θ R(1), hence the 1st part, X1,1(T0), of the 1st set derived from(Z,ω,pi,θ), S, L, and T0, is X1(T0). Moreover, the 2nd part, X1,2(T0), of the 1st set de-rived from (Z,ω,pi,θ), S, L, and T0, is the empty set because the only element of X1(T0) isT , T |θ(S) ≡θ R(1), and R(2) 6= R(1).53Therefore, as |X1,1(T0)|= 1 and |X1,2(T0)|= 0, the 1st vector derived from (Z,ω,pi,θ), S, L,and T0 is the following column vector.v1 =10The sum of the entries in the column vectors defined in Definition 5.8 gives the number ofperiodic (P,ω)-partitions.Proposition 5.10. Let (Z,ω,pi,θ) be a periodic quadruple system. Moreover, let S be anindex shape of (Z,ω,pi,θ), let L be an indexing of Tb(S,ω), let R = L−1 be the inverse ofL, let Pn = pi−1([n]) for all n ∈ N, let n′ be an admissible number for (Z,ω,pi,θ) and S,let T0 ∈ Tb(pi−1([n′,0]),ω), and let N = |S,ω|. Lastly, let vn be the nth vector derived from(Z,ω,pi,θ), S, L, and T0. Then for all n ∈ N,|Pn,ω|=N∑i=1vn(i).Before proving this proposition, we illustrate this proposition with an example.Example 5.11. Let (Z,ω,pi,θ), S, and L be as in Example 5.7. Moreover, let R = L−1 bethe inverse of L. By Example 5.9, an admissible number n′ for (Z,ω,pi,θ) is n′ =−1. So letT0 ∈ Tb(pi−1([n′,0]),ω) be depicted by the following diagram as calculated in Example 5.9.8 7 6 45 3 2 1One can calculate that the 2nd vector v2 derived from (Z,ω,pi,θ), S, L, and T0 is equal to32 .54To see how to calculate v2, we note the following. Let P′ = pi−1([−1,0]) be as in Example5.9 and set n = 2. Then, as n′ =−1, Qn = Q2 is depicted by the twelve cell diagram below,Pn = P2 is depicted by the cells filled with bullets, and P′ is depicted by the blank cells ascalculated in Example 5.9.• • • •• • • •In the same way that we calculated the 1st set X1(T0) derived from (Z,ω,pi,θ), S, and T0,we can calculate that the 2nd set X2(T0) derived from (Z,ω,pi,θ), S, and T0 consists of thefollowing five elements.16 15 14 1213 11 10 98 7 6 35 4 2 116 15 14 1213 11 10 98 7 5 36 4 2 116 15 14 1213 11 10 98 7 6 54 3 2 116 15 14 1213 11 10 98 7 5 46 3 2 116 15 14 1213 11 10 98 7 6 45 3 2 1To check that the above diagrams depict elements of X2(T0), note that each element T ∈X2(T0) depicted above satisfies T |P′ ≡θ T0 because T |P′ is depicted below.16 15 14 1213 11 10 9Moreover, as in Example 5.9, it can be seen that for all T ∈ X2(T0) depicted above, for allU ∈ T , for all p ∈ P′, and for all q ∈ P2, U(p)>U(q).55Next, note that, θ 2(S) is depicted by the four cells filled with bullets, where the sixteen celldiagram below depicts Q2 as calculated in Example 5.9.•• • •Hence, the following holds. The 1st part, X2,1(T0), of the 2nd set derived from (Z,ω,pi,θ), S,L, and T0 consists of the elements T ∈ X2(T0) such that Tθ2(S) ≡θ R(1). It can be checked,by checking the five elements earlier in this example and comparing the entries that are inθ 2(S) with R(1) as given in Example 5.9, that the elements of X2,1(T0) are depicted below.16 15 14 1213 11 10 98 7 6 54 3 2 116 15 14 1213 11 10 98 7 5 46 3 2 116 15 14 1213 11 10 98 7 6 45 3 2 1In particular,v2(1) = |X2,1(T0)|= 3.The 2nd part, X2,2(T0), of the 2nd set derived from (Z,ω,pi,θ), S, L, and T0 consists of theelements T ∈ X2(T0) such that Tθ2(S) ≡θ R(2). It can be checked similarly to the calculationof X2,1(T0) above that the elements of X2,1(T0) are depicted below.16 15 14 1213 11 10 98 7 6 35 4 2 116 15 14 1213 11 10 98 7 5 36 4 2 1In particular,v2(2) = |X2,2(T0)|= 2.56The sum of the entries of v2 is v2(1)+v2(2) = 3+2= 5. Moreover, Tb(P2,ω) consists of thefollowing five elements.8 7 6 35 4 2 18 7 5 36 4 2 18 7 6 54 3 2 18 7 5 46 3 2 18 7 6 45 3 2 1In particular, |P2,ω|= 5, which equals to the sum of the entries of v2.Proof. Let n ∈N, let Xn,i(T0) be the ith part of the nth set derived from (Z,ω,pi,θ), S, L, andT0 for all 1≤ i≤ N, and let Xn(T0) be the nth set derived from (Z,ω,pi,θ), S, and T0. Recallthat, by Definition 5.8, Xn,i(T0) is the set of elements T ∈ Xn(T0) such thatT |θn(S) ≡θ R(i)for all 1 ≤ i ≤ N. Moreover, for all T ∈ Xn(T0), there is exactly one number 1 ≤ i ≤ Nsuch that T |θn(S) ≡θ R(i) because R(i1) 6= R(i2) for all 1≤ i1 ≤ N and 1≤ i2 ≤ N satisfyingi1 6= i2. Hence, we haveXn(T0) =N⋃i=1Xn,i(T0),where the union is pairwise disjoint. Moreover, |Xn(T0)| = |Pn,ω| for the following reason.Define the map f : Xn(T0)→ Tb(Pn,ω) byf (T ) = T |Pn.By Definition 5.8, T |P′ = T ′|P′ = T0 for all T,T ′ ∈ Xn(T0), where P′ = pi−1([n′,0]). Fur-thermore, for all T ∈ Xn(T0), for all U ∈ T , for all p ∈ P′, and for all q ∈ Pn, U(p) >U(q).57Hence, for all T,T ′ ∈ Xn(T0), T 6= T ′ if and only if T |Pn 6= T ′|Pn . So as f (T ) = T |Pn for allT ∈ Tb(Pn,ω), f is injective.To see that the map f is surjective, let T ∈ Tb(Pn,ω) and let U ∈ T . Set Qn = pi−1([n′,n])and let U0 ∈ T0 be such that for all p ∈ P′ and q ∈ Pn,U0(p)>U(q).Then, define U ′ ∈A (Qn,ω) byU ′(p) =U0(p) if p ∈ P′U(p) if p ∈ Pn.Lastly, let T ′ be the element in Tb(Qn,ω) that satisfies U ′ ∈ T ′. Then,f (T ′) = T ′|Pn = T.Hence, as the choice of T was arbitrary, f is surjective.It follows that f is a bijection and, as f is a bijection, |Xn(T0)|= |Pn,ω|. Lastly, by Definition5.8, vn(i) = |Xn,i(T0)| for all 1≤ i≤ N. Therefore,|Pn,ω|= |Xn(T0)|=N∑i=1|Xn,i(T0)|=N∑i=1vn(i).Next, we prove a structural property of connected triples. It is a crucial lemma that will allowus to prove the main result of this chapter. Informally, the following lemma states that for58connected triples of finite posets, we can define a notion of union for two P-partitions in awell-defined manner.For the proof of the following lemma, recall that if U1,U2 ∈A (P,ω) for some finite poset Pand labelling ω of P, then U1 and U2 are order equivalent if U1 ≡U2.Lemma 5.12. Let Q be a finite poset, let (A,B,C) be a connected triple of Q, and let ωQbe a labelling of Q. Then for all T ′ ∈ Tb(A∪B,ωQ) and T ′′ ∈ Tb(B∪C,ωQ) such thatT ′|B = T ′′|B, there is a unique element T ∈ Tb(Q,ωQ) such that T |A∪B = T ′ and T |B∪C = T ′′.Example 5.13. Let Q be the twelve element poset depicted by the below diagram. Moreover,let A be the subposet of Q depicted by the cells that are filled with asterisks, let B be thesubposet of Q depicted by the cells that are filled with bullets, and let C be the subposet ofQ depicted by the blank cells. Moreover, let ωQ be a dual natural labelling of Q, where interms of tableaux the entries in the rows decrease from left to right, and the entries in thecolumns decrease from top to bottom.∗ ∗ ∗ •∗ • • •From how A, B, and C are defined, (A,B,C) is a connected triple of Q by Definition 4.1. LetT ′ be the element of Tb(A∪B,ωQ) that is depicted by the left-most diagram below, and letT ′′ be the element of Tb(B∪C,ωQ) that is depicted by the right-most diagram below.8 7 6 35 4 2 178 5 36 4 2 1Then T ′|B = T ′′|B for the following reason. The element T ′|B of Tb(B,ω) is depicted by59the left-most diagram shown below and the element T ′′|B of Tb(B,ω) is depicted by theright-most diagram shown below.34 2 178 5 3Hence, T ′|B = T ′′|B. So by Lemma 5.12, there exists a unique element T ∈ Tb(Q,ωQ) thatsatisfies T |A∪B = T ′ and T |B∪C = T ′′. This unique element T is depicted by the followingdiagram.12 11 10 79 8 5 36 4 2 1The reason that T |A∪B = T ′ and T |B∪C = T ′′ is because T |A∪B is depicted by the left-mostdiagram shown below, T |B∪C is depicted by the right-most diagram shown below, and theleft-most diagram shown below also depicts T ′.12 11 10 79 8 5 378 5 36 4 2 1Proof. It is enough to prove the following. Assume that there are elements U1,1,U1,2 ∈A (A∪B,ωQ) and elements U2,1,U2,2 ∈ A (B∪C,ωQ) such that U1,1 ≡ U1,2, U2,1 ≡ U2,2,U1,1|B ≡U2,1|B, and U1,2|B ≡U2,2|B. Then the following two statements hold.1. There exist elements U1 ∈ A (Q,ωQ) and U2 ∈ A (Q,ωQ) such that U1|A∪B ≡ U1,1,U1|B∪C ≡U2,1, U2|A∪B ≡U1,2, and U2|B∪C ≡U2,2.2. If U ′1 ∈A (Q,ωQ) and U ′2 ∈A (Q,ωQ) satisfy U ′1|A∪B≡U1,1, U ′1|B∪C ≡U2,1, U ′2|A∪B≡U1,2, and U ′2|B∪C ≡U2,2, then U ′1 ≡U ′2.60We first prove Statement 1. Since U1, j|B ≡U2, j|B for all 1 ≤ j ≤ 2, there are order embed-dings g1, j : U1, j(A∪B)→ N0 and g2, j : U2, j(B∪C)→ N0 such that, for all p ∈ B,g1, j(U1, j(p)) = g2, j(U2, j(p)).So for all 1≤ j ≤ 2, define U j : Q→ N0 byU j(p) =g1, j(U1, j(p)) if p ∈ A∪Bg2, j(U2, j(p)) if p ∈ B∪C.For all 1≤ j ≤ 2, the above map U j is well-defined because of the definition of g1, j and g2, j.Moreover, for all 1≤ j ≤ 2, the map U j satisfiesU j|A∪B = g1, j ◦U1, j ≡U1, j and U j|B∪C = g2, j ◦U2, j ≡U2, j.Hence, to prove Statement 1, it is enough to prove that U j ∈A (Q,ωQ) for all 1≤ j ≤ 2. Solet j ∈ {1,2}. To see that U j is order reversing as required by the definition of A (Q,ωQ) inChapter 3, suppose otherwise.Because U j|A∪B ∈A (A∪B,ωQ) and U j|B∪C ∈A (B∪C,ωQ), U j|A∪B and U j|B∪C are orderreversing.So, as we are supposing that U j is not order reversing, there are elements p ∈ A and q ∈Csuch that p < q but U j(p)<U j(q). By Property 2 of Definition 4.1, there exists an elementp′ ∈ B such that p< p′ < q in Q. As p, p′ ∈ A∪B, as p< p′ in A∪B, and as U j|A∪B is orderreversing, it follows that U j(p)≥U j(p′). Moreover, as p′,q∈B∪C, as p′< q in B∪C, and asU j|B∪C is order reversing, it follows that U j(p′)≥U j(q). But then, U j(p)≥U j(p′)≥U j(q),61which is contrary to the assumption that U j(p)<U j(q).So U j is order reversing. Suppose that U j /∈ A (Q,ωQ). Then there are elements p,q ∈ Qsuch that p< q in Q, ωQ(p)> ωQ(q), and U j(p) =U j(q). Because U j|A∪B ∈A (A∪B,ωQ)and U j|B∪C ∈A (B∪C,ωQ), it follows that p∈ A and q∈C. Since p∈ A and q∈C, Property2 of Definition 4.1 implies that there exists an element p′ ∈ B such that p< p′ < q in Q.If ωQ(p) ≤ ωQ(p′) and ωQ(p′) ≤ ωQ(q), then ωQ(p) ≤ ωQ(p′) ≤ ωQ(q), implying thatωQ(p)≤ωQ(q). But that is contrary to the assumption thatωQ(p)>ωQ(q). Hence, ωQ(p)>ωQ(p′) or ωQ(p′)>ωQ(q). So as p, p′ ∈ A∪B, p< p′ in A∪B, p′,q∈ B∪C, p′< q in B∪C,U j|A∪B ∈A (A∪B,ωQ), and U j|B∪C ∈A (B∪C,ωQ), it follows thatU j(p)>U j(p′)≥U j(q) or U j(p)≥U j(p′)>U j(q).But then, U j(p)>U j(q), which is contrary to the assumption that U j(p) =U j(q).Hence, Ui ∈A (Q,ωQ), and Statement 1 follows.To prove Statement 2, let U1,1, U1,2, U ′1, U1,2, U2,2, and U′2 be as described in the beginningof the proof, and suppose that U ′1 is not order equivalent to U′2. Because U′1|A∪B ≡U1,1 ≡U1,2 ≡U ′2|A∪B and because U ′1|B∪C ≡U2,1 ≡U2,2 ≡U ′2|B∪C, we have that U ′1|A∪B ≡U ′2|A∪Band U ′1|B∪C ≡U ′2|B∪C. So there are elements p,q ∈Q such that p ∈ A, q ∈C, and exactly oneof the following holds.• U ′1(p)<U ′1(q) and U ′2(p)>U ′2(q)• U ′1(p)>U ′1(q) and U ′2(p)<U ′2(q)• U ′1(p) =U ′1(q) and U ′2(p) 6=U ′2(q)62• U ′1(p) 6=U ′1(q) and U ′2(p) =U ′2(p)Suppose that U ′1(p) < U′1(q) and U′2(p) > U′2(q). Then, as U′1 and U′2 are order reversingmaps, it follows that p ‖ q in Q. But as (A,B,C) is a connected triple of Q, that violatesProperty 2 of Definition 4.1. Similarly, if U ′1(p)>U′1(q) and U′2(p)<U′2(q), then Property2 of Definition 4.1 would be violated. So without loss of generality, suppose that U ′1(p) =U ′1(q) and U′2(p) 6=U ′2(q).Since p∈A and q∈C, Property 2 of Definition 4.1 implies that there exists an element p′ ∈Bsuch that p < p′ < q in Q. Hence, as U ′1 is order reversing and as U′1(p) =U′1(q), U′1(p) =U ′1(p′) =U ′1(q). So as p, p′ ∈ A∪B and U ′1|A∪B ≡U ′2|A∪B, it follows that U ′2(p) =U ′2(p′).Similarly, as p′,q ∈ B∪C and U ′1|B∪C ≡U ′2|B∪C, it follows that U ′2(p′) =U ′2(q). But then,U ′2(p) =U′2(q), which is contrary to the assumption that U′2(p) 6=U ′2(q). Hence, Statement2 follows.Remark 5.14. Note that the converse of Lemma 5.12 is also true. If T ∈ Tb(Q,ω), then Tuniquely determines T |A∪B ∈ Tb(A∪B,ω) and T |B∪C ∈ Tb(B∪C,ω).In preparation for the main result of this chapter, we introduce the following technical def-inition. It defines a positive integer that depends on the periodic quadruple system beingconsidered.Definition 5.15. Let (Z,ω,pi,θ) be a periodic quadruple system and let S be an index shapeof (Z,ω,pi,θ). Then the minimum number for (Z,ω,pi,θ) and S is the smallest positiveinteger m such that if n ∈ N satisfies n≥ m, then for all p ∈ Z satisfying pi(p) = n+1, thereexists an element q ∈ θ n(S) such that q< p in Z and pi(q)≥ 1.63Remark 5.16. The minimum number of a periodic quadruple system always exists. Let(Z,ω,pi,θ) be a periodic quadruple system and let S be an index shape of (Z,ω,pi,θ). SinceS is finite, there is a positive integer n such that, for all p ∈ θ n(S), pi(p) ≥ 1. Moreover, Sconnects Z, so as θ is an order automorphism on Z, θ n(S) connects Z. Hence, by Property2 of Definition 4.1, it follows that for all p ∈ Z satisfying pi(p) = n+1 and p′ ∈ Z satisfyingpi(p′) ≤ 0, there exists an element q ∈ θ n(S) such that p′ < q < p. But as pi(q) ≥ 1 for allq∈ θ n(S), it follows from Definition 5.15 that the minimum number of (Z,ω,pi,θ) exists andis at most n.Example 5.17. If (Z,ω,pi,θ) is a periodic quadruple system built from a truncated shiftedshape such as the periodic quadruple system in Example 4.18, then there is an index shape Sof (Z,ω,pi,θ) such that the minimum number for (Z,ω,pi,θ) and S is 1. In particular, thereare such index shapes for periodic quadruple systems built from parallelogramic shapes suchas the one in Example 4.6. To see how to check that such index shapes exist, we observe thefollowing special case.Let (Z,ω,pi,θ) and S be as in Example 5.11. We explain why the minimum number m for(Z,ω,pi,θ) and S is 1. Consider the twelve cell diagram below.∗◦ ◦ ◦• • • •The above diagram depicts the poset pi−1([0,2]). Moreover, pi−1({0}) is represented by thefour cells in the top row of the diagram, θ(S) is depicted by the cells filled with an asteriskand the cells filled with circles, and pi−1({2}) is depicted by the cells filled with bullets.Set m = 1, and set n = m. From the above diagram, it can be seen that if p ∈ Z satisfiespi(p) = n+1 = 2, then p is represented by one of the cells filled with bullets. From the same64diagram, it can be seen that there exists an element q ∈ θ n(S) = θ(S), specifically one of thecells filled with a circle, such that q < p in Z and pi(q) ≥ 1. Hence, m = 1 is the minimumnumber of (Z,ω,pi,θ).Remark 5.18. Example 5.17 can be generalized to prove the following. If (Z,ω,pi,θ) is aperiodic quadruple system as described in Theorem 4.26, then there is an index shape S of(Z,ω,pi,θ) such that the minimum number for (Z,ω,pi,θ) and S is 1.We now prove the main result of this chapter by proving the existence of a certain matrixdifference equation. For the proof, recall the definitions of the sets Xn(T0) and Xn,i(T0) inDefinition 5.8.Theorem 5.19. Let (Z,ω,pi,θ) be a periodic quadruple system, let S be an index shape of(Z,ω,pi,θ), and let L be an indexing of Tb(S,ω). Moreover, let n′ be an admissible numberfor (Z,ω,pi,θ) and S, let T0 ∈ Tb(pi−1([n′,0]),ω), and let (vn)n=0,1,2,... be a sequence suchthat for all n ∈ N0, vn is the nth vector derived from (Z,ω,pi,θ), S, L, and T0. Lastly, let Mbe the tableau transfer matrix derived from (Z,ω,pi,θ), S, and L, and let m be the minimumnumber for (Z,ω,pi,θ) and S. Then for all n≥ m,vn+1 = M vn.Example 5.20. Let (Z,ω,pi,θ), S, L, T0 be as in Example 5.9 and Example 5.11. By Example5.17, the minimum number m for (Z,ω,pi,θ) and S is 1. So consider the 1st vector v1 derivedfrom (Z,ω,pi,θ), S, and L. As shown in Example 5.9,v1 =10 .65Next, let M be the tableau transfer matrix from Example 5.7. What this theorem allows us todo is to determine vn from M and v1 for any n≥ 1. For instance, we showed in Example 5.11thatv2 =32 .This vector can also be obtained from M and v1 as follows.v2 = Mv1 =3 42 310=32Proof. Let n ∈ N. Define Q = pi−1([n′,n+ 1]), C = pi−1({n+ 1}), B = θ n(S), and A =pi−1([n′,n])\B. Then (A,B,C) is a connected triple of Q. Note that A∪B = pi−1([n′,n]) andθ(B) = θ n+1(S).If T ∈ Xn+1(T0), then T |A∪B ∈ Tb(A∪B,ω) and T |B∪C ∈ Tb(B∪C,ω). Since T ∈ Xn+1(T0),Definition 5.8 implies that for all U ∈ T , p∈ pi−1([n′,0]), and q∈ pi−1([n+1]), U(p)>U(q).Hence, for all U ∈ T , p ∈ pi−1([n′,0]), and q ∈ pi−1([n+ 1]), U(p) >U(q), and it followsthat T |A∪B ∈ Xn(T0) and T |B∪C ∈ Tb(B∪C,ω) . As noted in Remark 5.14, T ∈ Xn+1(T0)uniquely determines T |A∪B and T |B∪C.Next, define the mapf : Xn+1(T0)→{(T ′′,T ′) ∈ Tb(B∪C,ω)×Xn(T0) : T ′′|B = T ′|B}byf (T ) = (T |B∪C,T |A∪B)for all T ∈ Xn+1(T0). By what we just showed, f is well-defined and injective. We will prove66that f is also a bijection. To that end, it is enough to show that f is surjective.Let T ′ ∈ Xn(T0), let T ′′ ∈ Tb(B∪C,ω), and assume that T ′|B = T ′′|B. Recall that Tb(Q,ω) =Tb(Q,ωQ), whereωQ is the labelling of Q such that ω|Q≡ωQ. Hence, by Lemma 5.12, thereis a unique element T ∈ Tb(Q,ω) such that T |A∪B = T ′ and T |B∪C = T ′′. So to prove that fis surjective, it is enough to prove that T ∈ Xn+1(T0).Let P′ = pi−1([n′,0]) and let P = pi−1([n+ 1]). Because T |A∪B = T ′ ∈ Xn(T0) and becauseP′ ⊆ A∪B, Definition 5.8 implies that T |P′ = T0. Hence, by Definition 5.8, it is enough toshow that for all U ∈ T , p ∈ P′, and q ∈ P, U(p)>U(q). To that end, let U ∈ T , let p ∈ P′,and let q ∈ P.If pi(q)≤ n, then p,q ∈ A∪B, implying, as T |A∪B ∈ Xn(T0), that U(p)>U(q) by Definition5.8 applied to T |A∪B. So assume without loss of generality that pi(q) = n+ 1. Becausen ≥ m, by hypothesis where m is the minimum number for (Z,ω,pi,θ) and S, Definition5.15 implies that there exists an element p′ ∈ θ n(S) such that p′ < q in Z and pi(p′)≥ 1. Inparticular, as p′ < q and U is order reversing, U(p′)≥U(q).Because B = θ n(S), p′ ∈ B. Moreover, T |A∪B ∈ Xn(T0) and p ∈ P′. Furthermore, by Defi-nition 5.8, U(p′′) >U(q′′) for all p′′ ∈ P′ and q′′ ∈ pi−1([n]). Lastly, p′ ∈ pi−1([n]) becausep′ ∈ θ n(S) and pi(p′)≥ 1. So as p ∈ P′ and p′ ∈ pi−1([n]), we have U(p)>U(p′). Hence,U(p)>U(p′)≥U(q),implying that U(p)>U(q). From this, it follows that T ∈ Xn+1(T0). Hence, f is a bijection.Whence, for all T2 ∈ Tb(S,ω), the number of elements T ∈ Xn+1(T0) satisfying T |θn+1(S) ≡θ67T2 is∑T1∈Tb(S,ω)M(T2,T1) |{T ∈ Xn(T0) : T |θn(S) ≡θ T1}| (5.1)for the following reasons.Since B = θ n(S), the fact that f is a bijection implies that the following is true for allT2 ∈ Tb(S,ω). If g is the restriction of f to the set of elements T ∈ Xn+1(T0) satisfyingT |θn+1(S) ≡θ T2, then g is injective and the range of g is the set of ordered pairs (T ′′,T ′) ∈Tb(B∪C,ω)×Xn(T0) satisfying T ′′|θn+1(S) ≡θ T2 and T ′′|θn(S) = T ′|θn(S).Moreover, as θ is an order automorphism on Z, asB∪C = θ n(S)∪pi−1({n+1}) = θ n+1(θ−1(S)∪pi−1({0})),as θ n(S) = θ n+1(θ−1(S)), and as M is the tableau transfer matrix derived from (Z,ω,pi,θ),S and L, Definition 5.6 implies that for all T1,T2 ∈ Tb(S,ω), the number of elements T ′′ ∈Tb(B∪C,ω) satisfying T ′′|θn+1(S) ≡θ T2 and T ′′|θn(S) ≡θ T1 is M(T2,T1).Hence, the number of elements T ∈ Xn+1(T0) satisfying T |θn+1(S) ≡θ T2 is given by Expres-sion 5.1.Lastly, by Definition 5.8,|Xn,L(T1)(T0)|= |{T ∈ Xn(T0) : T |θn(S) ≡θ T1}|for all T1 ∈ Tb(S,ω), and|Xn+1,L(T2)(T0)|= |{T ∈ Xn+1(T0) : T |θn+1(S) ≡θ T2}|68for all T2 ∈ Tb(S,ω).Therefore, for all T2 ∈ Tb(S,ω), Definition 5.8 implies thatvn+1(L(T2)) = |Xn+1,L(T2)(T0)|= |{T ∈ Xn+1(T0) : T |θn+1(S) ≡θ T2}|= ∑T1∈Tb(S,ω)M(T2,T1) |{T ∈ Xn(T0) : T |θn(S) ≡θ T1}|= ∑T1∈Tb(S,ω)M(T2,T1) |Xn,L(T1)(T0)|= ∑T1∈Tb(S,ω)M(T2,T1) vn(L(T1)).From this, the theorem follows from the definition of matrix multiplication.69Chapter 6Results relating to the marriage conditionIn this chapter, we consider families of sets that satisfy Hall’s marriage condition. We intro-duce a generalized notion of hook-lengths for such families. Then, we establish an existenceresult based on such generalized hook-lengths that gives a new characterization of marriageproblems with unique solutions. Afterwards, we prove a corollary that complements thisexistence result.Definition 6.1. (Hall, [21]) Let n ∈ N, and let F be a finite family of subsets of [n]. Then atransversal ofF is an injective function t :F → [n] such that t(F) ∈ F for all F ∈F .Informally, a transversal maps each F to one of its elements.Definition 6.2. (Hall, [21]) Let n ∈N, and letF be a finite family of subsets of [n]. ThenFsatisfies the marriage condition if for all subfamiliesF ′ ofF ,|F ′| ≤∣∣∣∣ ⋃F∈F ′F∣∣∣∣.70Example 6.3. A simple example illustrating both Definition 6.1 and Definition 6.2 is asfollows. Let n = 5, and letF = {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5}}.ThenF satisfies the marriage condition. For example, ifF ′ is the subfamily ofF defined byF ′= {{1},{1,2,3}}, then |F ′|= 2 and |{1}∪{1,2,3}|= 3. The map t :F →{1,2,3,4,5}defined by t([k]) = k for all 1≤ k ≤ 5 is a transversal ofF .One could interpret the above example as evidence to the possibility that a family of sets of[n] has a transversal if and only if it satisfies the marriage condition. It turns out that this isalways true. The following is known as Hall’s Marriage Theorem.Theorem 6.4. (Hall, [21]) Let n ∈ N, and let F be a family of non-empty subsets of [n].ThenF has a transversal if and only ifF satisfies the marriage condition.In order to use the families of sets in Hall’s Marriage Theorem, we will define more structureon the objects being considered. Definition 6.5 represents the local conditions and general-ized hook-lengths mentioned in Chapter 1; how this relates to hook-lengths will becomeclear in the next chapter. Recall the notation we use for functions in Chapter 2.Definition 6.5. Let n ∈ Z, let F be a family of non-empty subsets of [n], and let t be atransversal of F . Then a configuration f of t is a function f : [n]→ N such that for allF ∈F ,f (t(F))≤ |F |.Moreover, a permutation σ : [n]→ [n] satisfies f if the following holds for all F ∈F . Thepositive integer σ(t(F)) is the kth smallest element of σ(F), where k = f (t(F)).71Example 6.6. Let n = 5. Moreover let F and let t :F → [n] be as defined in Example 6.3.Furthermore, let Fi = [i] for all 1 ≤ i ≤ 5 so t(Fi) = i. Lastly, let f : [n]→ N be defined byf (1) = 1, f (2) = 1, f (3) = 2, f (4) = 4, and f (5) = 2. The map f is a configuration oft. For instance, since F3 = {1,2,3}, t(F3) = 3, f (t(F3)) = 2, |F3| = 3, and f (t(F3)) ≤ |F3|.Similarly, f (t(F1)) = 1 ≤ 1 = |F1|, f (t(F2)) = 1 ≤ 2 = |F2|, f (t(F4)) = 4 ≤ 4 = |F4|, andf (t(F5)) = 2≤ 5 = |F5|.Moreover, the permutation σ : [n]→ [n] defined by σ = 41352 satisfies f . For example, con-sider F3 = {1,2,3}. As before, t(F3) = 3 and f (t(F3)) = 2, so k = 2. Moreover, σ(t(F3)) =σ(3) = 3. Lastly, σ(F3) = {σ(1),σ(2),σ(3)} = {1,3,4}, and σ(t(F3)) = 3 is the secondsmallest element of σ(F3). Similarly, for F1, k = 1, σ(t(F1)) = 1, and σ(F1) = {4}; forF2, k = 1, σ(t(F2)) = 1, and σ(F2) = {1,4}; for F4, k = 4, σ(t(F4)) = 5, and σ(F4) ={1,3,4,5}; and for F5, k = 2, σ(t(F5)) = 2, and σ(F5) = {1,2,3,4,5}.Configurations satisfy the following property, whose usefulness will become more apparentin the next chapter.Lemma 6.7. Let n ∈ N, and let F be a family of subsets of [n] that has a transversal t :F → [n] such that t is surjective. Then every permutation σ : [n]→ [n] satisfies exactly oneconfiguration f of t.Proof. Let σ : [n]→ [n] be a permutation. Then σ satisfies the configuration f of t defined byletting, for all F ∈F , f (t(F)) = k where σ(t(F)) is the kth smallest element of the set σ(F).Now, suppose that σ satisfies more than one configuration of t. Then, let f1 and f2 be twodistinct configurations of t. Because f1 6= f2 and because t is surjective, there is an elementF ∈ F such that f1(t(F)) 6= f2(t(F)). So write k1 = f1(t(F)) and write k2 = f2(t(F)).Since σ satisfies f1, Definition 6.5 implies that σ(t(F)) is the kth1 smallest element of σ(F).72Moreover, since σ satisfies f2, Definition 6.5 implies that σ(t(F)) is the kth2 smallest elementof σ(F). However, this is impossible because k1 = f1(t(F)) 6= f2(t(F)) = k2.Now, we define the following stronger form of the marriage condition that was defined byChang [10] and Hirst and Hughes in [24].Definition 6.8. (cf. ([24], Theorem 4)) Let n ∈ N, let F be a finite family of subsets of [n],and write m = |F |. Then F is shellable if there exists a bijection σF : [m]→F such thatfor all k ∈ [m], ∣∣∣∣ k⋃i=1σF (i)∣∣∣∣= k. (6.1)Informally, σF maps each k to a subset, such that the union of the first k subsets has cardi-nality k.Remark 6.9. Shellable families of sets are connected to Theorem 6.4. Chang ([10], Theorem1) noted that a simple consequence of Hall Jr.’s work ([22], Theorem 2) is that a finite familyF of subsets of [n] has exactly one transversal if and only if F is shellable. Later on, Hirstand Hughes showed that this can be proved using a subsystem of second order arithmeticcalled RCA0 [24] and proved an extension of this result involving infinite families of finitesets in the context of reverse mathematics. From the aforementioned characterization offinite families of subsets of [n] that have exactly one transversal, we have, by Theorem 6.4,that all shellable families satisfy the marriage condition.Remark 6.10. The term shellable is not used in [10], [22], and [24]. However, we use thisterminology because Definition 6.8 resembles the definition of a shellable pure d-dimensionalsimplicial complex ([8], Appendix A2.4, Definition A2.4.1). The differences between Defi-nition 6.8 and Definition A2.4.1 are as follows. The sets in Definition 6.8 do not requireadditional conditions on the cardinalities of the members of F . Also, in Definition A2.4.1,73the requirement of the existence of a bijection σF : [m]→F as described in Definition 6.8is relaxed to requiring the existence of a certain bijection from a subset of [m] to a subset ofF .Remark 6.11. When describing the members of a shellable family, we will use a total order-ing on the members of that family. Specifically, let F be a shellable family of subsets of [n]and let m= |F |. By Definition 6.8, there exists a bijection σF : [m]→F such that Equation6.1 is satisfied for all k ∈ [m]. From this bijection σF , define a total ordering <F on themembers of F by defining, for all members F ′,F ′′ ∈F , F ′ <F F ′′ if σ−1F (F ′′)< σ−1F (F ′).The shelling order of a shellable complex from ([8], Appendix A2.4, Definition A2.4.1) is avariant of this total ordering.Example 6.12. Let n ∈ N, and define the following finite family of sets.F = {[i] : i ∈ [n]}ThenF is shellable for the following reason. Firstly, |F |= n, so the variable m in Definition6.8 satisfies m = n. Next, define the bijection σF : [n]→F be letting σF (k) = [k] for allk ∈ [n]. Then for all k ∈ [n], ∣∣∣∣ k⋃i=1σF (i)∣∣∣∣= |[k]|= k.So asF and σF satisfy Equation 6.1,F is shellable.Example 6.13. If n ∈ N and n≥ 3, then a family of subsets of [n] that satisfies the marriagecondition but is not shellable isF = {[n]\{k} : k ∈ [n]}.This family satisfies the marriage condition because for any subfamilyF ′ ofF with at least74one member, ∣∣∣∣ ⋃F∈F ′F∣∣∣∣ =n−1 if |F ′|= 1n else.However, if F is shellable, where m = |F |, then the following holds. By Definition 6.8and Equation 6.1, there exists a bijection σF : [m]→ F such that |σF (1)| = 1. So asσF (1) ∈ F , it follows that F has a member whose cardinality is one. However, for allF ∈F , |F |= n−1≥ 2. So it follows thatF is not shellable.Now, we prove the main result of this chapter. It is a partial converse of Lemma 6.7.Theorem 6.14. Let n∈N. Moreover, letF be a family of subsets of [n] such thatF satisfiesthe marriage condition, let t be a transversal of F , and assume that |F | = n. Then Fis shellable if and only if the following holds. For all configurations f of t, there exists apermutation σ : [n]→ [n] that satisfies f .Example 6.15. Let n = 3. Moreover, let F = {{1,2,3},{1,3}}, and let t :F → [n] be de-fined by t({1,2,3}) = 1 and t({1,3}) = 3. The family F is not shellable since we cannotfind a bijection σF : [m]→ F such that |σF (1)| = 1. Now, let f : [n]→ N be the con-figuration of t defined by f (1) = 1, f (2) = 2, and f (3) = 1. It is a configuration of t sincef (t({1,2,3})) = f (1) = 1≤ 3= |{1,2,3}| and f (t({1,3})) = f (3) = 1≤ 2= |{1,3}|. Thenno permutation σ : [n]→ [n] satisfies f as follows.Suppose that there is a permutation σ0 : [n]→ [n] that satisfies f . First, consider the elementF1 = {1,2,3} of F . Then k = f (t(F1)) = f (1) = 1. Moreover, σ0(F1) = {1,2,3}. So asσ0 satisfies f , σ0(t(F1)) = σ0(1) is the smallest element of {1,2,3}. Hence, σ0(1) = 1.Next, consider the element F2 = {1,3} of F . Then k = f (t(F2)) = f (3) = 1. So as σ0satisfies f , σ0(t(F2)) = σ0(3) is the smallest element of σ0(F2) = {σ0(1),σ0(3)}. But then,75σ0(3)< σ0(1), contradicting the fact that σ0(1) = 1.Proof. First assume that for all configurations f of t, there exists a permutation σ : [n]→[n] that satisfies f . If n = 1, then the only family of {1} with a transversal is the familyF = {{1}}, which is shellable. So assume without loss of generality that n ≥ 2. Considerthe configuration f1 of t defined by f1(t(F)) = |F | for all F ∈ F . By assumption, thereexists a permutation σ ′ : [n]→ [n] that satisfies f1. Moreover, let k ∈ [n−1], and assume thatwe can fix an ordering F = {F ′i : i ∈ [n]} of F so that the following holds for all integers0≤ j ≤ k−1. ∣∣∣∣n− j⋃i=1F ′i∣∣∣∣= n− j (6.2)Note that Equation 6.2 holds if k = 1 because the fact that F has a transversal implies that⋃F∈F F = [n].Next, let 1≤ s≤ n− k+1 satisfyσ ′(t(F ′s )) = max1≤ j≤n−k+1σ ′(t(F ′j)). (6.3)Suppose that there exists an element j ∈ [n] such that 1≤ j≤ n−k+1, j 6= s, and t(F ′s )∈ F ′j .By Equation 6.3, σ ′(t(F ′j)) ≤ σ ′(t(F ′s )). So as t(F ′s ) ∈ F ′j and t(F ′s ) 6= t(F ′j), it follows thatfor some 1 ≤ ` ≤ |F ′j | − 1, σ ′(t(F ′j)) is an `th smallest element of σ ′(F ′j). But then, asf1(t(F ′j)) = |F ′j |, σ ′ does not satisfy f1, contradicting the assumption that σ ′ satisfies f1.Hence, t(F ′s ) /∈ F ′i for all 1 ≤ i ≤ n− k+ 1 satisfying i 6= s. In particular, fix an orderingF = {F ′′i : i ∈ [n]} of F so that F ′′i = F ′i if i > n− k+ 1 and F ′′n−k+1 = F ′s , where s is asdescribed in the above paragraph. From Equation 6.2, this ordering of the members of F76satisfies the following equation for all integers 0≤ j ≤ k.∣∣∣∣n− j⋃i=1F ′′i∣∣∣∣= n− jAs the choice of k∈ [n−1] is arbitrary, it follows that there exists an orderingF = {F1,F2, . . . ,Fn}ofF such that ∣∣∣∣ k⋃i=1Fi∣∣∣∣= kfor all 1≤ k ≤ n. Hence, F satisfies Equation 1 of Definition 6.8. So, by Definition 6.8, Fis shellable.Next, assume that F is shellable. Because F is shellable, we will use the total ordering asdescribed in Remark 6.11 to describe the members of this family. We proceed by inductionon n. If n = 1, then the only family of subsets of {1} with a transversal is the family F ={{1}}. Moreover, with t being the transversal of F defined by mapping {1} to 1, the onlyconfiguration f that satisfies t is the function f : {1} → N defined by f (1) = 1, and anypermutation σ : {1}→ {1} satisfies f .So let n≥ 2 and assume that the induction hypothesis holds. Let t be a transversal ofF andlet f be a configuration of t. Because F is shellable, Definition 6.8 and Remark 6.11 implythat there is an element n′ ∈ [n] such that, for all F ∈F , n′ /∈ F or t(F) = n′. So without lossof generality, assume that n′ = n. LetF ′ be the family of sets defined byF ′ = {F ∈F : t(F) 6= n}.As n /∈ F for all F ∈F such that t(F) 6= n,F ′ is a family of subsets of [n−1]. Next, definet ′ :F ′→ [n−1] by letting t ′(F) = t(F) for all F ∈F ′. Moreover, because t is a transversal77of F , t ′ is a transversal of F ′. By Definition 6.8 and the choice of n = n′, F ′ is shellablefor the following reason.Define the bijection σF ′ : [n−1]→F ′ byσF ′(k) = σF (k)for all k∈ [n−1]. Because σF satisfies Equation 6.1 of Definition 6.8, σF ′ satisfies Equation6.1 of Definition 6.8. Hence, F ′ is shellable. So by the induction hypothesis, there exists apermutation σ ′ : [n−1]→ [n−1] that satisfies all configurations f ′ of t ′.Let m = f (n), and let Fσ be the element of F such that t(Fσ ) = n. There is an orderembedding κ : [n− 1]→ [n] such that the element k ∈ [n]\κ([n− 1]) is the mth smallestelement of κ(Fσ ). With κ defined, define σ : [n]→ [n] as follows. Let σ(n) be the elementof [n] that is not in κ([n−1]), and, for all k ∈ [n−1], let σ(k) = κ(σ ′(k)). Because n = n′and n′ ∈ F for exactly one element F ∈F , σ satisfies f . From this, the theorem follows.Remark 6.16. A familyF of subsets of [n] such that |⋃F∈F F |= |F |= n is called a criticalblock in [22]. In [22], Hall Jr. used this notion as a very important ingredient in extendingHall’s Marriage Theorem to infinite families of finite sets.As a corollary, we show the following.Corollary 6.17. Let n ∈N. Moreover, letF be a family of subsets of [n] that has a transver-sal, let t be a transversal of F , and assume that |F | = n. Then every configuration f of tis satisfied by some permutation σ : [n]→ [n] if and only if the following holds. The con-figuration f0 of t defined by f0(t(F)) = 1 for all F ∈ F is satisfied by some permutationσ0 : [n]→ [n].78Example 6.18. The family of sets in Example 6.15 is, as shown in that example, a familywhere the configuration f0 as defined in Corollary 6.17 is not satisfied by any permutation.Proof. By Theorem 6.4,F has a transversal if and only ifF satisfies the marriage condition.So by Theorem 6.14, it is enough to prove thatF is shellable if and only if the configurationf0 of t as described in the corollary is satisfied by some permutation σ0 : [n]→ [n].We first show that if F is not shellable, then the configuration f0 is not satisfied by anypermutation. Let f1 be the configuration of t defined by f1(t(F)) = |F | for all F ∈F . Thefirst part of the proof of Theorem 6.14 proves that if f1 is satisfied by some permutationσ : [n] → [n], then F is shellable. So as F is not shellable, f1 is not satisfied by anypermutation σ : [n]→ [n]. Moreover, a permutation σ : [n]→ [n] satisfies f0 if and only ifthe permutation σ ′ : [n]→ [n] defined, for all k ∈ [n], byσ ′(k) = n−σ(k)+1satisfies f1. Hence, it follows from the above that ifF is not shellable, then f0 is not satisfiedby any permutation.So assume thatF is shellable, and use a total order to describe the members ofF by lettingσF : [n]→F be as described in Definition 6.8. Define the permutation σ0 : [n]→ [n] byhavingσ0(t(σF (k)) = n− k+1for all k ∈ [n]. This permutation satisfies f0 because for all k ∈ [n], σ0(t(σF (k))) = n−k+1is the smallest element of σ0(σF (k)). This completes the proof of the corollary.79Chapter 7Applications to skew tableauxIn this chapter, we describe how the results in the previous chapter can be applied to skewshapes. Specifically, we introduce a generalization of standard skew tableaux and Edelmanand Greene’s balanced tableaux, then prove some existence results about these generalizedstructures as described in Chapter 1 by using the characterization of the stronger form of themarriage condition. Afterwards, we briefly indicate other ways in which we can apply theresults of Chapter 7.Definition 7.1. (cf. [30], p.7 and [41], Definition 2.1.1, Definition 3.7.1) Let λ =(λ1,λ2, . . . ,λ`)and µ = (µ1,µ2, . . . ,µ`′) be partitions of positive integers such that `′ ≤ ` and µi ≤ λi for all1≤ i≤ `′. Moreover, letX =⋃`i=1λi⋃j=µi+1{(i, j)}.Lastly, let X ′⊂N2 be such that X ′=X+v for some v∈Z2, X ′−(0,1)*N2, and X ′−(1,0)*N2. Then define the skew shape λ/µ to be the Young diagram that is equal to X ′.If µ = /0 is the empty partition, then for any partition λ of a positive integer, define the skew80shape λ/µ to be the Young diagram that is equal to⋃`i=1λi⋃j=1{(i, j)}and call this Young diagram the Young diagram of λ . We also call the Young diagram of λa normal shape. Lastly, if λ = /0 is the empty partition, then we define the Young diagram ofλ to be the empty set.Example 7.2. Let λ = (4,2,1,1), and consider the Young diagram of λ . By Definition 7.1,row 1 of this diagram consists of λ1 = 4 cells, row 2 of this diagram consists of λ2 = 2 cells,row 3 of this diagram consists of λ3 = 1 cell, and row 4 of diagram consists of λ4 = 1 cell.Hence, the Young diagram is as follows.Remark 7.3. Let λ be a partition of a non-negative integer. Then we will refer to the Youngdiagram of λ as λ . In particular, we can speak of cells of λ or even rows of λ . Since we willdo this, we will say things such as “let λ be a normal shape” when mentioning the Youngdiagram of λ .Example 7.4. Let λ = (4,3,2,2) and µ = (2,2,1). Then `= 4, `′ = 3, and for all 1≤ i≤ `′,µi ≤ λi. Hence, the skew shape λ/µ is well-defined. The set X as described in Definition7.1 is obtained from the Young diagram of λ by deleting the µ1 = 2 left-most cells of row 1of λ , the µ2 = 2 left-most cells of row 2 of λ , and, as µ3 = 1, the left-most cell of row 3 ofλ . Because this set X satisfies X − (0,1) * N2 and X − (1,0) * N2, it follows that X ′ = X.81Hence, by Definition 7.1, the skew shape λ/µ is the following Young diagram.Remark 7.5. When mentioning skew shapes λ/µ , we simply say “let λ/µ be a skew shape”without explicitly mentioning that λ and µ are partitions that satisfy the conditions describedin Definition 7.1.Definition 7.6. (Folklore, cf. [30, 41, 45]) Let λ/µ be a skew shape consisting of n cells.Then a standard skew tableau of shape λ/µ is a bijective filling of the cells of λ/µ withnumbers from [n] such that entries increase along every row from left to right and entriesincrease along every column from top to bottom. Moreover, a reverse standard skew tableauof shape λ/µ is a bijective filling of the cells of λ/µ such that the entries decrease alongevery row from left to right and entries decrease along every column from top to bottom. Ifµ = /0, then a standard skew tableau of shape λ/µ is a standard Young tableau of shape λand a reverse standard skew tableau of shape λ/µ is a standard reverse tableau of shape λ .Example 7.7. Consider the skew shape λ/µ from Example 7.4. An example of a standardskew tableau of shape λ/µ is the following.1 4253 6To see that the above is a standard skew tableau, note that the entries, 1 and 4, in row 1 ofthis tableau are increasing from left to right, that the entries 5 and 6, in column 2 of thistableau are increasing from top to bottom, and so on. An example of a reverse standard skew82tableau of shape λ/µ is the following.6 1453 2The above is a reverse standard skew tableau since the entries, 6 and 4, in column 3 of thistableau are decreasing from top to bottom, the entries, 3 and 2, in row 4 of this tableau aredecreasing from left to right, and so on.When describing families of sets, we will replace [n] in the last chapter with the set of cellsof λ/µ . Moreover, in place of the permutations σ : [n]→ [n], we define generalized standardskew tableaux.Definition 7.8. (cf. [41], Definition 2.1.3) Let λ/µ be a skew shape with n cells. Then ageneralized standard skew tableau of shape λ/µ is a bijective filling of the cells of λ/µ withnumbers from [n].Example 7.9. If λ = (4,3,1) and µ = (2), then an example of a generalized skew tableau ofshape λ/µ is as follows.3 56 1 24Definition 7.10. ([41]) Let λ/µ be a skew shape. For any cell (i, j) in λ/µ , define thecorresponding hook H(i, j) and hook-length h(i, j) as follows:• H(i, j) = {(i′, j) ∈ λ/µ : i′ ≥ i}∪{(i, j′) ∈ λ/µ : j′ ≥ j},• h(i, j) = |H(i, j)|.83Example 7.11. Consider the following skew shape λ/µ , where λ = (5,4,3,3) and µ =(2,2,1). Moreover, let r be the cell of λ/µ depicted below that is filled with a bullet. ThenHr consists of the cells that are filled with asterisks or bullets, and hr = 4.• ∗∗∗Let λ be a normal shape. Then an inner corner of λ ([41], Definition 2.8.1) is a cell r ∈ λsuch that deleting r from λ results in another normal shape. With this definition in mind, letλ/µ be a skew shape with n cells, and consider the family of sets defined byF = {Hr : r ∈λ/µ}. Then F is shellable. To see this, let r1,r2, . . . ,rn be a sequence of cells in λ/µ thatis obtained as follows.• Let r1 be an inner corner of λ .• If 1≤ k < n and if r1, r2, . . . , rk have already been defined, then let λ (k) be the Youngdiagram that results from deleting cells r1, r2, . . . , and rk from λ , and let rk+1 be aninner corner of λ (k).Lastly, let λ (n) = µ . Define σF : [n]→ F by letting σF (k) = Hrk for all k ∈ [n]. Thebijection σF satisfies Equation 6.1 because, for all k ∈ [n], λ (k) has n− k cells,λ (k) ∪k⋃i=1Hri = λ/µ, (7.1)andλ (k) ∩k⋃i=1Hri = /0. (7.2)84Hence, F is shellable by Definition 6.8. In particular, by Remark 6.9, F has a uniquetransversal. The unique transversal t :F → λ/µ ofF is given by t(Hr) = r for all r ∈ λ/µ .Example 7.12. Let λ = (4,2,2) and let µ = (1). Next, letF = {Hr : r ∈ λ/µ}. We illustratewhy F is shellable. The normal shape λ is depicted below and all inner corners of λ arefilled with bullets.••Pick the inner corner r1 = (3,2) of λ . Then the normal shape λ (1) is depicted below and allinner corners of λ (1) are filled with bullets•••and we can pick the inner corner r2 = (1,4) of λ (1). Continuing in this way, one possibilityis the following sequence of cells in λ/µ depicted below.r6 r5 r2r7 r3r4 r1In particular, r3 = (2,2), r4 = (3,1), r5 = (1,3), r6 = (1,2), and r7 = (2,1). Now, define σF :{1,2, . . . ,7}→F so that σF (1) =H(3,2), σF (2) =H(1,4), σF (3) =H(2,2), σF (4) =H(3,1),σF (5) = H(1,3), σF (6) = H(1,2), and σF (7) = H(2,1). This bijection satisfies Equation 7.1and Equation 7.2. Hence,F is shellable.Edelman and Greene introduced the following variant of standard Young tableaux.85Definition 7.13. (Edelman and Greene, [13]) Let λ be a normal shape containing n cells.Then a balanced tableau of shape λ is a bijective filling of the cells of λ with numbersfrom [n] such that if (i, j) ∈ λ and if i′ is the largest positive integer such that (i′, j) ∈ λ , ifk = i′− i+1, and if Si, j is the set of entries m such that m is contained in a cell in H(i, j), thenthe entry in cell (i, j) of λ is the kth smallest entry of Si, j.Example 7.14. Let λ = (4,3,2). Then a balanced tableau of shape λ is as follows.4 5 8 36 7 91 2For instance, let i = 2 and j = 1. Then the entry contained in cell (i, j) of λ is 6. More-over, the largest integer i′ such that (i′, j) ∈ λ is 3, k = i′− i+ 1 = 3− 2+ 1 = 2, H(i, j) ={(2,1),(2,2),(2,3),(3,1)} and Si, j, the set of entries m of this tableau such that m is con-tained in a cell in H(i, j), equals {1,6,7,9}. Hence, the kth smallest entry of Si, j is 6, which isthe entry in cell (2,1) of the above tableau.In order to generalize standard skew tableaux, reverse standard skew tableaux, and balancedtableaux, we introduce the following special case of configurations from Definition 6.5.Definition 7.15. Let λ/µ be a skew shape. A configuration of λ/µ is a function f : λ/µ→Nfrom the cells of λ/µ to the positive integers so that if r ∈ λ/µ , then f (r)∈N and f (r)≤ hr.Remark 7.16. We say that f is a configuration of λ/µ rather than say that f is a con-figuration of the transversal t of the set F = {Hr : r ∈ λ/µ} defined by t(Hr) = r for allr ∈ λ/µ .Example 7.17. Consider the skew shape λ/µ where λ = (3,2,1) and µ = (1). We denoteconfigurations f of λ/µ by filling, for all r ∈ λ/µ , cell r with the number f (r). For instance,three configurations of λ/µ are the following.861 11 112 12 113 13 11Now, we define the special case of the notion of satisfaction from Definition 6.5.Definition 7.18. Let T be a generalized standard skew tableau of shape λ/µ and let f be aconfiguration of λ/µ . Then T satisfies f if for all cells r ∈ λ/µ , the entry in cell r of T isthe kth smallest, where k = f (r), entry in the set of entries of T that are located in the hookHr.In particular, a standard skew tableau of shape λ/µ is precisely a generalized standard skewtableau of shape λ/µ that satisfies the configuration f0 of λ/µ defined by f0(r) = 1 forall r ∈ λ/µ , and a reverse standard skew tableau of shape λ/µ is precisely a generalizedstandard skew tableau of shape λ/µ that satisfies the configuration f1 of λ/µ defined byf1(r) = hr for all r ∈ λ/µ . We will see examples of this in Example 7.19.Moreover, if λ is a normal shape, then let f be the configuration of λ such that, for all(i, j) ∈ λ , if i′ is the largest positive integer such that (i′, j) ∈ λ , then f ((i, j)) = i′− i+ 1.So any tableau T of shape λ is balanced if and only if T satisfies f . This characterization ofbalanced tableaux was used in [13] as the definition of balanced tableaux; the special caseof Definition 7.15 for normal shapes also appears in [13] under a different name. Namely,Edelman and Greene call f (r) the hook rank of r. However, they only use hook ranks todefine balanced tableaux. In this thesis, we have a very different emphasis as we focus onproperties of the configurations themselves.Example 7.19. Consider the skew shape λ/µ from and the three configurations of λ/µ fromExample 7.17. The generalized standard skew tableaux that satisfy the leftmost configurationdepicted in Example 7.17 are precisely the standard skew tableaux of shape λ/µ . Moreover,87the generalized standard skew tableaux that satisfy the rightmost configuration depicted inExample 7.17 are precisely the reverse standard skew tableaux of shape λ/µ . Furthermore,four examples of generalized standard skew tableaux that satisfy the middle configurationdepicted in Example 7.17 are displayed below.4 52 312 14 354 23 513 24 51Definition 7.20. Let λ/µ be a skew shape and h be a configuration of λ/µ . Then we writeN(h) to denote the number of generalized standard skew tableaux of shape λ/µ that satisfyh.Corollary 7.21. Let λ/µ be a skew shape. Then the number of configurations f of λ/µ suchthat N( f )> 0 is∏r∈λ/µhr .Proof. There are ∏r∈λ/µ hr configurations f of λ/µ since f (r) ≤ hr for every r ∈ λ/µ .So, since {Hr : r ∈ λ/µ} is a shellable family of subsets of the set of cells of λ/µ by thediscussion after Example 7.11, Theorem 6.14 implies that N( f )> 0 for all configurations fof λ/µ . From this, the corollary follows.A well-known formula is the hook-length formula, first proved by Frame, Robinson, andThrall [16]. It is as follows. If λ is a normal shape with n cells, then the number of standardYoung tableaux of shape λ equalsn!∏r∈λ hr.Moreover, the above formula was also proved by Edelman and Greene to equal to the numberof balanced tableaux of shape λ [13]. In our context, we will show that the above formula88also has interesting connections to the configurations that we are investigating.Corollary 7.21 has the following consequence.Theorem 7.22. Let λ/µ be a skew shape with n cells, and let X(λ/µ) denote the set ofconfigurations of λ/µ . Moreover, let N be the number of configurations f of λ/µ such thatN( f )> 0. Then,1N ∑f∈X(λ/µ)N( f ) =n!∏r∈λ/µ hr.Example 7.23. Let λ/µ = (4,3,2)/(2,1). Then1N ∑f∈X(λ/µ)N( f ) =n!∏r∈λ/µ hr=6!1 ·3 ·1 ·3 ·1 ·2 = 40.The hook-lengths are represented with the following diagram.3 13 12 1Proof. Every generalized standard skew tableau of shape λ/µ satisfies exactly one configu-ration of λ/µ by Lemma 6.7, so by Definition 7.20 and the fact that there are n! generalizedstandard skew tableaux of shape λ/µ ,∑f∈X(λ/µ)N( f ) = n!.Moreover, by Corollary 7.21,N = ∏r∈λ/µhr.From this, the theorem follows.89Lastly, we note that a special case of our work has also been considered in the literature byViard. We derived our work independently of Viard.Remark 7.24. Consider a finite subset S of N2. Next, for all r = (i, j) ∈ S, define Fr ={(i1, j) ∈ S : i1 ≥ i}∪ {(i, j1) : j1 ≥ j}, and define F = {Fr : r ∈ S}. This construction isrelated to the tools we used in Chapter 7 for the following reason. By using the same ex-planation as the one we gave for why {Hr : r ∈ λ/µ} is shellable, we observe that F isshellable and that its unique transversal is defined by t(Fr) = r for all r ∈ S.LetF and t be as described in the above paragraph. Viard [50, 51] considered objects thatare equivalent to configurations of t and permutations that satisfy such configurations. Viard[50, 51] asserted that he has established one direction of a special case of Theorem 6.14 byclaiming to have proved a statement equivalent to asserting that all configurations f of t aresatisfied by at least one permutation σ : S→ S. In particular, using his claim, he derivestwo consequences that imply Corollary 7.21 and Theorem 7.22.There are two versions of hisarguments (a less general version in [50] and a more general version in [51]), both versionsare different from our proof of Theorem 6.14.90Chapter 8ConclusionIn this thesis, we proved that the number of periodic P-partitions can be analysed with thehomogeneous first-order matrix difference equation in Theorem 5.19.The case of Theorem 5.19 when the labelling ω is dual-natural can be applied to the fol-lowing. As indicated by Example 4.6, Theorem 5.19 can be applied to bijective fillings ofthe parallelogramic shapes considered by Lo´pez et.al. [27], by Sun [47], and by Tewariand van Willigenburg [49]. Moreover, as indicated in Example 4.18, Theorem 5.19 can beapplied to bijective fillings of certain truncated shifted shapes. This would add to what isknown about enumerating bijective fillings on truncated shifted shapes from Adin, King,and Roichman [1, 3] and from Panova [38].The case of Theorem 5.19 when the labelling ω is a generalized Schur labelling can be ap-plied to the problem of enumerating semistandard tableaux. The problem of enumeratingtableaux known as semi-standard tableaux is, in general, far from solved [45]. For semi-standard tableaux on partition shapes, the number of such numbers are called Kostka num-91bers. These numbers are related to Specht modules and have several implications in algebraiccombinatorics [41, 45].Moreover, in this thesis, we gave a new characterization of shellable families in Theorem6.14 by generalizing the notion of standard Young tableaux and Edelman and Greene’s bal-anced tableaux and proved an existence result for such generalized tableaux on skew shapesin Theorem 7.22. This would add to the properties described in Remark 6.9 that are knownabout shellable families of sets. Additionally, as shellable families are families of sets thatsatisfy a stronger form of the marriage condition, Theorem 6.14 adds to what is known aboutthe marriage condition. Further to this, Theorem 6.14 and Theorem 7.22 provide existenceresults to natural generalizations of balanced tableaux and skew tableaux and establish thatthe numbers of such tableaux are related to the enumerative formulas for balanced tableauxdiscovered by Edelman and Greene in [13, 14] and the enumerative formulas for standardYoung tableaux discovered by Frame, Robinson, and Thrall in [16].We now discuss the future directions that we have in mind for this work.Recall that the Cayley-Hamilton Theorem states that if M is a square matrix and if p(x) is thecharacteristic polynomial of M, then p(M) = 0. By applying the Cayley-Hamilton Theoremto the square matrix in Theorem 5.19 and by using Lemma 5.10, we plan to prove that thematrix difference equation in Theorem 5.19 can be used to prove that periodic P-partitionscan be enumerated with constant coefficient linear recurrence relations. In particular, weplan to recover all of the constant coefficient linear recurrence relation results of Lo´pez et.al.[27], Sun [47], and Tewari and van Willigenburg [49].In view of the above plan, we aim to analyse six aspects of the above recurrence relations ob-tained via the Cayley-Hamilton Theorem, which, in this chapter, we call periodic recurrence92relations after the periodic P-partitions that they enumerate, and the number of periodic P-partitions, which are enumerated by the periodic recurrence relations.Firstly, we plan to use a known result that express the characteristic polynomial of a squarematrix A in terms of its trace trA [26] and to give combinatorial descriptions for trM whenM is the matrix in Theorem 5.19. From this, we can obtain combinatorial descriptions forthe coefficients of the periodic recurrence relations. Using the work from ([6], Question1284192; c.f. [9], Section 3.1) to describe the characteristic polynomial of the square matrixA, the above combinatorial descriptions can also be converted into a determinantal formulasfor the above coefficients.Secondly, we plan to analyse the asymptotics of the number of periodic P-partitions. Con-sider the notation Pn as given in Proposition 5.10. We plan to prove that |Pn,ω| is asymptoticto crn as n→∞ for some constants c> 0 and r> 1 that depend on the sequence (Pn)n=1,2,....To do this we will use properties of transfer matrices for directed graphs [44] to prove fur-ther combinatorial properties of the matrix in Theorem 5.19, then invoke results in Perron-Frobenius theory [4, 11, 32].Thirdly, we plan to analyse the largest and second largest eigenvalues of the matrix in Theo-rem 5.19. For the largest eigenvalue, we plan to give a combinatorial description and to givebounds. For the bounds, we will use Perron-Frobenius theory and matrix theory [33]. Suchan approach can also utilize many known bounds, that have varying levels of complexity,for the largest eigenvalue [7, 17, 20, 32, 33, 37, 52]. For the second largest eigenvalue, weplan to use certain tools in matrix and spectral graph theory [11, 33] to give combinatorialdescriptions.Fourthly, in a related direction, we plan to establish a link between certain finite posets and93certain monic polynomials in Z[x]. Speficially, we plan to prove a relationship betweenthe minimal polynomials of the matrices in Theorem 5.19 and the posets that are the indexshapes in Theorem 5.19 by proving the following.Conjecture 8.1. The condition that one such minimal polynomial divides another such min-imal polynomial is equivalent to the condition that one such poset is a subposet of anothersuch poset.Fifthly, as an application of the connected triple concept we introduced, we plan to provethat many columns of the transfer matrices in Theorem 5.19 are identical. A generaliza-tion of such properties was explored by Lundow [29] where symmetry properties of certainrecurrence relations were investigated.Lastly, in the case when the labelling ω in the periodic quadruple system (Z,ω,pi,θ) is dual-natural, we also plan to adapt Lo´pez et.al’s proof technique from [27], by generalizing it tothe level of generality considered in this thesis, to derive exponential upper bounds on theorders of the periodic recurrence relations, and to derive exponential upper bounds on thedegrees of the minimal polynomials of the matrices in Theorem 5.19.For the results relating to generalized balanced tableaux and marriage problems with uniquesolutions, there are three aspects of these results that we plan to analyse.In a preprint submitted for publication, we generalize Theorem 6.14 to certain words in [n]m,where m≤ n and m is bounded below by a formula that depends on the shellable family F .Moreover, we generalize Theorem 7.22 to shellable families and the aforementioned wordsin [n]m and the expression in Theorem 7.22 is generalized to include Stirling numbers of thesecond kind. In discussing the feasibility of such a formula, we use known properties ofthese Stirling numbers.94There is a known formula in the literature, that is a more complex form of the hook-lengthformula, for determining the number of standard skew tableaux of shape λ/µ [34]. More-over, asymptotic properties of such numbers were analysed by Morales, Pak, and Panova in[34]. By combining these results with Theorem 7.22, we plan to investigate the number ofconfigurations f such that N( f ) is strictly less than the expression given in Theorem 7.22.Such an investigation appears to be generalizable since there are variants and generalizationsof Naruse’s formula that are known [19, 36], and since for at least some of these variants,extensions of Morales, Pak, and Panova’s asymptotic properties are conjectured to extend toat least some of these variants.Lastly, we plan to define a natural partial ordering on the possible configurations f of atransversal t of a family of sets. With this partial order, we plan to derive a product formulathat would give a general upper bound for N( f ), where N( f ) is as defined in Theorem 7.22,by utilizing the order-preserving maps in the proof of Theorem 6.14.95Bibliography[1] R. Adin, R. King, and Y. Roichman, Enumeration of standard Young tableaux of certaintruncated shapes, Electron. J. Comb. 18(2) (2011). → pages 2, 91[2] R. Adin and Y. Roichman, Standard Young Tableaux Chapter 14 of Handbook of Enu-merative Combinatorics 1st Edition, Edited by Miklo´s Bo´na, Chapman and Hall/CRC(2015). → pages 2, 9, 11, 12, 30[3] R. Adin and Y. Roichman, Triangle-Free Triangulations, Hyperplane Arrangementsand Shifted Tableaux Electron. J. Comb. 19(3) (2012). → pages 2, 91[4] J. Allouche and J. Shallit, Automatic Sequences, Theory, Applications, Generalizations,Cambridge Univ. Press (2003). → page 93[5] O. Angel, A. Holroyd, D. Romik, and B. Vira´g, Random sorting networks, Adv. Math.215 839 - 868 (2007). → page 5[6] J. Atwood and J. Spolsky, Math Stack Exchange, https://math.stackexchange.com →page 93[7] A. Brauer, The theorems of Ledermann and Ostrowski on positive matrices, Duke Math.J. 24, 265 - 274 (1957). → page 9396[8] A. Bjo¨rner and F. Brenti, Combinatorics of Coxeter Groups, Grad. Texts in Math. 231,Springer, (2005). → pages 73, 74[9] T. Curtright and D. Fairlie, A Galileon Primer, arxiv : 1212.6972v1 (2012). → page 93[10] G. Chang, On the Number of SDR of a (t,n)-family European J. Combin.10, 231 - 234(1989). → pages 4, 73[11] F. Chung, Laplacians and the Cheeger inequality for directed graphs Ann. Comb. Vol-ume 9, Issue 1, 1 - 19 (2005). → page 93[12] B. Davey and H. Priestley, Introduction to Lattices and Order, Second Edition Cam-bridge Univ. Press (2002). → page 8[13] P. Edelman and C. Greene, Balanced Tableaux Adv. Math. 63 42 - 99 (1987). → pages4, 5, 86, 87, 88, 92[14] P. Edelman and C. Greene, Combinatorial correspondences for Young tableaux, bal-anced tableaux, and maximal chains in the weak Bruhat order of Sn, Contemp. Math.34 (1984). → pages 4, 5, 92[15] S. Fomin, C. Greene, V. Reiner, M. Shimozono, Balanced Labellings and SchubertPolynomials European J. Combin. 18, 373 - 389 (1997). → page 5[16] J. Frame, G. Robinson, R. Thrall, The hook graphs of the symmetric group Canad. J.Math. 6, 316 - 325 (1954). → pages 88, 92[17] K. Garren, Bounds for the eigenvalues of a matrix National Aeronautics and Space Ad-ministration, Washington D.C., Langley Research Center, Langley Station, Hampton,Va. (1968). → page 9397[18] I. Gessel, Multipartite P-partitions and inner products of skew Schur functions Comb.Algebra, Proc. Conf., Boulder/CO 1983, Contemp. Math. 34, 289-301 (1984). → page1[19] W. Graham and V. Kreiman, Excited Young diagrams, equivariant K-theory, and Schu-bert varieties, Trans. Amer. Math. Soc. Vol. 367, No. 9 6597 - 6645 (2015). → page95[20] C. Hall and T. Porsching, Bounds for the maximal eigenvalue of a nonnegative irre-ducible matrix. Duke Math. J. 36, 159-164 (1969). Review by R. Rinehart available onmathsci.net → page 93[21] P. Hall, On Representatives of Subsets, J. London Math. Soc, 10 (1) 26 - 30 (1935). →pages 4, 70, 71[22] M. Hall Jr, Distinct Representatives of Subsets, Bull. Amer. Math. Soc. Vol. 54, No. 10,922 - 926 (1948). → pages 4, 73, 78[23] J. Hirst and N. Hughes, Reverse mathematics and marriage problems with finitely manysolutions Arch. Math. Logic 55:1015 - 1024 (2016). → page 4[24] J. Hirst and N. Hughes, Reverse mathematics and marriage problems with unique so-lutions Arch. Math. Logic 54:49 - 57 (2015). → pages 4, 73[25] M. Konvalinka, A bijective proof of the hook-length formula for skew shapes,arXiv:1703.08414v2 (2018). → page 4[26] M. Lewin, On the coefficients of the characteristic polynomial of a matrix DiscreteMath. 125 255-262 (1994). → page 9398[27] A. Lo´pez, L. Martı´nez, A. Pe´rez, B. Pe´rez, O. Basova, Combinatorics related to Hig-man’s conjecture I: Parallelogramic digraphs and dispositions, Linear Alg. Appl. 530414 - 444 (2017). → pages 2, 3, 22, 27, 91, 92, 94[28] D. Little, Combinatorial aspects of the Lascoux - Schu¨tzenberger tree, Adv. Math. 174236 - 253 (2003). → page 5[29] P. Lundow Compression of transfer matrices Discrete Math. 231 321 - 329, Elsevier(2001). → page 94[30] K. Luoto, S. Mykytiuk, S. van Willigenburg, An introduction to quasisymmetric Schurfunctions - Hopf algebras, quasisymmetric functions, and Young composition tableaux- Springer (2013). → pages 11, 12, 80, 82[31] P. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York (1960). →page 1[32] C. Meyer, Matrix Analysis and Applied Linear Algebra, First Edition, SIAM (2000).→ page 93[33] H. Minc, Nonnegative Matrices, Wiley Interscience Series in Discrete Mathematics andOptimization (1988). → page 93[34] A. Morales, I. Pak, G. Panova, Asymptotics of the number of standard Young tableauxof skew shape, Electron. J. Combin. 70 26 - 49 (2018). → pages 5, 95[35] A. Morales, I. Pak, G. Panova, Hook formulas for skew shapes I. q-analogues andbijections J. Combin. Theory Ser. A 154 350 - 405 (2018). → page 4[36] H. Naruse and S. Okada, Skew hook formula for d-complete posets via equivariantK-theory Algebr. Comb. Vol. 2 Issue 4 541 - 571 (2019). → pages 4, 9599[37] A. Ostrowski, H. Schneider Bounds for the maximal characteristic root of a non-negative irreducible matrix. Duke Math. J. 27, 547 - 553 (1960). Review by W. Le-dermann available on mathsci.net → page 93[38] G. Panova, Tableaux and plane partitions of truncated shapes Adv. Appl. Math. 49 196- 217 (2012). → pages 2, 91[39] I. Pak, F. Petrov, and V. Sokolov, Hook Inequalities arXiv:1903.11828v2 (2019). →page 5[40] P. Reichmeider, The Equivalence of Some Combinatorial Matching Theorems, Polygo-nal Pub House (1985). → page 4[41] B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, andSymmetric Functions (2nd Edition), Graduate Texts in Mathematics 203, Springer-Verlag New York Inc., (2001). → pages 3, 11, 12, 80, 82, 83, 84, 92[42] B. Schro¨der, Ordered Sets, An Introduction with Connections from Combinatorics toTopology Second Edition, Birkha¨user, Springer International Publishing (2016). →page 8[43] N. Sloane, The on-line encyclopedia of integer sequences http://oeis.org. → page 3[44] R. Stanley, Enumerative Combinatorics, Volume 1, Second Edition Cambridge Stud. inAdv. Math. 49, Cambridge Univ. Press (2012). → pages 2, 8, 11, 12, 16, 18, 93[45] R. Stanley, Enumerative Combinatorics, Volume 2, First Edition Cambridge Stud. inAdv. Math. 62, Cambridge Univ. Press (1999). → pages 3, 4, 11, 12, 26, 82, 91, 92[46] R. Stanley, Ordered structures and partitions Revision of R. Stanley’s PhD thesis atHarvard Univ. 1971, Dep. Math. Univ. California Berkley, California 94720. → page 1100[47] P. Sun, Enumeration of standard Young tableaux of shifted strips with constant widthElectron. J. Combin. 24 1 - 11, (2017). → pages 2, 3, 22, 27, 91, 92[48] J. Swanson, On the Existence of Tableaux with Given Modular Major Index, Algebr.Comb. Vol. 1, No. 1, 3 - 21 (2018). → page 5[49] V. Tewari and S. van Willigenburg, Modules of the 0-Hecke algebra and qua-sisymmetric Schur functions Adv. Math. 285 1025 - 1065 (2015). → pagesv, 2, 3, 22, 27, 30, 91, 92[50] F. Viard, A natural generalization of balanced tableaux, arxiv 1407.6217v2 (2016). →page 90[51] F. Viard, Des graphes oriente´s aux treillis complets : une nouvelle approche de l’ordrefaible sur les groupes de Coxeter. Univ. Claude Bernard Lyon 1 E´cole doctorale Info-Math , ED 512 Spe´cialite´ : Mathe´matiques N. do´rdre 232-2015. → page 90[52] J. Zhang, Some bounds for the determinant and eigenvalues of a matrix. KnowledgePractice Math., no. 3, 19 - 25 (1981). Review by J. Kim available on mathsci.net →page 93101

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0392434/manifest

Comment

Related Items