EXPANSION POSETS FOR POLYGON CLUSTER ALGEBRAS By Andrew Claussen A DISSERTATION Michigan State University in partial ful(cid:27)llment of the requirements Submitted to for the degree of Mathematics — Doctor of Philosophy 2020 ABSTRACT EXPANSION POSETS FOR POLYGON CLUSTER ALGEBRAS By Andrew Claussen De(cid:27)ne an expansion poset to be the poset of monomials of a cluster variable attached to an arc in a polygon, where each monomial is represented by the corresponding combinatorial object from some (cid:27)xed combinatorial cluster expansion formula. We introduce an involution on several of the interrelated combinatorial objects and constructions associated to type A surface cluster algebras, including certain classes of arcs, triangulations, and distributive lattices. We use these involutions to formulate a dual version of skein relations for arcs, and dual versions of three existing expansion posets. In particular, this leads to two new cluster expansion formulas, and recovers the lattice path expansion of Propp et al. We provide an explicit, structure-preserving poset isomorphism between an expansion poset and its dual version from the dual arc. We also show that an expansion poset and its dual version constructed from the same arc are dual in the sense of distributive lattices. We show that any expansion poset is isomorphic to a closed interval in one of the lattices L(m, n) of Young diagrams contained in an m × n grid, and that any L(m, n) has a covering by such intervals. In particular, this implies that any expansion poset is isomorphic to an interval in Young’s lattice. We give two formulas for the rank function of any lattice path expansion poset, and prove that this rank function is unimodal whenever the underlying snake graph is built from at most four maximal straight segments. This gives a partial solution to a recent conjecture by Ovsienko and Morier-Genoud. We also characterize which expansion posets have symmetric rank generating functions, based on the shape of the underlying snake graph. We show that the support of any type A cluster variable is the orbit of a groupoid. This implies that any such cluster variable can be reconstructed from any one of its monomials. Finally, in work joint with Nicholas Ovenhouse, we partially generalize T-paths to con(cid:27)gura- tions of a(cid:28)ne (cid:30)ags, and prove that a T-path expansion analogous to the type A case holds when the initial seed is from a fan triangulation. We (cid:27)nish by describing the structure of two types of expansion posets in this context. To my parents, Kay Marie Claussen and Irvin Boyd Claussen. iv ACKNOWLEDGMENTS First and foremost, I would like to thank my advisor Misha Shapiro. Certainly, this thesis would not have been possible without his tireless guidance, endless patience, and unwavering personal and academic support. I would like to thank the other members of my committee Jonathan Hall, Rajesh Kulkarni, and Bruce Sagan, both for their inspiring courses and lectures, and for their continual support and encouragement throughout the years. In particular, I am deeply indebted to Bruce Sagan for his diligent reading of this work. His large list of corrections has greatly improved this thesis. A special thanks goes to my friend and collaborator Nicholas Ovenhouse. In particular, I am grateful for both the innumerable comments and corrections that he o(cid:29)ered during the writing of this thesis, and also for his willingness to have our joint work included here. I would like to thank my fellow graduate students for their friendship and support, especially Nick Ovenhouse, Blake Icabone, Du(cid:29) Baker-Jarvis, and Sami Merhi. Likewise, thanks to everyone I met through the advanced track program at MSU, especially Daniel Diro(cid:29), Bar Roytman, Christopher Klerkx, Rebecca Sodervick, Jonathan Jonker, and Katrina Suchoski. I am grateful to Tsvetanka Sendova, Russel Schwab, and Jeanne Wald for their commitment to my professional development, and for all the opportunities they have presented me with during my time at MSU. Indeed, thanks to all the faculty and sta(cid:29) at MSU with whom I have had the pleasure of working with. I would like to thank Mark Naber of Monroe County Community College for inspiring me to v further my mathematical education. Finally, I am thankful to all my wonderful family and friends for the love and support they have given me throughout this endeavor. I’d like to give special thanks to my dad (Rusty), Marshia, Aaron and Autumn, Chris, Jake, Graham, and the Minney family. vi TABLE OF CONTENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 7 7 10 11 . 13 . 13 14 . 15 . . 16 21 . 25 . 30 . . 32 . 35 . 35 39 . 43 . . 47 . 52 52 . . 52 53 . 54 . 55 . . 58 61 . . 62 . 63 63 . 66 . . 69 73 . LIST OF FIGURES . . . . . . . . . Chapter 1 . Introduction . Cluster Algebras . . Chapter 2 . . . . 2.1 Cluster Algebras from Quivers . . . 2.2 Cluster Algebras from Surfaces . . 2.3 Cluster Algebras of Finite Type An . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 3 . . . . . . . . . . . Posets . Combinatorial Constructions . . . 3.1 Words . . . . . 3.2 Type An Dynkin Quivers . . . . . 3.3 . . . 3.4 Triangulations . . . 3.5 Arcs, Cluster Variables, and Resolutions . . 3.6 . . 3.7 Continued Fractions . 3.8 Distributive Lattices . . Snake Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 4 . Expansion Posets . Perfect Matchings of Snake Graphs 4.1 . Perfect Matchings of Angles 4.2 . 4.3 T-Paths . . 4.4 Expansion Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 5 . . . . . . . . . . . Posets . Dual Combinatorial Constructions . . . . . . . . . . . . . . . . . . . . . Slides, Arcs, and Cluster Variables . Snake Graphs . . . 5.1 Words . . . 5.2 Type An Dynkin Quivers . . . 5.3 . 5.4 Triangulations . . . 5.5 5.6 . 5.7 Continued Fractions . 5.8 Distributive Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 6 Dual Expansion Posets . . Lattice Paths on Snake Graphs . . . Lattice Paths of Angles . . . . . . 6.1 6.2 6.3 S-walks . . 6.4 Expansion Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Chapter 7 Expansion Posets as Intervals in Young’s Lattice . . . . . . . . . Posets of Snake Graphs and the q-binomial Coe(cid:28)cients . . . 7.1 Graded Expansion Posets . 7.2 7.3 The Embeddings Lw (cid:44)→ On . . . . . . . . . . . . . . . . . . . . . . . . . . . . . j . . . Chapter 8 Lattice Path Recursion . . 8.1 8.2 Hook Rank Formula . 8.3 . . Fibonacci Rank Formula . A Recursion and Two Rank Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 9 9.1 Rank Unimodality . 9.2 Rank Symmetry . . Unimodality and Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 10 Expansion Posets as Groupoid Orbits . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 11 Some T -paths for Con(cid:27)gurations of Flags . . . . . . . . . 11.1 Decorated Teichmüller Spaces . . 11.2 Higher Teichmüller Spaces . . 11.3 Colored SL3 Diagrams . . . . 11.4 Crossings in Colored SL3 Diagrams . 11.5 Fork-Join Networks . . . 11.6 Generalized T-paths . . . . 11.7 An Expansion Formula for Arcs in Fan Triangulations . 11.8 Some Expansion Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 81 . 83 . . 86 . 94 . 94 . 98 . 102 . 105 . 106 . 119 . 124 . 126 . 126 . 128 . 130 . 131 . 132 . 135 . 141 . 143 . 149 LIST OF FIGURES Figure 1.1: A (cid:30)ip inside a triangulated pentagon . Figure 1.2: Expansion duality . Figure 2.1: Quiver mutation . . . . . . . . . Figure 2.2: Flip inside a quadrilateral Figure 2.3: One seed for A3. Figure 3.1: Type An Dynkin diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 3.2: Orientation of a type An Dynkin diagram . . . Figure 3.3: . . . . . . . . . The Dynkin quiver Aab . . The poset Cab . . Four examples of fence posets Cw . . . . . . . . . . . . . . . . . . . . Figure 3.4: Figure 3.5: Figure 3.6: Clockwise 3-cycles created from edges in Aw . . . Figure 3.7: Leftmost 3-cycle . . . . . . . . . . . . . . . Figure 3.8: Rightmost 3-cycle, if either l(w) is odd or l(w) is even and w ends in a2 or b2. Figure 3.9: Rightmost 3-cycle, if l(w) is even and w ends in ab or ba. . . . Figure 3.10: The quiver Qab Figure 3.11: The triangulated polygon Σab . . . Figure 3.12: A fan triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 3.13: The arc γab inside Σab, and the associated cluster variable xab . Figure 3.14: Resolution of the intersection point pi . . Figure 3.15: One element of Tree(ab) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 3.16: An arc in a triangulated subpolygon . . . . . . . . . . . . . . . ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 8 10 12 14 14 15 15 16 17 17 18 18 18 20 20 21 22 24 24 Figure 3.17: Shorthand to describe the corners and edges of a tile Ti . Figure 3.18: Construction of the snake graph Gab . . . . Figure 3.19: The folding and unfolding maps . . . . . . . . . . . . . . . . . . . . . Figure 3.20: The sign function s on Gab Figure 3.21: The sign sequence sab on Gab . . Figure 3.22: Four Fibonacci cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 4.1: Figure 4.2: Figure 4.3: Figure 4.4: Figure 4.5: Figure 4.6: Figure 4.7: Figure 4.8: Figure 4.9: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The perfect matching P− on Gab The (cid:27)ve perfect matchings on Gab Twist of a perfect matching at tile Ti The poset Pab . . . The perfect matching of angles α− on Σab. Twist of a perfect matching of angles at diagonal δi . . The poset Aab . . The T-path T− with edges from ∆ab . . Twist of a T-path at diagonal δi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 27 27 28 29 33 36 37 38 39 40 41 42 44 45 . . . . . . . . . . . . . . . . . . . . . . . Figure 4.10: T-path twists at internal diagonals are always de(cid:27)ned . Figure 4.11: The poset Tab . . . Figure 4.12: The map Pab −→ Aab via angle identi(cid:27)cation and folding . . . Figure 4.13: The map Aab −→ Tab via diagonal coloring and cancellation . 50 Figure 4.14: The composition Pab −→ Aab −→ Tab −→ Pab restricted to minimal elements 51 53 Figure 5.1: 45 47 50 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The quiver Aab and its dual Abb . The poset Cab and its dual Cbb . The triangle map applied to Σab gives Σbb . . . . . . . . . Figure 5.2: Figure 5.3: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 54 Figure 5.4: Dual resolution of the intersection point pi . Figure 5.5: One element of Tree(bb)∗ . . Figure 5.6: Construction of the dual snake graph Gbb Figure 5.7: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 6.3: Figure 6.2: Figure 6.6: Figure 6.5: Figure 6.4: Figure 6.1: Figure 5.9: Figure 5.8: Transforming Gab into its dual Gbb . The sign sequence sab and its dual sbb The Fibonacci cube Γ3 and its dual . The lattice path L− on Gbb . . Flip of a lattice path at tile Ti . The poset Lbb . The lattice path of angles β− on Gbb Flip of a lattice path of angles at diagonal δi The poset Bbb . . . Flip of an S-walk at diagonal δi . . The poset Sbb . . The map Lw −→ Bbb via angle identi(cid:27)cation and folding . Figure 6.9: Figure 6.10: The map Bbb −→ Sbb via associating edges to angles . . . . Figure 6.11: The arc δ, and the output arc δ∗ for both j odd and j even . Figure 6.12: Transforming the minimal element P− into the minimal element L− . Figure 6.13: Transforming the minimal element α− into the minimal element β− . Figure 6.14: Transforming the minimal element T− into the minimal element S− . . . Figure 7.1: Posets, shapes, and rank functions for three snake graphs Figure 6.7: Figure 6.8: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 7.2: Local picture for two equivalent snake graphs . Figure 7.3: The poset O5 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 57 59 60 61 62 63 65 66 67 68 69 70 71 72 73 76 78 78 79 83 83 84 Figure 7.4: The poset 3 × 3 (bottom), its lattice of order ideals I(3 × 3) (top left), and . . the rank function of O7 3 ∼= I(3 × 3) (top right) . . . . . . . . . . . . . . Figure 7.5: The Young diagram associated to the partition (4, 3) of 7 . Figure 7.6: Figure 7.7: Figure 7.8: . . . . . . Snake graphs from lattice paths . ∼= Lab . The posets Lab and Iab Three lattice path posets embedded into O6 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 87 88 88 90 Figure 7.9: Local picture for two snake graphs related under the dual equivalence relation 91 Figure 7.10: Snake graphs from perfect matchings . Figure 7.11: The poset dual to O5 2 . . . . . . . . . . . . The maximal straight segments of Gw . . . Initial step in the recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 8.1: Figure 8.2: Figure 8.3: Figure 8.4: Figure 8.5: Figure 8.6: Figure 8.7: Figure 9.1: Figure 9.2: . The recurrence for the (cid:27)rst maximal straight segment of Gw . The recurrence for the second maximal straight segment of Gw . Recursive computation of the rank function Lw3(q) . . . . The construction of Gw from Gw . . The poset Gab, its node weights, and the rank function Lw(q) . The snake graphs Gw and G0, and the associated posets Lw0 The rank function L . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 9.3: The rank function [m]qL Figure 9.4: A Markov snake graph . a2b5(q) via block stacking . . . a2b5(q) for 1 ≤ m ≤ 12 . . . . . . . . . . . . . . . . . . . . Figure 9.5: The snake graph with continued fraction [2, 2, 2, 2, 2] . Figure 11.1: A 3-triangulation . . . . . . . . . . . Figure 11.2: Visualization of a Laurent monomial . . . . . . . . . . . . . . . . . . . . and Lw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 93 95 96 97 97 98 . 103 . 103 . 108 . 109 . 117 . 123 . 123 . 129 . 130 Figure 11.3: Face resolution . Figure 11.4: Edge resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.5: A directed edge and a face which cross . Figure 11.6: A fork-join network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.7: A fork-join network satisfying conditions (A1) and (A2) Figure 11.8: Construction of an alternating fork-join network Ω . Figure 11.9: Faces as webs . . . . . . . . . . . . . . . . . Figure 11.10: Two edge-type T-paths . Figure 11.11: A generic fan triangulation with diagonals δi . Figure 11.12: Step (E1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.13: The two choices in Step (E2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . 131 . 132 . 133 . 133 . 134 . 135 . 137 . 137 . 138 . 138 Figure 11.14: The result of superimposing the edges from the left diagram in Figure 11.13 . 139 Figure 11.15: The result of superimposing the edges from the right diagram in Figure 11.13 139 Figure 11.16: The result of superimposing onto the diagram from Figure 11.14 the edges . from (E3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.17: The result of superimposing onto the diagram from Figure 11.15 the edges . from (E3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 . 140 . 142 . 143 . 144 . . . . . . . . . . . . . . . . . . Figure 11.18: The (cid:27)rst step in the resolution of the longest edge in a hexagon . Figure 11.19: The two types of(cid:98)y-variables . Figure 11.20: Covering relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.21: The lattice path abbabbabb . . . Figure 11.22: The construction of Lγ . Figure 11.23: The gluing construction of the expansion poset of the longest edge in a pentagon 147 . 145 . 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11.24: Expansion poset of a fan face . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Figure 11.25: The bijection between a fan face poset and the corresponding SL2 T-path poset 148 Chapter 1 Introduction Cluster algebras are a class of inherently combinatorial commutative algebras that were de(cid:27)ned by Fomin and Zelevinsky in [14]. The de(cid:27)nition of cluster algebras was motivated by observations in representation theory. Since then, cluster algebra structures have been recognized and studied in various other (cid:27)elds of mathematics, such as decorated Teichmüller theory and Poisson geometry (see [18] and [12], [13]), higher Teichmüller theory [9], rings of invariants (see [10] and [11]), elementary number theory [5] including diophantine equations [34], and knot theory [26], just to name a few. Each cluster algebra has a distinguished set of generators, called the cluster variables. These generators are grouped into overlapping subsets, called clusters, all having the same cardinality, called the rank of the cluster algebra. A seed of a cluster algebra is a triple consisting of a cluster, a coe(cid:28)cient tuple, and a skew- symmetrizable matrix called an exchange matrix. In any rank n cluster algebra, each seed can be mutated in direction i for any 1 ≤ i ≤ n to produce n more seeds. By construction, seed mutation is an involution. Clusters in adjacent seeds di(cid:29)ering by a mutation in direction i are equal, except that the ith variables in each di(cid:29)er from one another by what is called an exchange relation. This means that their product is a certain binomial sum whose form is governed by the exchange matrices. Any cluster algebra can be computed by (cid:27)xing an initial seed and iterating seed mutation to produce all the cluster variables. 1 nomial can be written as(cid:80) A Laurent polynomial is a polynomial with negative exponents allowed, i.e., any Laurent poly- I∈Zn aI XI. One of the (cid:27)rst fundamental results of cluster algebra theory is that any cluster variable can be written as a Laurent polynomial with respect to any cluster. This is called the Laurent phenomenon. We will work within the subclass of cluster algebras in which exchange matrices and matrix mutation may be replaced by quivers and quiver mutation, respectively. These cluster algebras are called cluster algebras from quivers, or skew-symmetric cluster algebras of geometric type A large subclass of cluster algebras are the cluster algebras from surfaces [8]. In such a cluster algebra, the cluster variables are in bijection with certain curves in the surface called tagged arcs, seeds are in bijection with tagged triangulations of the surface, and mutation corresponds to a (cid:30)ip of a tagged arc in a tagged triangulation. The combinatorics of the subclass of cluster algebras from a disc with n + 3 marked points on the boundary (i.e., a polygon) are the main focus of this paper. These cluster algebras are examples of cluster algebras of (cid:27)nite type An. As the notion of tagged triangulations and tagged arcs is unnecessary in this restricted level of generality, we will henceforth only speak of (ordinary) arcs. Any seed in a cluster algebra of (cid:27)nite type An can be modeled by a triangulated (n + 3)- gon, made up of n triangulating arcs (which we also call internal diagonals, or just diagonals), and n + 3 segments that make up the boundary of the polygon, called boundary segments. Mutation corresponds to a (cid:30)ip of one of the n internal diagonals in the triangulation. Figure 1.1 below shows one of the two possible (cid:30)ips inside a triangulated polygon. Numerous combinatorial cluster expansion formulas for surface type and type An cluster al- gebras have been developed in recent years. Each such expansion gives an explicit formula to compute any cluster variable by writing it as a weighted sum over a certain class of combinato- rial objects. We recall three such expansion formulas from the literature - perfect matchings of 2 Figure 1.1: A (cid:30)ip inside a triangulated pentagon snake graphs, perfect matchings of angles, and T -paths. (see [30] and [31], [42] and [43], and [36], [38], and [37] respectively). The monomials of any cluster variable can be naturally arranged into a poset [15]. We can equip each such poset with the additional node structure it inherits from some combinatorial expansion formula. We call any such poset an expansion poset (in fact, each of these posets is isomorphic to a distributive lattice [31]). In this paper, inspired by the snake graph involution introduced in [33] and the involution “Jimm” in [41], we de(cid:27)ne a new notion of duality, a certain involution on several of the combi- natorial objects found in type A cluster theory, including for instance triangulations of an n-gon, and a certain class of distributive lattices. Each such object is parameterized by a binary word w, so that duality between objects is controlled by duality w ←→ w∗ on the underlying words. These constructions yield a dual version of skein relations for arcs. Furthermore, we use this duality to produce an equivalent yet combinatorially distinct version (built from the dual arc in the dual triangulation) of each of the three expansion posets mentioned above. Namely, we observe that there is an explicit poset isomorphism (respecting additional node structure) between the perfect matching expansion poset Pw, and the dual lattice path expansion w∗ associated to the dual word. This duality, minus poset structures, was given in [33] poset L in the context of frieze patterns. We de(cid:27)ne two more expansion posets, new to the best of our 3 knowledge, which we call lattice paths of angles Bw and S-walks Sw, respectively. We observe that there is an explicit structure-preserving poset isomorphism between the expansion posets Aw and B w∗, and likewise between the T-path expansion poset Tw and S w∗. The three isomorphisms just indicated are all written in terms of either snake graph duality, or traingulation duality. Here, we call any such isomorphism an expansion duality. The horizontal maps in the (cid:27)gure below represent expansion dualities. The maps comprising the two triangles are written either in terms of the folding/unfolding maps from [29], or the “angle projection” maps de(cid:27)ned in [43] (or some combination of the two). Figure 1.2: Expansion duality L∗ w B∗ w Pw Aw S∗ w Tw Furthermore, we show that the two isomorphism classes of expansion posets attached to any arc are dual in the sense of distributive lattices mentioned above. A partition of a positive number m is a weakly decreasing sequence (λ1, λ2, . . . , λl) such that m = λ1 + λ2 +··· + λl. A Young diagram is a visualization of a partition of a positive integer by rows of boxes (see [35]). Young’s lattice is the in(cid:27)nite lattice whose nodes are Young diagrams, which are ordered by inclusion (see [35] and [39]). Young’s lattice possesses a collection of (cid:27)nite (cid:3) m × n rectangular grid, and whose rank function is the q-binomial coe(cid:28)cient(cid:2)n+m sublattices, typically called L(m, n), whose nodes are all those Young diagrams that (cid:27)t within an . We give m q a groupoid structure on the set of all snake graphs which reconstructs the posets L(m, n). That is, each orbit of this groupoid can be given the structure of a poset, which is isomorphic to one of 4 the lattices L(m, n), and furthermore (the isomorphism class of) every L(m, n) can be obtained in this way. We show that each expansion poset considered above is isomorphically embedded as a closed interval in some L(m, n), and moreover that each L(m, n) has a covering by such embeddings. We provide two closed formulas for the rank function Lw(q) of any lattice path expansion poset Lw of lattice paths on the snake graph Gw. The (cid:27)rst is written as sums of products of hook snake graphs, and its terms are parameterized by the nodes in a Boolean lattice. The second for- mula we introduce is a re(cid:27)nement of the (cid:27)rst, and is written in terms of q-numbers corresponding to lengths of the maximal straight segments that Gw is built from. The latter formula is obtained by considering the snake graph Gw itself as a lattice path on another snake graph. In fact, this construction makes Gw into the central node in a Fibonacci cube, an interconnection topology de(cid:27)ned in [23]. Recently, a conjecture was made in [27] that is equivalent to asking if the coe(cid:28)cients of the rank generating function of any expansion poset are unimodal, meaning that they weakly increase, and then weakly decrease. By again studying lattice path expansions, we show this conjecture to be true for snake graphs built from at most four maximal straight segments. We also characterize, based on the shape of the underlying snake graph, which expansion posets have palindromic, or symmetric, coe(cid:28)cients. Next, we interpret the support of any cluster variable xw in a type A surface cluster algebra as an orbit of a certain groupoid. It follows that any two cluster variables, written with respect to the same initial seed, have disjoint supports. Thus, any cluster variable xw is completely determined by any one of its Laurent monomials. Lastly, in work joint with Nicholas Ovenhouse, we partially generalize the T-path expansion mentioned above to con(cid:27)gurations of a(cid:28)ne (cid:30)ags (see [9]). We describe in two special cases the 5 poset structure on the Laurent monomials from an expansion in this context. 6 Chapter 2 Cluster Algebras We begin this chapter by de(cid:27)ning the subclass of cluster algebras called cluster algebras from quivers, or skew-symmetric cluster algebras of geometric type. Next, we introduce cluster algebras from surfaces. Finally, we describe surface cluster algebras of type A, which is the class of cluster algebras we study in the rest of the paper. 2.1 Cluster Algebras from Quivers De(cid:27)nition 2.1. A quiver is a 4-tuple Q = (Q0, Q1, s, t), where Q0 is a set of nodes or vertices, Q1 is a multiset of arrows whose elements are from Q0 × Q0, and the source and target functions s, t : Q1 −→ Q0 are the (cid:27)rst and second projection, respectively. A quiver Q contains a loop if there exists a node v ∈ Q0 and an arrow e ∈ Q1 such that v = s(e) = t(e). We say Q contains a 2-cycle if there exists two distinct nodes v1, v2 ∈ Q0 and two arrows e1, e2 ∈ Q1 such that v1 = s(e1) = t(e2) and v2 = s(e2) = t(e1). A quiver Q contains a 3-cycle if there exist three distinct nodes v1, v2, v3 ∈ Q0 and three arrows e1, e2, e3 ∈ Q1 such that v1 = s(e1) = t(e3), v2 = s(e2) = t(e1), and v3 = s(e3) = t(e2). We say Q is (cid:27)nite if both Q0 and Q1 are (cid:27)nite sets. In this case, we label the vertices of Q by 1, 2, ..., #{nodes in Q}. From now on, we only consider (cid:27)nite quivers (unless stated otherwise) that do not contain any loops or 2-cycles. 7 De(cid:27)nition 2.2. Let Q = (Q0, Q1) be a quiver with vertices Q0 = {1, 2, ..., n}. We de(cid:27)ne quiver mutation at vertex k to be the the map on quivers µk whose image µk(Q) is de(cid:27)ned by the following procedure: 1. For each pair of arrows i → k → j, create a new directed edge i → j (note that prohibiting 2-cycles implies that i (cid:54)= j). 2. Reverse the orientation of each arrow incident to k 3. Delete any and all 2-cycles created in step 1. Example 2.3. In Figure 2.1, we illustrate the three-step process in De(cid:27)nition 2.2 by mutating the left-most quiver at vertex 1 to produce the right-most quiver. Figure 2.1: Quiver mutation 1 Q = 3 1 3 1 Step 1 2 2 Step 2 2 3 1 Step 3 3 = µ1(Q) 2 We say that two quivers Q1 and Q2 are mutation equivalent if one can be obtained from the other by some sequence of quiver mutations. One can check that quiver mutation at vertex k is an involution, so that mutation equivalence is indeed an equivalence relation. De(cid:27)nition 2.4. Fix n ≤ m and let Q = (Q0, Q1) be a quiver with vertices Q0 = {1, 2, ..., n, n + 1, ..., m}. Partition Q0 into the two sets Qmutable = {n + 1, n + 2, ..., m}, which we call the mutable vertices and the frozen vertices, respectively. Fix an am- bient (cid:27)eld F ∼= Q(f1, f2, ..., fn, fn+1, ..., fm). By associating to each vertex i in Q0 the inde- terminate fi, we obtain a seed in F, denoted(cid:0)(f1, f2, ..., fm), Q(cid:1). The variables f1, f2, ..., fn = {1, 2, ..., n} and Qf rozen 0 0 are called cluster variables (or mutable variables), and fn+1, ..., fm are called frozen variables. 8 The n-tuple (f1, f2, ..., fn) is called the cluster of the seed(cid:0)(f1, f2, ..., fm), Q(cid:1), and the m-tuple (f1, f2, ..., fm) is the extended cluster of the seed(cid:0)(f1, f2, ..., fm), Q(cid:1). De(cid:27)nition 2.5. Consider the seed(cid:0)(f1, f2, ..., fm), Q(cid:1). For 1 ≤ k ≤ n, we de(cid:27)ne seed mutation at variable k to be the map on seeds µk whose image (cid:0)(f1, f2, ..., fm), Q(cid:1) =(cid:0)((cid:101)f1,(cid:101)f2, ...,(cid:102)fm), µk(Q)(cid:1) µk is de(cid:27)ned as follows: • If j (cid:54)= k, then (cid:101)fj = fj. • If j = k, then fk and (cid:101)fk are related by the following exchange relation: (cid:89) fk(cid:101)fk = (cid:89) k→t fs + ft. s→k De(cid:27)nition 2.6. Consider the initial seed(cid:0)(x1, x2, ..., xm), Q(cid:1) with initial cluster (x1, x2, ..., xn) (cid:0)(x1, x2, ..., xm), Q(cid:1), and let X be the union of all cluster variables in all seeds in S. Let R = Z[xn+1, ..., xm]. The cluster algebra A = A(cid:0)(x1, x2, ..., xm), Q(cid:1) from the quiver Q is the R- and initial cluster variables x1, x2, ..., xn. Let S be the set of all seeds mutation equivalent to algebra generated by X . The rank of the cluster algebra A is the cardinality n of any of its clusters. Below we state the Laurent Phenomenon in the restricted generality of cluster algebras from quivers. Theorem 2.7. (Theorem 3.1 in [14]) Let A be the cluster algebra from the quiver Q with arbitrary initial seed(cid:0)(x1, x2, ..., xm), Q(cid:1). Then any cluster variable in A can be expressed as a Laurent polynomial in the variables x1, x2, ..., xn, with coe(cid:28)cients in Z. 9 2.2 Cluster Algebras from Surfaces See [12], [9] for details on the topics presented in this section. In particular, we remind the reader that tagged arcs are required for the general discussion but will not be mentioned here. De(cid:27)nition 2.8. An oriented surface Σ with nonempty boundary is called a marked surface if Σ comes equipped with a collection of (cid:27)nitely many marked points on its boundary. De(cid:27)nition 2.9. An arc is any curve inside Σ with endpoints at marked points, considered up to isotopy relative the set of marked points on the boundary of Σ, and such that the relative interior of this curve is disjoint from the boundary of Σ. Any curve beginning and ending at distinct marked points which lies entirely within the boundary of Σ and does not contain any marked points in its interior is called a boundary segment. De(cid:27)nition 2.10. Two arcs in Σ are called compatible if they have isotopy representatives that do not intersect, except possibly at endpoints. An ideal triangulation ∆ is a maximal collection of distinct pairwise compatible isotopy classes of arcs, along with all boundary segments. The arcs of a triangulation cut the surface into ideal triangles. A (cid:30)ip (or Whitehead move) of an ideal triangulation at an arc γ is the process of removing γ from ∆ and replacing it with the unique arc(cid:101)γ that gives another ideal triangulation of Σ (see Figure 6.2). Figure 2.2: Flip inside a quadrilateral It is known that any two ideal triangulations of Σ are connected by a sequence of (cid:30)ips. 10 De(cid:27)nition 2.11. Let Σ be a marked surface. We now construct a cluster algebra A(Σ), called the cluster algebra from the surface Σ, that depends only on Σ. To do this, we construct a quiver whose nodes are in one-to-one correspondence with the collection of arcs and boundary segments of some ideal triangulation ∆ of Σ, and whose arrows form clockwise 3-cycles inside each ideal triangle. This construction does not depend on the choice of ideal triangulation. The correspondences below follow from the construction given in the previous de(cid:27)nition. initial cluster variables of A(Σ) ←→ arcs in ∆ non-initial cluster variables of A(Σ) ←→ arcs in Σ that are not in ∆ frozen variables of A(Σ) ←→ boundary segments of Σ seeds of A(Σ) ←→ triangulations ∆ of Σ seed mutations in A(Σ) ←→ (cid:30)ips of arcs in ∆ 2.3 Cluster Algebras of Finite Type An A type An Dynkin diagram is an undirected graph with n nodes 1, 2, ..., n and one edge between each pair of consecutive nodes i and i + 1 for 1 ≤ i ≤ n − 1. De(cid:27)nition 2.12. A cluster algebra of ((cid:27)nite) type An is any cluster algebra from a quiver Q = (Q0, Q1, s, t) such that the induced subquiver on the mutable vertices Qmutable is mutation equivalent to some orientation of a type An Dynkin diagram. 0 Any cluster algebra from a surface A(Σ) such that Σ is an (n + 3)-gon, i.e. Σ is a closed disc with n + 3 marked points on its boundary, is a rank n cluster algebra of type An. As is the 11 case for general surfaces, cluster variables correspond to arcs in the (n + 3)-gon, frozen variables correspond to the boundary segments, seeds correspond to triangulations, and seed mutations correspond to (cid:30)ips of arcs. Example 2.13. Figure 2.3 below shows one seed of a surface cluster algebra of type A3. Figure 2.3: One seed for A3. 4 7 6 9 8 1 2 3 5 We will use this seed as the basis for a running example to be followed throughout the rest of this text. 12 Chapter 3 Combinatorial Constructions In this chapter, we recall several interrelated objects and constructions naturally occuring in type A cluster combinatorics. The objects found in this chapter are parameterized by binary words. 3.1 Words De(cid:27)nition 3.1. A (binary) word of length n − 1 is a (cid:27)nite string formed from n − 1 choices of elements from the set {a, b}. A word of length n − 1 will be denoted w = w1w2...wn−1 and its length is l(w) = n − 1. The word (cid:124) (cid:123)(cid:122) (cid:125) w = aa··· a k1times (cid:124) (cid:123)(cid:122) (cid:125) bb··· b k2times ··· will be abbreviated w = ak1bk2 ··· . As mentioned above, the constructions that follow are parameterized by the words w. De(cid:27)nition 3.2. A word w is straight if the only letter occurring in w is a, or the only letter occurring in w is b. Conversely, a word is zigzag if neither of the substrings aa nor bb occur in w. Example 3.3. We (cid:27)x the word w = ab for our concrete running example to be followed through- out this section. Note that the word w = ab is zigzag. 13 3.2 Type An Dynkin Quivers Recall that a type An Dynkin diagram is an undirected graph with n nodes 1, 2, ..., n and one edge between each pair of consecutive nodes i and i + 1 for 1 ≤ i ≤ n − 1. We picture any type An Dynkin diagram as shown in Figure 3.1. Figure 3.1: Type An Dynkin diagram 1 2 ··· n Order the nodes 1, 2, ..., n and edges i, i + 1 of any type An Dynkin diagram by 1 < 2 < ... < n and 1, 2 < 2, 3 < ... < n − 1, n, respectively. An orientation of a type An Dynkin diagram is a choice of orientation for each of the n − 1 edges of An. De(cid:27)nition 3.4. A type An Dynkin quiver is a quiver that is mutation equivalent to an orientation of a type An Dynkin diagram. Figure 3.2 shows one of the 2n−1 possible orientations of a Dynkin diagram of type An, each of which is an example of a type An Dynkin quiver (since it is mutation equivalent to itself). Figure 3.2: Orientation of a type An Dynkin diagram 1 2 ··· n De(cid:27)nition 3.5. Let w = w1w2...wn−1 be a word of length l(w) = n − 1, and An the Dynkin diagram of type An with nodes labeled 1, 2, ..., n. The type An Dynkin quiver Aw associated to w is de(cid:27)ned by mapping each wi to the ith edge i, i + 1 of the Dynkin diagram An and declaring that any edge labeled by a becomes oriented i ←− i + 1, and that any edge labeled by b becomes oriented i −→ i + 1. Example 3.6. The word w = ab gives the Dynkin quiver Aw shown in Figure 3.3. 14 Figure 3.3: The Dynkin quiver Aab a 1 2 b 3 Remark 3.7. If the word w is straight then the edges in the Dynkin quiver Aw are all oriented in the same direction. Conversely, if the word w is zigzag then the edges in Aw alternate in orientation. 3.3 Posets The posets we de(cid:27)ne here are called piecewise-linear posets in [1], and zig-zag chains in [25]. De(cid:27)nition 3.8. De(cid:27)ne the poset Cw associated to w to be the Hasse diagram of a poset whose underlying graph is the Dynkin diagram An and covering relations are i (cid:108) j in Cw i(cid:29) i → j in Aw. We visualize the edges of Cw as taking unit diagonal steps upwards. Example 3.9. Figure 3.4 shows the poset Cab. Figure 3.4: The poset Cab 1 a 3 b 2 Remark 3.10. If the word w of length l(w) = n− 1 is straight then the poset Cw is a linear chain with n elements and n − 1 edges. In this case, the covering relations are if w = an−1, or 1 > 2 > 3 > ··· > n 1 < 2 < 3 < ··· < n 15 if w = bn−1. Conversely, if the word w is zigzag, then the poset Cw is a fence or zigzag poset (see [28]) with n elements and n − 1 edges, with covering relations if w = ababa··· , or 1 > 2 < 3 > ··· 1 < 2 > 3 < ··· if w = babab··· . See Figure 3.5 for four examples of a fence poset from a word w. Figure 3.5: Four examples of fence posets Cw ∼= Cab ∼= Caba ∼= Cabab ∼= Cababa 3.4 Triangulations A subquiver Q(cid:48) of the quiver Q is subcollection of nodes and arrows from Q. We say that Q(cid:48) is a complete subquiver if it can be obtained from Q by (cid:27)rst specifying a subcollection of nodes of Q, and then declaring that any arrow from Q which starts or ends at some vertex of this subcollection 16 is also an arrow of Q(cid:48). Form a new quiver Qw, containing Aw as a complete subquiver, by adding n + 3 frozen nodes and 2n + 4 directed edges to and from Aw as follows: • For each edge i, i + 1 in Aw, introduce a node n + i and two directed edges between n + i and the endpoints i and i + 1 of i, i + 1 such that a clockwise 3-cycle is formed. See Figure 3.6. Figure 3.6: Clockwise 3-cycles created from edges in Aw i + n ··· i i + 1··· or ··· i i + 1··· i + n • Add two nodes 2n and 2n + 1 that form a clockwise 3-cycle with the (cid:27)rst node 1 of Aw. This is shown in Figure 3.7. Figure 3.7: Leftmost 3-cycle 2n + 1 2n 1··· • Add two nodes 2n + 2 and 2n + 3 that form a clockwise 3-cycle with the last node n of Aw. If l(w) is odd, or l(w) is even and w ends in a2 or b2, form the 3-cycle shown in Figure 3.8. 17 Figure 3.8: Rightmost 3-cycle, if either l(w) is odd or l(w) is even and w ends in a2 or b2. ··· n 2n + 2 2n + 3 If l(w) is even and w ends in ab or ba, instead form the 3-cycle shown in Figure 3.9. Figure 3.9: Rightmost 3-cycle, if l(w) is even and w ends in ab or ba. ··· n 2n + 3 2n + 2 Example 3.11. Figure 3.10 shows the quiver Qab. Figure 3.10: The quiver Qab 4 1 2 3 5 9 8 7 6 By construction, each quiver Qw comes equipped with an embedding into the plane. We will always consider Qw under this embedding. We can now construct a triangulated polygon from this quiver; nodes of Qw correspond to edges in the triangulation, and each triangle in the triangulation corresponds to the 3-cycle in the quiver which it contains. 18 De(cid:27)nition 3.12. The quiver Qw induces the triangulation ∆w associated to w of the (n + 3)-gon Σ whose elements are the internal diagonals labeled by 1, 2, . . . , n and boundary edges labeled by n + 1, n + 2, . . . , 2n + 3. The ordering of nodes in Aw (cid:44)→ Qw induces an ordering of the internal diagonals δ1 < δ2 < ··· < δn of ∆w. For 1 ≤ i ≤ n − 1, let ∆i be the unique triangle cut out by ∆w such that the two internal diagonals δi and δi+1 are sides of ∆i. Let ∆0 be the unique triangle with sides consisting of two boundary segments and the internal diagonal δ1, and ∆n the unique triangle with sides consisting of two boundary segments and the internal diagonal δn. The ordering of the internal diagonals induces an ordering ∆0 < ∆1 < ··· < ∆n on the triangles ∆i. By construction, the pair of consecutive triangles ∆i−1 and ∆i each has precisely one edge labeled i, and there are no other common labels among their edges. We use the notation Σw = [∆0, ∆1, . . . , ∆n] to indicate that the surface Σ with the triangulation ∆w can be built by suc- cessively gluing ∆i+1 to ∆i along the edge labeled i + 1 for each i. Example 3.13. Figure 3.11 shows the triangulated polygon Σab, with both edge labels i and triangles ∆i indicated (along with the quiver Qab, its edges pictured here with dashed arrows). The quiver Qw induces a type An cluster algebra A(Σ)w with initial extended cluster equal to (x1, x2, . . . , xn, xn+1, . . . , x2n+3). In the next section we assign to any word w a cluster variable in the associated cluster algebra. De(cid:27)nition 3.14. We say that ∆w is a fan triangulation if there exists some vertex v of Σ such 19 Figure 3.11: The triangulated polygon Σab 7 6 ∆0 4 ∆1 2 1 ∆2 5 9 8 ∆3 3 that each internal diagonal δ1, δ2, . . . , δn has v as one of its endpoints. We say that ∆w is a zigzag triangulation if no three internal diagonals share a common endpoint. Remark 3.15. If w is straight, then ∆w is a fan triangulation. Conversely, if w is zigzag, then ∆w is zigzag triangulation. Example 3.16. The triangulation ∆ab shown in Example 3.13 is a zigzag triangulation. Figure 3.12 below shows one example of a fan triangulation. This particular triangulation will be en- countered again later, starting in Chapter 5. Figure 3.12: A fan triangulation 20 3.5 Arcs, Cluster Variables, and Resolutions De(cid:27)nition 3.17. Let A be the vertex of ∆0 that is not an endpoint of edge δ1, and let B be the vertex of ∆n that is not an endpoint of edge δn. Consider the directed arc γw = γA→B from A to B in Σw with initial vertex A and terminal vertex B. We call the arc γw the arc in Σw associated to w. The resulting cluster variable xw is called the cluster variable associated to w. Example 3.18. Figure 3.13 below shows the arc γab and the associated cluster variable xab, pa- rameterized by the word w = ab. Figure 3.13: The arc γab inside Σab, and the associated cluster variable xab xab = x2 2x7x8+x2x5x7x9+x4x5x6x9+x2x4x6x8+x1x3x6x9 x1x2x3 A 1 7 6 4 5 2 γab 3 9 8 B Any cluster variable xw can be written as xw = f (x1, x2, . . . xn) x1x2 . . . xn , where f is a polynomial with coe(cid:28)cients from Z[xn+1, xn+2, . . . , x2n+3]. The (cid:27)rst goal of the remainder of this section is to explain the resolution process given in [19] used to compute the monomials in f, and hence the cluster variable xw. The second goal is to de(cid:27)ne the set Res(w) of resolutions associated to w, and the set Tree(w) of resolution trees associated to w. 21 Fix w and consider the arc γw inside the triangulated polygon Σw. Recall the diagonals of ∆w are δ1, δ2, . . . , δn and that by construction γw crosses each of these n internal diagonals, creating n intersection points in Σw. Call these intersection points pi = γw ∩ δi. To resolve the intersection point pi, we choose a small neighborhood of pi and replace it with a pair of nonintersecting smooth curves in one of two di(cid:29)erent ways, shown below in Figure 3.14. Figure 3.14: Resolution of the intersection point pi pi + Choose one resolution out of the two above for each intersection point pi; this results in a collection of n + 1 nonintersecting curves in Σ. Note that closed curves based at some v ∈ Σ can occur, but that this process never leads to a closed curve that is not attached to some vertex of Σ. De(cid:27)nition 3.19. The set of resolutions Res(w) associated to w consists of those diagrams that can be obtained from resolving each pi in one of the two possible ways, in some chosen order. Each element in Res(w) is weighted as follows. First, replace each arc in r ∈ Res(w) with distinct endpoints with the arc or boundary segment from ∆w that it is isotopic to. Let E(r) be the collection of arcs and boundary segments from ∆w produced from the resolution r, along 22 produce two isotopic arcs. De(cid:27)ne the weight of any resolution r to be xr =(cid:81) with ∅ if any closed loops are present. Note that E(r) is in fact a multiset, since a resolution can j∈E(r) xj, where x∅ = 0. Proposition 3.20. (Proposition 2.1 in [19]) Fix the word w. Consider the arc γw in the triangulated polygon Σw triangulated by ∆w. Then any internal diagonals obtained by a resolution belong to ∆w. The cluster variable xw is equal to xw = (cid:88) 1 x1x2 . . . xn r∈Res(w) xr. We now describe how to produce a resolution tree from w. Each node of such a tree is a diagram of arcs inside the (n + 3)-gon Σ, and is weighted by the product of cluster variables associated to those arcs (or zero if there is a closed loop in the diagram). The root of any resolution tree from w is the diagram consisting of the arc γw inside Σw. Choosing an intersection point pi to resolve at creates two children of this root (see Figure 3.14). If we continue along in this way (choosing an intersection point to resolve at in each child, etc.), and halt whenever we have resolved every intersection point, a binary tree (with additional node structure) is produced. De(cid:27)nition 3.21. The set of resolution trees Tree(w) associated to w is the set whose elements are the binary resolution trees from w as described above. Note that Res(w) is equal to the union of the leaves of the trees in Tree(w). Example 3.22. The (cid:27)gure below shows one element of Tree(w) for the word w = ab. Although our construction of arcs seems restrictive, the next lemma shows that there is in fact no loss of generality. 23 Figure 3.15: One element of Tree(ab) f = x1x2x3xγ γ1 x2x3xγ1x7 x2x3xγ2x6 γ2 + ... f = x2 2x7x8 + x2x5x7x9 x4x5x6x9 x2x4x6x8 + + + x1x3x6x9 Lemma 3.23. Any cluster variable associated to an arc in a polygon can be computed as xw for some word w. Proof. Let ν be an arc in the triangulated polygon Σ∆, triangulated by ∆. If ν crosses every internal diagonal in ∆, then we are done. Otherwise, we work inside the triangulated subpolygon Σ(cid:48) in Σ∆ obtained by deleting from ∆ any edge that is not an edge of some triangle crossed by ∆ ν. Furthermore, we “freeze” any edge η bordering a deleted triangle, meaning we disallow this arc to be (cid:30)ipped, so that also xη cannot be mutated. Figure 3.16: An arc in a triangulated subpolygon Σ∆ η ν The result now follows by noting that any arc obtained by resolving ν will be contained entirely within the triangulated subpolygon just mentioned. 24 3.6 Snake Graphs De(cid:27)nition 3.24. The snake graph Gw associated to w is the labeled planar graph recursively de(cid:27)ned by the procedure given below. 1. Choose an orientation-preserving embedding of the triangulated square [∆0, ∆1] into the discrete plane Z2 such that its image (cid:101)T1 is a triangulated unit square with vertices (0, 0), (1, 0), (0, 1), and (1, 1) in Z2, and such that the point A ∈ ∆0 maps to the point (0, 0). Note that the (line spanned by the) image of the triangulating edge will have slope −1. 2. Choose an orientation-reversing map of [∆1, ∆2] into Z2 such that its image (cid:101)T2 is a trian- gulated unit square (again, with triangulating edge having slope −1) glued to (cid:101)T1 along the unique edge in each labeled j ∈ {n + 1, ..., 2n + 3}. 3. Continue this process, using orientation-preserving maps for i odd and orientation-reversing all triangulating edges having slope −1) glued either above or to the right of the previous maps for i even, to get the graph (cid:102)Gw, built from triangulated unit squares (cid:101)Ti in Z2 (with square. Each (cid:101)Ti will be called a tile of (cid:102)Gw. The triangulating edge of each (cid:101)Ti is called the diagonal of (cid:101)Ti. (cid:102)Gw. Let Ti be the tile (cid:101)Ti after its diagonal has been removed. We will call Ti a tile of Gw. We will 4. The snake graph Gw is the graph in Z2 gotten by deleting each diagonal from each tile in often refer to the corners (SW, SE, NE, NW) and edges (S,E,N,W) of a tile Ti as indicated in the next (cid:27)gure. 25 Figure 3.17: Shorthand to describe the corners and edges of a tile Ti NW W SW N Ti S NE E SE Order the tiles of Gw by T1 < T2 < ··· < Tn. A boundary edge of Gw is any edge of Gw not occurring as a shared edge between any two of its consecutive tiles. Any edge that is not a boundary edge (i.e., each gluing edge) will be called an internal edge of Gw. Let the internal edges of Gw be labeled e1, e2, . . . , en−1, where ei is the gluing edge between tiles Ti and Ti+1. De(cid:27)nition 3.25. A snake graph Gw is called straight if all of its tiles lie in a single row or column. A snake graph is called zigzag if no three consecutive tiles are straight. Example 3.26. In Figure 3.18, we illustrate the construction of the (straight) snake graph Gab associated to the (zigzag) word w = ab. Remark 3.27. It follows easily from the constructions that a straight word w yields a fan trian- gulation ∆w (see Remark 3.16), which in turn results in a zigzag snake graph Gw. Conversely, a zigzag word w yields a zigzag triangulation ∆w, which gives a straight snake graph Gw. Remark 3.28. The de(cid:27)nition we have given for building a snake graph from a triangulated sur- face is essentially a process called unfolding. Conversely, any snake graph from a surface can be folded back up to reconstruct the surface. Later, it will be convenient to use the folding/unfolding maps to relate certain expansions to others. For details see [29]. Figure 3.19 below illustrates the folding and unfolding maps. De(cid:27)nition 3.29. Fix a word w and the snake graph Gw. Form a word sh(Gw) of length n − 1, called the shape of the snake graph Gw, by letting i run through 1, 2, . . . , n in the following rule: 26 Figure 3.18: Construction of the snake graph Gab 1 7 6 1 2 4 2 4 5 2 5 T ile 1 3 T ile 2 9 8 3 T ile 3 7 1 2 4 6 5 4 9 5 2 3 8 Remove Diagonals Figure 3.19: The folding and unfolding maps unf olding = f olding 8 3 2 2 1 7 9 5 4 6 remove/add diagonals If tile Ti+1 is glued to the right of tile Ti, write the letter a, and if tile Ti+1 is glued to the top of tile Ti, write the letter b Example 3.30. The shape of the snake graph for the word w = ab is sh(Gw) = bb. Remark 3.31. If w is straight then Gw is zigzag (see Remark 3.27) and so sh(Gw) is zigzag. Conversely, if w is zigzag then Gw is straight and hence sh(Gw) is straight. 27 De(cid:27)nition 3.32 and De(cid:27)nition 3.34 below will be used in the next section to de(cid:27)ne the con- tinued fraction associated to a word. Recall that Gw has an embedding into Z2 such that the (cid:27)rst tile T1 of Gw has vertices (0, 0), (1, 0), (0, 1), and (1, 1). Additionally, recall that each tile Ti of Gw is glued either above or to the right of the previous tile Ti−1. Informally, the snake graph Gw “goes up and to the right”. De(cid:27)nition 3.32. (see [5]) Fix the word w and the associated snake graph Gw. Let x and y be the names of the coordinate functions on Z2. Note that the midpoint me of each edge e in Gw lies 2) for j ∈ Z. The sign function s on Gw is on precisely one of the diagonal lines y = x + (j + 1 the function on the edges e of Gw to the set {−, +} de(cid:27)ned by  −, +, s(e) = if me lies on y = x + (j + 1 if me lies on y = x + (j + 1 2) for j even 2) for j odd. Example 3.33. The construction of the sign function s on Gab is shown below in Figure 3.20. Figure 3.20: The sign function s on Gab For  ∈ {−, +}, de(cid:27)ne 28 + if  = − − if  = +. − = Recall the internal edges of Gw are labeled e1, . . . , en−1. Let e0 be the S edge of the (cid:27)rst tile T1 of Gw. Suppose that Gw has three or more tiles. In this case, the de(cid:27)nition of en depends on the shape of the last three tiles of Gw. If the last three tiles are straight, then en is de(cid:27)ned to be whichever edge in Tn that is across from en−1 (so that s(en) = −s(en−1)). If instead the last three tiles of Gw form a zigzag snake graph, then the edge en is either the N or E edge in Tn, whichever is adjacent to en−1 (thus, s(en) = s(en−1)). If Gw has two tiles, we choose en = e2 to be the N edge of the last tile of Gw. If Gw has one tile, then en = e1 is the edge across from e0. De(cid:27)nition 3.34. (see [5]) Fix the word w, the associated snake graph Gw, and the sign function s on the edges of Gw. The sign sequence sw associated to the word w is the sequence sw = (s(e0), s(e1), . . . , s(en)). Example 3.35. For w = ab the associated sign sequence is sab = (−, +,−, +). Figure 3.21: The sign sequence sab on Gab 29 3.7 Continued Fractions In [5] (see also [6], [26]), connections between cluster algebras, continued fractions, and snake graphs were established. We review some of the basic de(cid:27)nitions found there, and use them to de(cid:27)ne the continued fraction associated to a word w. De(cid:27)nition 3.36. Fix k1 ∈ Z and for 2 ≤ i ≤ d (cid:27)x the positive integers ki ∈ Z. A (cid:27)nite continued fraction, denoted by [k1, k2, . . . , kd] is an expression of the form k1 + k2 + 1 1 k3 + . 1 . . . + 1 kd Say that the continued fraction [k1, k2, . . . , kd] is positive if ki > 0 for every i. From now on we will only consider positive continued fractions. De(cid:27)nition 3.37. Fix a word w of length n − 1, along with the snake graph Gw. Recall the sign sequence sw = (s(e0), . . . , s(en)) of Gw, and our convention that s(e0) = −. Let  = −. De(cid:27)ne positive integers k1, ..., kd as indicated below. sw = (s(e0), . . . , s(en)) = (, , . . . ,  k1 times (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) k2 times (cid:125) (cid:124) ,−,−, . . . ,− , . . . , (−1)k, (−1)k, . . . (−1)k ). (cid:123)(cid:122) times kd (cid:125) De(cid:27)ne the ((cid:27)nite, positive) continued fraction CF(w) associated to w to be CF(w) = [k1, k2, . . . , kd]. Remark 3.38. By Theorem A in [5] (which we recall as Theorem 4.5 below), simplifying the continued fraction CF(w) gives a rational number in lowest terms that is greater than 1. 30 Example 3.39. The continued fraction CF(ab) is equal to 5 is sab = (−, +,−, +), so that 3 . Indeed, the associated sign sequence CF(ab) = [1, 1, 1, 1] = 1 + 1 1 = 5 3 . 1 + 1 + 1 1 Remark 3.40. Suppose the word w is either straight or zigzag, and that its length is l(w) = n − 1. By Remark 3.31, this implies that sh(Gw) is either zigzag or straight, respectively. Let the Fibonacci numbers be denoted by F1 = 1, F2 = 1, F3 = 2, etc. Consider the continued fraction CF(w). (a) If sh(Gw) is the straight word sh(Gw) = an−1 then (cid:124) (cid:123)(cid:122) (cid:125) CF(w) = [2, 1, . . . , 1 n−1 times ] = (b) If sh(Gw) is the straight word sh(Gw) = bn−1 then (cid:125) CF(w) = [1, 1, 1, . . . , 1 n+1 times (cid:123)(cid:122) (cid:124) Fn+2 Fn . Fn+2 Fn+1 . ] = (c) If sh(Gw) is the zigzag word sh(Gw) = bab··· then CF(w) = [1, n] = n+1 n . (d) If sh(Gw) is the zigzag word sh(Gw) = aba··· then CF(w) = [n] = n 1 = n. 31 3.8 Distributive Lattices De(cid:27)nition 3.41. Let D be a (cid:27)nite poset. The meet of the elements p ∈ D and q ∈ D is the unique element denoted p ∧ q ∈ D (if it exists) that satis(cid:27)es: (a) p ∧ q ≤ p and p ∧ q ≤ q, and (b) if there exists some r ∈ D such that r ≤ p and r ≤ q, then r ≤ p ∧ q. The join of p and q is the unique element p ∨ q ∈ D (if it exists) that satis(cid:27)es: (a) p ∨ q ≥ p and p ∨ q ≥ q, and (b) if there exists some r ∈ D such that r ≥ p and r ≥ q, then r ≥ p ∨ q. We say D is a lattice if for any two elements p, q ∈ D, both p ∧ q and p ∨ q exist. Remark 3.42. Let D be a (cid:27)nite poset. An element m ∈ D is called a minimal element if there does not exist d ∈ D such that d < m. Similarly, an element M ∈ D is called maximal if there does not exists d ∈ D such that M < d. If D has a unique minimal (resp., maximal) element, then we call it the minimum (resp., maximum) element. It is easy to see that every (cid:27)nite lattice has a minimum element and a maximum element. De(cid:27)nition 3.43. Suppose that the (cid:27)nite poset D is a lattice. We say D is a distributive lattice if for all p, q, r ∈ D the following two distributive laws hold: (a) p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) (b) p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r). De(cid:27)nition 3.44. Let C be a (cid:27)nite poset. An order ideal I of C is a subset of C such that if p ∈ I and q ∈ C with q < p, then q ∈ I. We denote by I(C) the poset (ordered by inclusion) of order ideals of C. 32 Example 3.45. The poset of order ideals of a fence on n vertices is called a Fibonacci cube of order n. We will denote the order ideals of Cw for l(w) = n − 1, w = aba··· by Γn. Alternatively, the Fibonacci cube of order n may be de(cid:27)ned as a graph, with vertices those binary words from {a, b} with n bits that do not contain two consecutive instances of the bit b. There is an edge between two vertices if they di(cid:29)er by precisely one bit in the same position. For original references, see [22] and [23]. For a somewhat recent survey on Fibonacci cubes, see [24]. Figure 3.22 below shows the Fibonacci cubes which result from computing the poset of order ideals on each of the four zigzag posets shown in Figure 3.5. Figure 3.22: Four Fibonacci cubes Γ3 Γ4 Γ5 Γ6 De(cid:27)nition 3.46. Let D be a (cid:27)nite lattice. An element r ∈ D is said to be join-irreducible if r is not the unique minimum element of D (see Remark 3.42) and there do not exist two elements p, q ∈ D with p < r, q < r, and r = p∨ q. We denote by J (D) the poset (with the induced order) of join-irreducible elements of D. Theorem 3.47. (see [2]) Let D be a (cid:27)nite lattice. Let C = J (D) be the poset of join-irreducibles of D. Then D is a distributive lattice if and only if D is isomorphic to I(C). By Theorem 3.47, I(Cw) is a distributive lattice for any word w. 33 De(cid:27)nition 3.48. The distributive lattice Dw associated to w is de(cid:27)ned by Dw = I(Cw). Example 3.49. The distributive lattice Dab is isomorphic to the Fibonacci cube Γ3, shown as the leftmost poset in Figure 3.22. 34 Chapter 4 Expansion Posets Fix a word w of length l(w) = n − 1 and the associated objects de(cid:27)ned in the previous chapter. The goals of this chapter are as follows: (1) Recall three known combinatorial interpretations of the terms in the Laurent expansion of any cluster variable xw parameterized by the arc γw. (2) Equip each such representation with a poset structure. 4.1 Perfect Matchings of Snake Graphs It is easy to see that any snake graph with n tiles has an even number 2(n + 1) of vertices. De(cid:27)nition 4.1. A perfect matching P of the snake graph Gw is a choice of n + 1 edges in Gw such that each vertex of Gw is the endpoint of exactly one edge e in P. P is de(cid:27)ned to be the product of initial cluster variables xP =(cid:81) The weight of the edge e is the initial cluster variable xe. The weight of a perfect matching e∈P xe. Let Pw be the set of all perfect matchings of the snake graph Gw. Example 4.2. Figure 4.1 shows one perfect matching P− (see De(cid:27)nition 4.6 and Figure 4.4 below for the notation P−) of the snake graph Gab. The weight of this perfect matching is x1x3x6x9. 35 Figure 4.1: The perfect matching P− on Gab 1 9 6 3 Theorem 4.3. (Theorem 3.1 in [29]) Let w be any word, and consider the set Pw of perfect matchings on the snake graph Gw. Then the cluster variable xw can be written as the sum (cid:88) xw = 1 x1x2 . . . xn P∈Pw xP . Example 4.4. Figure 4.2 below shows the (cid:27)ve perfect matchings on the snake graph Gab. Note that summing over the weights of these perfect matchings gives the cluster variable xab displayed in Figure 3.13. Consider the word w, the snake graph Gw, and the associated continued fraction CF(w) = w be the subsnake graph of Gw obtained from w is de(cid:27)ned to be a line segment, with one perfect w be the perfect matchings on Gc [a1, a2 . . . ak]. For any c such that 0 ≤ c < n, let Gc Gw by deleting its (cid:27)rst c tiles. If c = n, then Gc matching. Denote the cardinality of the set Pw by |Pw|. Let Pc and |Pc w| the cardinality of the set Pc w. w 36 Figure 4.2: The (cid:27)ve perfect matchings on Gab 2 8 4 6 9 5 7 2 8 2 3 2 7 1 9 5 4 6 9 6 Theorem 4.5. (Theorem 3.4 in [5]) For any word w, its associated continued fraction CF(w) is equal to the quotient of cardinalities CF(w) = and the fraction on the right hand side is reduced. |Pw| (cid:12)(cid:12)(cid:12)Pa1 (cid:12)(cid:12)(cid:12) , w We now give the set Pw a poset structure. Let P ∈ Pw. A twist of P at tile i is the local move that takes two edges in P that are located opposite one another on tile Ti of Gw and replaces them with the remaining two edges of Ti. Directly below is the local picture for the twist at a generic tile Ti. 37 Figure 4.3: Twist of a perfect matching at tile Ti Ti Ti An up-twist at tile Ti is a twist that meets the twist-parity condition (see Theorem 5.4 in [31]): (1) If i is odd, the horizontal edges of Ti are replaced with the vertical edges of Ti, or (2) If i is even, the vertical edges of Ti are replaced with the horizontal edges of Ti. De(cid:27)nition 4.6. The minimal matching P− of Pw is the unique perfect matching of Gw such that every edge in P− is a boundary edge of Gw and the S edge of tile T1 is in P−. The maximal matching P+ of Pw is the unique perfect matching of Gw such that every edge in P+ is a boundary edge of Gw and the S edge of tile T1 is not in P+. De(cid:27)nition 4.7. De(cid:27)ne a poset structure on Pw as follows. The unique minimal element of Pw is the minimal matching P−, and the unique maximal element is P+. A perfect matching P2 covers a perfect matching P1 if there exists a tile Ti such that P2 can be obtained from P1 by performing a single up-twist of P1 at Ti. Example 4.8. The poset Pab of perfect matchings on the snake graph Gab is shown below in Figure 4.4. Note that Pab is isomorphic to the Fibonacci cube Γ3. The sum of the weights attached to each perfect matching gives the cluster variable xab shown in Example 3.13. 38 Figure 4.4: The poset Pab 2 8 4 6 9 5 7 2 8 2 3 2 7 1 9 5 4 6 9 6 Remark 4.9. Let the length of w be l(w) = n − 1. (a) The poset of perfect matchings Pw on a zigzag snake graph Gw is isomorphic to a linear chain with n + 1 elements and n edges. (b) The poset of perfect matchings Pw on a straight snake graph Gw of shape sh(Gw) = bn−1 is isomorphic to the Fibonacci cube Γn. If instead Gw is the horizontal straight segment with n tiles, then Pw is the order-theoretic dual of Γn. 4.2 Perfect Matchings of Angles Fix a word w of length l(w) = n − 1. By the constructions above, this choice determines the arc γw = γA→B in the triangulated (n + 3)-gon Σw. Recall the notation Σw = [∆0, ∆1, . . . , ∆n]. 39 De(cid:27)nition 4.10. Any angle o of the triangle ∆i is incident to its vertex. A perfect matching α of angles in Σw is a selection of n + 1 angles from the triangles ∆0, ∆1, . . . , ∆n of Σw, one per triangle, such that (1) Each angle is incident to an endpoint of one of the internal diagonals δ1, δ2, . . . , δn. (2) No two angles are incident to the same vertex of the polygon Σ. of o. The weight of α is de(cid:27)ned to be the product of initial cluster variables xα =(cid:81) The weight of each angle o in ∆i is the cluster variable xo associated to the edge of ∆i opposite o∈α xo. Let Aw be the set of all perfect matchings of angles in Σw. Example 4.11. Shown in Figure 4.5 is one perfect matching of angles in Σab (in fact, it is the min- imal matching α−, explained below). Selecting an angle to be included in a particular matching is visualized by placing a ball “close” to that angle inside the appropriate triangle. Figure 4.5: The perfect matching of angles α− on Σab. 9 1 3 6 Note that the weight x1x3x6x9 of this element is the same as the weight of the snake graph perfect matching shown in Example 4.1. Theorem 4.12. (Theorem 1.2 in [43]) Let w be any word, and consider the set Aw of perfect match- ings of angles on the triangulated surface Σw. Then the cluster variable xw can be written as (cid:88) xα. xw = 1 x1x2 . . . xn α∈Aw 40 De(cid:27)nition 4.13. An angle is incident to the two arcs in ∆w which are sides of that angle. By a boundary angle of Σw, we mean any angle of Σw that is incident to exactly one boundary edge of ∆w. Any angle that is neither incident to A or B, nor a boundary angle, will be called an internal angle. We now give the set Aw a poset structure. Let α ∈ Aw. A twist of α at diagonal δi is the local move that takes two angles in α incident to opposite vertices of the same internal diagonal i and replaces them with the remaining two angles incident to δi. Directly below is the local picture for the twist at diagonal δi. Figure 4.6: Twist of a perfect matching of angles at diagonal δi i i If were traverse γA→B from A to B, we obtain a partition of {vertices of Σ}−{A, B} in two sets; those vertices which are to the left of γA→B, and those vertices of Σ to the right of γA→B. Let li be the endpoint of i to the left of γA→B, and ri the endpoint to the right. A twist at δi is an up-twist if the angle from ∆i incident to ri is replaced with the angle incident to li, and the angle from ∆i−1 incident to li is replaced with the angle incident to ri. De(cid:27)nition 4.14. The minimal matching α− of Aw is the unique perfect matching of angles in Σw such that the boundary angle in ∆0 with boundary edge δ2n+1 is included in α−, and only boundary angles are used in α−. The maximal matching α+ is the unique perfect matching of 41 angles in Σw such that the boundary angle in ∆0 with boundary edge δ2n is included in α+, and only boundary angles are used in α+. De(cid:27)nition 4.15. The poset structure on Aw is de(cid:27)ned as follows. The unique minimal element of Aw is the minimal matching α−, and the unique maximal element is α+. A perfect matching of angles α2 covers a perfect matching of angles α1 if there exists a diagonal δi such that α2 can be obtained from α1 by performing a single up-twist of α1 at δi. Remark 4.16. Alternatively, α− can be de(cid:27)ned by the following min-condition, found in [42]. At each vertex v of Σw, order the angles incident to v in counterclockwise order around v. For each vertex v of the triangulated polygon Σw that is incident to at least one internal diagonal of ∆w, the angle o ∈ α− at v is the (cid:27)rst angle at v. Similarly, a max-condition (replace “counterclockwise” with “clockwise” in the above) can be used to de(cid:27)ne α+. Figure 4.7 shows the poset of perfect matchings of angles in Σab. This poset is isomorphic to the one given in Example 4.4, and one can check that the respective weights coincide as well. Figure 4.7: The poset Aab 9 7 2 5 4 2 8 6 8 9 9 7 2 2 6 6 4 5 1 3 42 4.3 T -Paths Recall that the internal diagonals of ∆w are labeled 1, 2, . . . , n and are ordered δ1 < δ2 < ··· < δn, and the notation for the intersection points pi = γw ∩ δi. De(cid:27)nition 4.17. A T -path from A to B, denoted T = (T1, T2, . . . , Tl(T )), is an ordered selec- tion of bicolored (either blue or red) edges from the triangulation ∆w subject to the following conditions: 1. The edges in T form a path from A to B. 2. The number of edges l(T ) in T is odd (we call l(T ) the length of the T-path). 3. The odd-indexed edges in T are all colored blue, and the even-indexed edges in T are all colored red. 4. All edges in T are distinct. 5. Every red edge in T crosses γA→B. 6. If δi and δj are two internal diagonals of the triangulation that γA→B crosses and i < j then the crossing point of δi and γA→B is closer to a than the crossing point of δj and γA→B. For any T ∈ Tw let T blue be the set of blue edges from T, and let T red be the red edges from T. De(cid:27)ne the weight xT of T by (cid:89) (cid:89) r∈T red x−1 r . xT = xb b∈T blue Let Tw be the set of all T-paths from A to B. 43 Example 4.18. Figure 4.8 shows one T-path on the triangulation Σab (in fact, it is the minimal T - . Note that multiplying this weight path T−, explained below). The weight of this T-path is x6x9 x2 by x1x2x3 gives x1x3x6x9, the weight of the elements in Example 4.1 and Example 4.5. Figure 4.8: The T-path T− with edges from ∆ab b r b Theorem 4.19. (Theorem 1.2 in [36]) Let w be any word, and consider the set Tw of T -paths on the triangulated surface Σw. Then the cluster variable xw can be written as (cid:88) T∈Tw xw = xT . We now give the set Tw a poset structure. Let T ∈ Tw and let T = (T1, T2, . . . , Tl(T )) be a T-path. Pick a red edge Tr from T, which necessarily has as its underlying edge an internal diagonal of ∆w. The two triangles ∆i and ∆i+1 from Σw that are glued along the underlying edge of Tr determine a triangulated quadrilateral [∆i, ∆i+1] with diagonal Tr. De(cid:27)ne a twist of T to be the local move that colors the four (non-triangulating) sides of the quadrilateral [∆i, ∆i+1] as follows: two edges of [∆i, ∆i+1] that are opposite one another are colored blue, the other two edges are colored red, and uncolored boundary edges in ∆w are not allowed to be colored red. Here, if a red edge is colored blue then the colors cancel one another and that edge is not used in the resulting T-path, and similarly for if a blue edge is colored red [21]. Directly below is the local picture for the T-path twist at diagonal δi. 44 Figure 4.9: Twist of a T-path at diagonal δi r i r r b b r i Remark 4.20. It is not obvious that a twist of a T-path is always de(cid:27)ned. Figure 4.10 shows the eight possibilities for how any T-path looks locally at an internal diagonal which is not the (cid:27)rst or last. In each quadrilateral shown, the top and bottom edges are boundary edges, the other three are internal diagonals, and the dotted lines can be either, as long as a red edge is not on the boundary. Each of the four arrows indicate when two T-paths are related by a twist. Figure 4.10: T-path twists at internal diagonals are always de(cid:27)ned b r r r b r b b r r b b r r b b b b r r b r b r b r r r r b r r b b r b b b b 45 Thus, twists are well-de(cid:27)ned for any diagonal that isn’t the (cid:27)rst or last. A similar analysis shows twists are always de(cid:27)ned for the (cid:27)rst and last diagonals, as well. Let ui−1 and di−1 be the two edges of ∆i−1 that are not equal to δi, such that ui−1 is adjacent to li, and di−1 is adjacent to ri. Let the two edges ui and di of ∆i be de(cid:27)ned similarly. A twist at δi is an up-twist if it colors di−1 and ui red, and colors di and ui−1 blue. Recall that the sides of the (cid:27)rst triangle ∆0 of Σw are labeled 1 −→ 2n −→ 2n + 1 −→ 1 in clockwise order. The minimal element T− of Tw is the unique T-path that starts with the blue edge δ2n and uses only internal diagonals for its edges, except for the (cid:27)rst and last boundary edges. The maximal element T+ of Tw is the unique T-path from A to B that starts with the blue edge δ2n+1 and uses only internal diagonals for its edges, except for the (cid:27)rst and last boundary edges. De(cid:27)nition 4.21. The poset structure on Tw is de(cid:27)ned as follows. The unique minimal element of Tw is T−, and the unique maximal element is T+. A T-path T2 covers a T-path T1 if there exists a diagonal δi such that T2 can be obtained from T1 by performing a single up-twist of T1 at diagonal δi. Example 4.22. Figure 4.11 shows the poset Tab of T-paths from A to B associated to the word w = ab. 46 Figure 4.11: The poset Tab b r b r b r b r b b r b r b b b r b b r b r r b b If we sum over the weights of this poset, we obtain xab = x6x9 x2 + x4x5x6x9 x1x2x3 + x5x7x9 x1x3 + x4x6x8 x1x3 + x2x7x8 x1x3 . If we (cid:27)nd a common denominator for the (cid:27)ve terms in this sum, we see that this expression for xab is equivalent to the one given in Example 3.13. 4.4 Expansion Isomorphisms The three expansion posets Pw, Aw, and Tw are each isomorphic to a linear chain when w is straight, and are each isomorphic to a Fibonacci cube when w is zigzag. In general, the three posets de(cid:27)ned in this chapter are isomorphic to one another when they are parameterized by the same word. In Proposition 4.23, we recall explicit isomorphisms between these posets which respects the additional node structure present in each (see [43] and N[29]). 47 Proposition 4.23. Fix the word w. Then there is a commutative diagram of poset isomorphisms Pw Aw Tw which each respect the additional node structure of each poset. Proof. Let α((cid:102)Gw) be the angles from (cid:102)Gw which are incident to a diagonal of (cid:102)Gw, i.e., those angles which are neither the angle incident to the SW corner of(cid:102)T1 nor the angle incident to the NE corner of (cid:102)Tn. By Lemma 3.2 in [43] there is a bijection between the edges in Gw and the set identifying certain pairs of angles in α((cid:102)Gw). The pairs of angles that are identi(cid:27)ed are those that of (cid:102)Gw. Any pair of angles in α((cid:102)Gw) which have been identi(cid:27)ed correspond to a single internal of angles α(Σw) in Σw which are neither incident to A nor B. This bijection is induced by are opposite one another in the quadrilateral determined by the diagonals of two consecutive tiles angle in α(Σw). By [43], the bijection above induces a set bijection Pw ∼=−→ Aw. Hence to see it is an isomor- phism of posets, we must only show that covering relations are preserved. To that end, suppose the perfect matching P2 covers P1, and that α1 is the image of P1 and α2 is the image of P2. angles in α((cid:102)Gw). Now via the orientation-preserving map (cid:101)Ti By de(cid:27)nition, P1 and P2 are related by a twist at some tile Ti. Suppose that i is odd. Then by the twist-parity condition, the up-twist at tile i exchanges the two horizontal edges of Ti with the remaining two vertical edges of Ti. Represent these two pairs of edges by their corresponding ∼−→ [∆i−1, ∆i] we see that α2 is obtained from α1 by an up-twist at diagonal δi. Thus the map in question is a poset isomorphism. If instead i is even, then an up-twist replaces vertical edges with horizontal ones. An argument similar to the above shows the map Pw −→ Aw still preserves covering relations in this case, keeping in mind that now we must reverse orientation to go between (cid:101)Ti and [∆i−1, ∆i]. 48 It is clear that this poset isomorphism preserves node weights. Thus, there is a structure- preserving poset isomorphism Pw ∼−→ Aw, as claimed. It is known that there is a set bijection Pw −→ Tw (see Remark 3.8.9 in [20] and Theorem 4.4 in [29]). This map can be described as follows. First, we fold Gw, keeping track of the images of the edges from P ∈ Pw under each fold, to obtain a multiset of n + 1 diagonals and boundary segments in ∆w (note that folding may send two distinct edges of P to the same internal diagonal of ∆w). We consider each such edge colored blue. Now, we superimpose a red edge on top of each internal diagonal in the diagram that is the union of ∆w and the multiset just mentioned, deleting any pair of opposite colored edges with the same underlying (internal) diagonal. The result of this process is a T-path from A to B. The proof that this map is indeed a structure-preserving isomorphism of posets is similar to ∼−→ Aw has these properties. The only di(cid:29)erence to note is that the , which corresponds to the superimposi- the proof that the map Pw weights of the nodes in Tw are all multiplied by tion of the n red edges. 1 x1...xn Now de(cid:27)ne the last map Aw −→ Tw to be the composition that (cid:27)rst applies the inverse of Pw −→ Aw to a perfect matching of angles, and then applies the map Pw −→ Tw. By the above discussion, this map has the desired properties. This completes the proof. Example 4.24. We illustrate two of the maps in Proposition 4.23 with the three posets associated to the word w = ab from our running example. The map Pab −→ Aab is de(cid:27)ned by taking the preimage of each edge in a perfect matching P ∈ Pab under the surjection from α((cid:103)Gab) to the edges in Gab, and then folding the result. 49 Figure 4.12: The map Pab −→ Aab via angle identi(cid:27)cation and folding f old each node The second map Aw −→ Tw is de(cid:27)ned by sending each angle in a matching α ∈ Aab to the edge in ∆w it is opposite of, and then coloring each internal diagonal red. Figure 4.13: The map Aab −→ Tab via diagonal coloring and cancellation 2 color diagonals red cancel Example 4.25. Figure 4.14 shows explicitly the application of the composition of bijections Pab −→ Aab −→ Tab −→ Pab to the input P− ∈ Pab. 50 Figure 4.14: The composition Pab −→ Aab −→ Tab −→ Pab restricted to minimal elements P− α− = T− = 51 Chapter 5 Dual Combinatorial Constructions 5.1 Words For any wi ∈ {a, b}, let w∗ i ∈ {a, b} be the image of wi under the involution a ←→ b. De(cid:27)nition 5.1. Let w = w1w2 . . . wn−1 be a word of length n− 1. The dual word w∗ is the word of length n − 1 de(cid:27)ned by w∗ = w∗ 5 ··· 1w2w∗ 3w4w∗ Example 5.2. The dual of the word w = ab is w∗ = a∗b = bb. Remark 5.3. The dual of a straight word w is a zigzag word w∗ and vice versa. 5.2 Type An Dynkin Quivers De(cid:27)nition 5.4. Let Aw be the Dynkin quiver associated to the word w. The dual Dynkin quiver A∗ w is obtained by reversing the orientation of every other edge of Aw, starting with the (cid:27)rst. The next result is clear from the de(cid:27)nitions. Proposition 5.5. For any word w, we have A∗ w = Aw∗. Example 5.6. In Figure 5.1, the Dynkin quiver Aab is shown on the left, and the dual Dynkin quiver A∗ w = Aw∗ = Abb is shown on the right. 52 Figure 5.1: The quiver Aab and its dual Abb a 1 2 b 3 1 b b 2 3 5.3 Posets Recall the poset Cw associated to the word w. De(cid:27)ne the orientation of an edge in Cw to be either NW or NE, according to whether it is labeled by a or b, respectively. De(cid:27)nition 5.7. The dual poset C∗ Cw, starting with the (cid:27)rst. w is de(cid:27)ned by changing the orientation of every other edge of Caution: The term "dual poset" is commonly used for the poset obtained from Cw by reversing all covering relations. Whenever we refer to the latter, we use the term "order-theoretic dual" to avoid confusion. Proposition 5.8. For any word w, we have C∗ w = Cw∗. Example 5.9. The leftmost poset in Figure 5.2 is the poset Cab (see Figure 3.4), and on the right is the dual poset C∗ w = Cw∗ = Cbb. Figure 5.2: The poset Cab and its dual Cbb 1 a 3 b 2 3 b 2 b 1 Remark 5.10. If w is straight then Cw is isomorphic to a linear chain, and the dual poset C∗ isomorphic to a fence. w is 53 5.4 Triangulations Recall the notation Σw = [∆0, ∆1,··· , ∆n], where ∆i are the ideal triangles (with edge labels from De(cid:27)nition 3.12) cut out by the triangulation ∆w of Σ. Let ∇i be the edge-labeled triangle with the same positive integer labels as ∆i but with opposite orientation. De(cid:27)ne the triangle map by the assignment Σw = [∆0, ∆1, . . . , ∆n] (cid:55)→ [∆0,∇1, ∆2,∇3, ∆4, . . . ]. De(cid:27)ne the image of this map to be Σ∗ w. De(cid:27)nition 5.11. Consider the triangulation ∆w of Σ associated to w. The dual triangulation ∆∗ of Σ is the triangulation of Σ obtained by application of the triangle map Σw (cid:55)→ Σ∗ w. w = ∆∗ Example 5.12. Fix w = ab. Figure 5.3 shows how the dual triangulation ∆∗ built by applying the triangle map to Σab. ab = ∆bb is w Figure 5.3: The triangle map applied to Σab gives Σbb ∇3 ∇1 Σw = 7 6 1 4 2 5 3 9 8 4 7 6 = ∆0 1 1 2 2 5 ∆1 3 3 9 8 ∆2 ∆3 triangle map 7 6 ∆0 1 1 2 4 8 9 2 5 3 3 ∆2 = 6 7 1 4 8 3 5 2 = Σ∗ w 9 The next result again follows from the constructions given thus far. Proposition 5.13. For any word w, we have Σ∗ w = Σw∗ and ∆∗ w = ∆w∗. Remark 5.14. If w is straight then ∆w is a fan triangulation and the dual ∆∗ gulation. Conversely, if w is zigzag then ∆w is a zigzag triangulation and the dual ∆∗ triangulation. w is a zigzag trian- w is a fan 54 Application of the triangle map to Σw gives a new seed for a cluster algebra A(Σ)w∗ isomor- phic to A(Σ)w. If the new initial variable yi is attached to the arc labeled i in Σ∗ w, we relabel this arc with the variable xi. This combinatorial relabeling is introduced so that when we compute cluster variables attached to arcs in the dual triangulation, the result is a Laurent monomial in the initial cluster variables from the original seed. 5.5 Slides, Arcs, and Cluster Variables Fix a word w and the associated arc γw = γA→B in Σw. Recall the internal diagonals of ∆w are δ1, δ2, . . . , δn. For 1 ≤ i ≤ n, let pi = γw ∩ δi be the intersection point of γw with the ith internal diagonal δi of ∆w. Set p0 = A and pn+1 = B. Choose a point mi ∈ Int(∆i) ∩ γw for each 0 ≤ i ≤ n. Let γi be the portion of the arc γw strictly between mi−1 and mi. Let γlef t be the portion of γi strictly between mi−1 and pi, and γright and mi. the portion of γi strictly between pi i i De(cid:27)nition 5.15. For 1 ≤ i ≤ n, de(cid:27)ne a slide of γw at pi by the following two-step process. (1) Perform the smooth isotopy that (cid:27)xes γw−γi and sends pi to one of the endpoints of δi such do not intersect any arc, and have no self-intersections. that the images of γlef t and γright i i (2) Delete the diagonal δi. Choosing one of the two possible slides at each pi results in a collection of curves in Σ, which only intersect possibly at their endpoints. Note that closed curves based at some v ∈ Σ are the only loops that can occur. Replace each curve with distinct endpoints by the arc or boundary segment from ∆w with the same endpoints, and replace each closed curve with ∅. See Figure 5.4 below. 55 Figure 5.4: Dual resolution of the intersection point pi mi−1 pi mi + De(cid:27)nition 5.16. The set of dual resolutions Res(w)∗ associated to w has as its elements those diagrams that can be obtained from sliding each pi in one of the two possible ways, in some order. For r∗ ∈ Res(w)∗, let E(r∗) be the collection of arcs and boundary segments from ∆w produced from the resolution r∗, along with ∅ if any closed loops are present. De(cid:27)ne the weight of any dual resolution r∗ to be xr∗ =(cid:81) j∈E(r∗) xj, where x∅ = 0. We now describe how to produce a dual resolution tree from w. Each node of such a tree is a diagram of arcs inside the (n + 3)-gon Σ, and is weighted by the product of cluster variables asso- ciated to those arcs, or zero if there is a closed loop in the diagram. The root of a dual resolution tree from w is the diagram consisting of the arc γw inside Σw. Choosing an intersection point pi to slide at creates two children of this root (see Figure 5.4). Continuing in this way (choos- ing an intersection point to slide at in each child, etc.) and halting whenever either we create a loop or we have performed a slide at every intersection point, a binary tree (with additional node structure) is produced. De(cid:27)nition 5.17. The set of dual resolution trees Tree(w)∗ associated to w is the set whose elements 56 are dual slide trees from w as described above. Remark 5.18. The set Res(w)∗ is equal to the union of the leaves of the trees in Tree(w)∗. Example 5.19. Fix w = ab. Figure 5.5 shows one element of Tree(w∗)∗ = Tree(bb)∗. Note that this tree is isomorphic to the element of Tree(w) = Tree(ab) from Example 3.15, and that the weights of the leaves here coincide with the weights of the leaves there. Figure 5.5: One element of Tree(bb)∗ f∗ = x1x2x3xγ∗ κ1 x2x3xκ1x7 + ... x2x3xκ2x6 κ2 f∗ = x2 2x7x8 + x2x5x7x9 + x4x5x6x9 + x2x4x6x8 + x1x3x6x9 De(cid:27)nition 5.20. Let A∗ and B∗ be the images of A and B under the triangle map Σw (cid:55)→ Σ∗ w. A∗→B∗ from A∗ to B∗ inside the polygon Σ∗ The dual of the arc γ is the oriented arc γw∗ = γ∗ w. The cluster variable x∗ (cid:88) w dual to xw is de(cid:27)ned by x∗ w = 1 x1x2...xn r∗∈Res(w)∗ xr∗. Remark 5.21. We caution that in general the arc γ∗ do not yet know that x∗ 6.22 below. w is not equal to the arc γw. Furthermore, we w is in fact a cluster variable in a cluster algebra; this is part (c) in Theorem 57 5.6 Snake Graphs The notion of a dual snake graph was introduced in [33]. De(cid:27)nition 5.22. Fix the arc γ in the triangulated polygon Σw triangulated by ∆w. The dual snake graph G∗ w associated to w is the labeled planar graph recursively de(cid:27)ned as follows: 1 is a tri- 2 along labeled j ∈ {n + 1, . . . , 2n + 3}. Note that if the intersection is the triangulated 1 1. Choose an orientation-preserving embedding of the triangulated square [∆0,∇1] into the discrete plane Z2 such that its image (cid:101)T∗ is a triangulated unit square with vertices (0, 0), (1, 0), (0, 1), and (1, 1) in Z2, and such that the point A ∈ ∆0 maps to the point (0, 0). Note that the (line spanned by the) image of the triangulating edge will have slope −1. 2. Choose an orientation-preserving map of [∆1,∇2] into Z2 such that its image (cid:101)T∗ angulated unit square (again, with triangulating edge having slope −1) glued to (cid:101)T∗ the unique edge in each(cid:102)T∗ point of the diagonals δ1 and δ2 is to the left (resp. right) of γw, then(cid:102)T∗ square directly above (resp. to the right of) (cid:101)T∗ graph (cid:102)G∗ slope −1) glued either above or to the right of the previous square. Each(cid:102)T∗ is called the diagonal of(cid:102)T∗ a tile of (cid:102)G∗ 4. The dual snake graph G∗ in (cid:102)G∗ 3. Continue this process, using orientation-preserving maps for both i odd and even, to get the w, built from triangulated unit squares in Z2 (with all triangulating edges having will be called w. The triangulating edge of each(cid:102)T∗ w is the graph in Z2 gotten by deleting each diagonal from each tile i i . . 1 i i 2 w. Example 5.23. Fix w = ab. Figure 5.6 illustrates the construction of the dual snake graph G∗ Gbb from the triangulation ∆ab. w = 58 Figure 5.6: Construction of the dual snake graph Gbb T ile 1 7 2 6 4 1 7 6 4 2 4 1 2 3 T ile 2 5 2 5 9 8 3 T ile 3 8 5 1 2 4 2 6 9 3 4 2 5 1 8 5 3 9 7 Remove Diagonals We give now an explicit procedure Gw (cid:55)→ G∗ w for computing the dual snake graph, starting from Gw. De(cid:27)nition 5.24. Consider the snake graph Gw with tiles T1, T2, . . . , Tn. Let the diagonal of Ti be called di. The antidiagonal of tile Ti, denoted Di, is the line segment inside Ti formed by joining the SW and NE corners of Ti. For any snake graph H with n tiles, the diagonal di of Ti gives two subgraphs Hi−1 and Hi of H that respectively consist of all vertices and edges of H weakly below or weakly above the line spanned by di. De(cid:27)ne HTi to be the snake graph produced by re(cid:30)ecting Hi about the line spanned by Di and regluing the image of Hi to Hi−1. It is clear that the result of this operation is another snake graph. Write (HTi)Tj = HTi◦Tj . One can see from the constructions that we have Gw (cid:55)→ G w. Namely, performing this composition of maps gives each tile of Gw a half-twist (as in De(cid:27)nition 5.22), and furthermore the shape of G w coincides with the shape of G∗ w. T1◦T2◦···◦Tn T1◦T2◦···◦Tn w = G∗ 59 Example 5.25. We demonstrate in Figure 5.7 the factorization Gab (cid:55)→ G Figure 5.7: Transforming Gab into its dual Gbb T1◦T2◦···◦Tn ab = Gbb. 2 1 7 9 5 4 6 8 3 2 7 2 6 4 3 1 5 8 2 T1 9 7 T2 9 5 1 2 4 2 6 8 5 1 9 3 2 4 2 6 8 3 7 T3 The next result follows from the factorization just given. Proposition 5.26. For any word w, we have (a) sh(Gw) = w∗ and sh(G∗ w) = w. (b) sh(Gw)∗ = sh(G∗ w). (c) G∗ w = Gw∗. De(cid:27)nition 5.27. Fix the word w, and consider the sign sequence sw = (s(e0), s(e1), . . . , s(en)) on the snake graph Gw. The dual sign sequence s∗ w is de(cid:27)ned by s∗ w = (s(e0),−s(e1), s(e2),−s(e3), . . . ). Proposition 5.28. For any word w, we have s∗ w = sw∗. Proof. This follows immediately from Proposition 5.26. Example 5.29. Below is the sign sequence sab and its dual s∗ ab = sbb. 60 Figure 5.8: The sign sequence sab and its dual sbb sw = (−, +,−, +) s∗ w = (−,−,−,−) 5.7 Continued Fractions For more on the involution on continued fractions given in the next de(cid:27)nition, see [41]. De(cid:27)nition 5.30. Consider the (cid:27)nite positive continued fraction [k1, k2, . . . , kd]. The dual contin- ued fraction [k1, k2, . . . , kd]∗ is gotten from [k1, k2, . . . , kd] by (cid:27)rst writing each ki as 1+1+...+1, substituting these expressions into their respective entries in the continued fraction, and applying the involution that exchanges the symbol “,” with the symbol “+”. Example 5.31. The continued fraction associated to the word w = ab is CF(ab) = [1, 1, 1, 1] (see Example 3.39). The dual continued fraction is computed as CF(w)∗ = CF(ab)∗ = [1, 1, 1, 1]∗ = [1 + 1 + 1 + 1] = [4] = CF(bb) = CF(w∗) Remark 5.32. The continued fractions in (a) from Remark 3.40 are dual to those in (c), and the same for (b) and (d). Proposition 5.33. For any word w we have CF(w)∗ = CF(w∗). 61 Proof. This follows immediately from Proposition 5.28. 5.8 Distributive Lattices De(cid:27)nition 5.34. The distributive lattice dual to Dw is simply Dw∗ = I(C∗ w). Example 5.35. The three expansion posets pictured in Examples 4.4, 4.7, and 4.11 are all isomor- ∼= Γ3. The dual lattice Dbb is a chain poset on 4 vertices. phic to the same distributive lattice Dab See Figure 5.9. Figure 5.9: The Fibonacci cube Γ3 and its dual Dab Dbb Remark 5.36. In general, a chain poset with n + 1 vertices is dual to the Fibonacci cube Γn. 62 Chapter 6 Dual Expansion Posets 6.1 Lattice Paths on Snake Graphs We recall here the lattice path expansion posets from [33]. De(cid:27)nition 6.1. A lattice path in a snake graph Gw with n tiles is a choice of n + 1 edges L from Gw which when concatenated form a path, taking only unit steps right or up, from the SW vertex of tile T1 to the NE vertex of tile Tn. The weight xL of L is de(cid:27)ned to be the product of initial l∈L xl. Let Lw be the set of all lattice paths of the snake graph Gw. cluster variables xL =(cid:81) Example 6.2. Figure 6.1 shows one of the (cid:27)ve lattice paths on the snake graph Gbb dual to Gab. Note that the weight of this lattice path coincides with the weight of the the perfect matching shown in Figure 4.1. Figure 6.1: The lattice path L− on Gbb 9 3 6 1 The next expansion formula is from [33]. 63 Theorem 6.3. Let w be any word, and consider the set L Gw∗. Then the cluster variable xw can be written as w∗ of lattice paths on the dual snake graph (cid:88) xw = 1 x1x2 . . . xn L∈L w∗ xL. Corollary 6.4. For any word w, we have |Pw| = |L w∗| and |Lw| = |P w∗|. Let CF(w) = [k1, k2, . . . , kd] and CF(w∗) = [K1, K2, . . . , Kl], and recall the notation Gc w, w, and |Pc w| similarly. Combining Pc Corollary 6.4 with Theorem 4.5 gives the next result. w| given directly before Theorem 4.5). De(cid:27)ne Lc w, and |Lc Corollary 6.5. For any word w, we have and CF(w) = CF(w)∗ = w |Pw| (cid:12)(cid:12)(cid:12) = (cid:12)(cid:12)(cid:12)Pk1 (cid:12)(cid:12)(cid:12) = (cid:12)(cid:12)(cid:12)PK1 w∗| |P w∗ |L w∗| w∗ (cid:12)(cid:12)(cid:12) (cid:12)(cid:12)(cid:12)Lk1 (cid:12)(cid:12)(cid:12). (cid:12)(cid:12)(cid:12)LK1 |Lw| w We now give the set Lw a poset structure. A (cid:30)ip of L at tile Ti is the local move that takes two edges of L located on the same tile Ti of Gw that are incident to a common vertex of Ti (necessarily the two edges in question are the S and E edges of Ti, or the W and N edges of tile Ti) and replaces them with the other two edges of Ti. Directly below is the local picture for the (cid:30)ip at a generic tile Ti. 64 Figure 6.2: Flip of a lattice path at tile Ti Ti Ti An up-(cid:30)ip at tile Ti is a (cid:30)ip that replaces the S and E edges of Ti with the N and W edges of Ti. De(cid:27)nition 6.6. The minimal element L− of Lw is the unique lattice path of Gw such that every edge in L− is a boundary edge of Gw and the S edge of tile T1 is in L−. The maximal element L+ of Lw is the unique lattice path of Gw such that every edge in L+ is a boundary edge of Gw and the S edge of tile T1 is not in L−. De(cid:27)nition 6.7. The poset structure on Lw is de(cid:27)ned as follows. The unique minimal element of Lw is the minimal lattice path L−, and the unique maximal element is L+. A lattice path L2 covers a lattice path L1 if there exists a tile Ti such that L2 can be obtained from L1 by performing a single up-(cid:30)ip of L1 at Ti. Example 6.8. Fix w = ab. In Figure 6.3, we illustrate the poset L the dual snake graph Gbb. Compare with Figures 4.4, 4.7, and 4.11 from Chapter 4. w∗ = Lbb of lattice paths on 65 Figure 6.3: The poset Lbb 8 2 2 7 2 5 9 7 8 2 4 6 9 5 4 6 9 3 6 1 Remark 6.9. If the word sh(Gw) is straight, the poset Pw is isomorphic to a Fibonacci cube (see (b) in 4.9), and likewise L w∗ is isomorphic to the same Fibonacci cube. Conversely, if the word w∗ are isomorphic to the same linear chain. sh(Gw) is zigzag, then both the posets Pw and L Similar remarks hold for the other expansion formulas. See Theorem 6.22 below for details. 6.2 Lattice Paths of Angles Say that a vertex v of Σ is incident to any triangle that it is a vertex of. De(cid:27)nition 6.10. A lattice path of angles β of Σw is a selection of n + 1 angles from the triangles ∆0, ∆1, . . . , ∆n of ∆, one per triangle, such that the following hold. (1) Each angle is incident to an endpoint of one of the internal diagonals δ1, δ2, . . . , δn. 66 (2) Consider the internal diagonal δi and one of its endpoints v. If v is incident to an even (resp., odd) number of triangles, then an even (resp., odd) number of angles of β are incident to v. of o. The weight of β is de(cid:27)ned to be the product of initial cluster variables xβ =(cid:81) Each angle o in ∆i can be assigned the cluster variable xo associated to the edge of ∆i opposite o∈β xo. Let Bw be the set of all lattice paths of angles in Σw. Example 6.11. Below we show one of the (cid:27)ve lattice paths of angles on the dual triangulated surface Σ∗ ab = Σbb. Figure 6.4: The lattice path of angles β− on Gbb 6 1 3 9 The next result is included as part of the statement of Theorem 6.22 (e), and is proved there. Theorem 6.12. Let w be any word. Consider the set B triangulated surface Σ∗ w. Then the cluster variable xw can be written as w∗ of lattice paths of angles on the dual (cid:88) xw = 1 x1x2 . . . xn β∈B w∗ xβ. We now give the set Bw a poset structure. A (cid:30)ip of β at diagonal δi is the local move that takes two angles in β that are each incident to the same endpoint of the internal diagonal δi and replaces them with the remaining two angles incident to δi. 67 Directly below is the (cid:30)ip at a generic internal diagonal δi. Figure 6.5: Flip of a lattice path of angles at diagonal δi i i Let li be the endpoint of δi to the left of γA→B, and ri the endpoint to the right. An up-(cid:30)ip of β at diagonal δi is a (cid:30)ip that meets either of the following two conditions: (1) i is odd, and the two angles incident to li are replaced with the two angles incident to ri, or (2) i is even, and the two angles incident to ri are replaced with the two angles incident to li. De(cid:27)nition 6.13. The minimal element β− of Bw is the unique lattice path of angles such that the boundary angle in ∆0 with boundary edge δ2n+1 is included in β−, and only boundary angles are used in β−. The maximal element β+ of Bw is the unique lattice path of angles such that the angle the boundary angle in ∆0 with boundary edge δ2n is included in β+, and only boundary angles are used in β+. De(cid:27)nition 6.14. The poset structure on Bw is de(cid:27)ned as follows. The unique minimal element of Bw is the minimal lattice path of angles β−, and the unique maximal element is β+. A lattice path of angles β2 covers another lattice path of angles β1 if there exists a diagonal δi such that β2 can be obtained from β1 by performing a single up-twist of β1 at δi. Example 6.15. Fix w = ab. The poset of lattice paths of angles on the dual triangulated surface Σbb is shown in Figure 6.6 below. 68 Figure 6.6: The poset Bbb 8 6 2 4 7 2 9 5 7 8 2 2 6 9 4 5 6 1 3 9 6.3 S-walks Let F = (V, E) be any graph, with vertex set V and edge set E. A walk is a sequence of vertices (v0, v1, . . . , vk) such that consecutive vertices are incident, i.e., (vi, vi+1) ∈ E for each i with 0 ≤ i ≤ k − 1. We say that k is the length of the walk. Recall the notation Σw for the triangulation associated to w, and that A and B are the end- points of the (directed) arc γw = γA→B. De(cid:27)nition 6.16. An S-walk from A to B is a walk S = (A = v0, v1, . . . , vn+1 = B) of length n + 1 which uses the vertices of the triangulation ∆w and is such that at least one edge from each triangle ∆i in Σw occurs in S. De(cid:27)ne the weight xS of S by xS =(cid:81) s∈S xs. Let Sw be the set of all S-walks from A to B. Again, the proof of the next result is given in Theorem 6.22 below. Theorem 6.17. Let w be any word. Consider the set S w∗ of S-walks from A∗ to B∗ with edges 69 taken from the dual triangulation ∆∗ w. Then the cluster variable xw can be written as (cid:89) xw = 1 x1x2 . . . xn S∈S∗ w xS. We now give the set Sw a poset structure. Recall that li is the endpoint of δi to the left of γA→B, and ri is the endpoint to the right. Consider the (triangulated) minimal quadrilateral [∆i−1, ∆i], and let the endpoints of δi be li and ri. A (cid:30)ip of S at diagonal δi is the local move that replaces the two distinct edges in S which are both boundary edges of [∆i−1, ∆i] incident to ri (resp. li), and replaces them with the other two boundary edges of [∆i−1, ∆i] incident to li (resp. ri). Directly below is the local picture of an S-walk (cid:30)ip at a generic internal diagonal δi. Figure 6.7: Flip of an S-walk at diagonal δi i i An up-(cid:30)ip of S at diagonal δi is a (cid:30)ip that meets either of the following two conditions: (1) i is odd, and the two edges in S incident to ri are replaced with the two edges in Qi incident to li, or (2) i is even, and the two edges in S incident to li are replaced with the two edges in Qi incident to ri. De(cid:27)nition 6.18. The minimal element S− of Sw is the unique S-walk that starts with the bound- ary edge δ2n+1, and only uses internal diagonals as edges, except for the (cid:27)rst and last (boundary) 70 edges. The maximal element S+ of Sw is the unique S-walk that starts with the edge δ2n, and only uses internal diagonals as edges, except for the (cid:27)rst and last (boundary) edges. De(cid:27)nition 6.19. The poset structure on Sw is de(cid:27)ned as follows. The unique minimal element of Sw is the minimal S-walk S−, and the unique maximal element is S+. An S-walk S2 covers another S-walk S1 if there exists a diagonal δi such that S2 can be obtained from S1 by performing a single up-(cid:30)ip of S1 at δi. Example 6.20. Fix w = ab. The poset of S-walks on the dual triangulated surface Σ∗ displayed in Figure 6.8. Note that the “middle” internal diagonal in S+ is used twice. ab = Σbb is Figure 6.8: The poset Sbb 8 6 2 4 7 2 9 5 7 8 2 2 6 9 4 5 6 1 3 9 We now give the analogue of Proposition 4.23. The proof of this result will follow from part (d) of Theorem 6.22. Proposition 6.21. Fix the word w. There is a commutative diagram of weight-preserving poset isomorphisms 71 Lw Bw Sw that are identi(cid:27)ed are those that are opposite one another in the quadrilateral determined by two We illustrate Proposition 6.21 with the three dual posets Lbb, Bbb, and Sbb from the running example. By Lemma 3.2 in [43] there is a bijection between the angles in Σw not incident to A or B, and the edges in Gw induced by identifying certain pairs of angles in (cid:102)Gw. The pairs of angles consecutive tiles of (cid:102)Gw. Any pair of angles in (cid:102)Gw which have been identi(cid:27)ed correspond to a Thus, given a lattice path L ∈ Lw, we can associate to it a collection of angles in (cid:101)G and fold single internal angle in Σw. the result to obtain a lattice path of angles β in Σw. Figure 6.9: The map Lw −→ Bbb via angle identi(cid:27)cation and folding f old each node 72 The map Bw −→ Sw is de(cid:27)ned by taking the collection of edges which are opposite some vertex in S ∈ Sw. See Figure 6.10 below. Figure 6.10: The map Bbb −→ Sbb via associating edges to angles 2 ”project” onto edges The map Lw −→ Sw is de(cid:27)ned by folding and is the composition of the previous two. 6.4 Expansion Duality Theorem 6.22. Fix the word w. (a) There is a explicit bijection Tree(w)∗ −→ Tree(w∗) that preserves additional node structure, and weights of leaves. (b) There is a weight-preserving bijection Res(w)∗ −→ Res(w∗) respecting additional node struc- ture. (c) The Laurent polynomial x∗ w is a cluster variable in A(Σ)w∗, and is equal to x∗ w = xw∗. 73 (d) There are explicit isomorphisms of distributive lattices Pw ∼−→ L w∗, Aw ∼−→ B w∗, and Tw ∼−→ S w∗ respecting the additional structure of each lattice, and making the following diagram commute. L∗ w B∗ w Pw Aw S∗ w Tw Namely, corresponding nodes in the six posets have the same weight, except for the nodes of the T -path expansion poset. In this case, node weights have an additional factor of 1 x1x2...xn that is not preset in any of the node weights for the other (cid:27)ve expansion posets. (e) The cluster variable xw can be written as xw = 1 x1x2 . . . xn L∈L w∗ x1x2 . . . xn B∈B w∗ xL = (cid:88) (cid:88) 1 (cid:88) 1 x1x2 . . . xn S∈S w∗ xS. xB = (f) There are isomorphisms of distributive lattices Dw ∼= I(Cw) ∼= Pw and Dw∗ ∼= I(C∗ w) ∼= Lw. Thus, Pw and Lw are dual to one another in the sense of distributive lattices (see De(cid:27)nition 5.34). Proof. (a) Let t ∈ Tree(w)∗. The map Tree(w)∗ −→ Tree(w∗) is de(cid:27)ned by the application of the triangle map to each node of the input tree t, except that we must additionally specify how to transform arcs δ ∈ Σw which are not contained in the triangulation ∆w into arcs δ∗ ∈ Σ∗ w. 74 Suppose δ /∈ ∆w is an arc in a diagram which is a node in t, and that δ crosses the triangles ∆i, . . . , ∆j. The obvious one-to-one correspondence induced by the triangle map between angles in Σw and angles in Σ∗ w gives a natural candidate for the image of the arc δ. Namely, suppose the endpoints of δ are vi and vj, corresponding to the angles αi an αj in ∆i and ∆j, respectively. Let α∗ and α∗ be the angles which are the respective images of αi and αj under the triangle map. Let v∗ be the vertex that α∗ the vertex that α∗ is incident to. Then δ∗ is the arc that j is incident to, and let v∗ be i i j i j (1) starts at the vertex v∗ i , (2) ends at the vertex v∗ j , (3) passes through the center of precisely those triangles in Σ∗ w which are the images of the triangles ∆i, . . . ∆j under the triangle map, and (4) has as its only intersections (besides endpoints) the midpoint of each internal diagonal it crosses. For instance, suppose the arc δ starts at A, is contained in the triangulated subpolygon [∆0, ∆1, . . . , ∆j], and ends at vertex vj of ∆j. The output δ∗ for the two subcases j even and j odd are shown in Figure 6.11. This map is well-de(cid:27)ned by induction on n, and that edge weights of leaves are preserved is obvious. The inverse map Tree(w)∗ −→ Tree(w∗) is de(cid:27)ned similarly, and the composition is the identity. Hence the map in question is an invertible bijection respecting additional node structure as claimed. (b) This follows directly from (a), since Res(w) is equal to the union of the leaves in the trees in Tree(w), and Res(w)∗ is equal to the union of the leaves in the trees in Tree(w)∗. 75 Figure 6.11: The arc δ, and the output arc δ∗ for both j odd and j even A∗ ∆0 δ∗ ∇1 ∇j−1 ∆j . . . v∗ j A ∆0 ∆1 . . . δ ∆j−1 j even . . . vj j odd . . . ∆j δ∗ ∇j ∆j−1 v∗ j . . . A∗ ∆0 (c) From (b) we have x∗ w = 1 x1x2 ··· xn ∇1 (cid:88) xr∗ = 1 x1x2 ··· xn (cid:88) r∈Res(w∗) xr = xw∗. r∗∈Res(w)∗ (d) De(cid:27)ne the set map Pw −→ L w∗ by applying Gw (cid:55)→ G w T1◦T2◦...◦Tn to the underlying snake graph of each node P ∈ Pw, keeping track of the images under the maps Ti of all the edges in P. It follows from [33] that Pw −→ L w∗ is a well-de(cid:27)ned set bijection. That this map extends to an isomorphism of posets is much like the proofs given in 4.23. It is obvious that ∼−→ weights are preserved. Thus, there is a structure-preserving poset isomorphism Pw w∗, as claimed. L One can check from the de(cid:27)nitions that the nonzero leaves of Res(w∗)∗ are precisely the S-walks from A∗ to B∗ with edges from the dual triangulation Σ∗ w. Similarly, T-paths from A to B with edges from ∆w are in bijection with the nonzero leaves in Res(w) (induced 76 ∼−→ S w∗ is a structure-preserving poset isomorphism, as claimed. by mulitplication or division by x1x2 . . . xn). Hence by part (b), there is a set bijection Tw −→ S w∗ which is induced by the triangle map. Clearly, corresponding node weights di(cid:29)er by multiplication or division by x1x2 . . . xn. It is again straightforward to check that covering relations are preserved by using cases on the parity of i. Thus, the map Tw The map of sets Aw −→ B w∗ is de(cid:27)ned by the one-to-one correspondence of angles α(Σw) −→ α(Σw∗) (mentioned in part (a) above) induced by the triangle map. To see that this map is well-de(cid:27)ned, we can use the following observation. Suppose we are given a perfect matching of angles α ∈ α(Σw). Now glue a new triangle to one of the two bound- ary edges in ∆w that are incident to B. In either case, there is a unique angle from this new triangle that we can add to the original matching α to create a new perfect matching of angles in the larger triangulated polygon just constructed. That this choice is unique follows from part (2) of De(cid:27)nition 4.10. Now we use induction on n. So, suppose Σw has n + 1 internal diagonals, and consider the perfect matching of angles α ∈ Aw. Let Σ(cid:48) be the triangulated subpolygon of Σw obtained from deleting the last triangle, and de(cid:27)ne Σ(cid:48) w∗ ⊂ Σw∗ similarly. By induction, the triangle map restricted to Σ(cid:48) w produces a lattice path of angles in Σ(cid:48) w∗. The claim now follows by considering cases on the parity of n. w One can construct each map in the triangle of isomorphisms from Proposition 6.21 as a composition of duality maps and the appropriate map from Proposition 4.23. Thus the diagram in question is commutative. Finally, that Pw is a distributive lattice follows from Theorem 5.2 in [31]. Thus, the rest are distributive lattices as well. (e) Follows directly from (d). 77 (f) That I(Cw) ∼= Pw follows from De(cid:27)nition 5.3 and Theorem 5.4 in [31]. That I(C∗ w) ∼= Lw follows from the construction on page 18 of [25]. Namely, the poset C∗ w can be built from the minimal path L− in Gw by deleting the (cid:27)rst and last steps in L−, and rotating the result 45◦ clockwise. That Pw and Lw are dual as distributive lattices follows from the de(cid:27)nition. Example 6.23. We illustrate how applying the isomorphisms from Theorem 6.22 (d) to the three minimal elements in the running example from the previous chapter gives the three respective minimal elements from the running example in this chapter. The next (cid:27)gure shows the minimal matching P− in Pab being sent to L− in Lbb. Figure 6.12: Transforming the minimal element P− into the minimal element L− 2 1 7 9 5 4 6 8 3 2 7 2 6 4 3 1 5 8 2 T1 9 7 T2 9 5 1 2 4 2 6 8 5 1 9 3 2 4 2 6 8 3 7 T3 To compute the image of α− ∈ Aab under Aab −→ Bbb, we apply the triangle map. This is shown in Figure 6.13. Figure 6.13: Transforming the minimal element α− into the minimal element β− = = 78 The isomorphism Tab −→ Sbb is obtained by coloring all internal diagonals blue, canceling blue-red pairs if necessary, and then applying the triangle map. See Figure 6.14. Figure 6.14: Transforming the minimal element T− into the minimal element S− b r b b r b b b b b b b b triangle map color diagonals blue cancel 79 Chapter 7 Expansion Posets as Intervals in Young’s Lattice Loosely speaking, a graded poset is one whose elements can be arranged into “horizontal ranks”. Each graded poset has an associated rank-generating function, which is a polynomial in one variable whose jth nonnegative integer coe(cid:28)cient records the number of elements sitting at rank j. The (cid:27)rst objective of this chapter is to give some preliminaries on graded posets and their rank functions, and to note that each expansion poset we have studies thus far is graded. Our second objective is to put an equivalence relation on the set of all snake graphs, and re(cid:27)ne each resulting equivalence class to a graded poset. The covering relation in each such poset resembles a (cid:30)ip of a lattice path inside a snake graph. We observe that each poset of snake graphs from our construction is isomorphic to one of the well-known lattices L(m, n) whose rank generating functions are the classical q-binomial coe(cid:28)cients. For more on the posets L(m, n) and their (symmetric and unimodal) rank generating functions (and much more on unimodality in general, and related concepts), see [40], [4], and [3]. Our (cid:27)nal objective in this chapter is to show how each poset L(m, n) has a covering by intervals, each of which is isomorphic to one of the lattice path expansion posets considered above. This covering is such that two lattice path expansions embed into the same lattice L(m, n) if and only if their underlying snake graphs are elements of the same snake graph poset. Finally, 80 since each L(m, n) is itself an interval in Young’s lattice, this shows that each expansion poset is isomorphic to an interval in the latter. 7.1 Graded Expansion Posets De(cid:27)nition 7.1. Let D be a (cid:27)nite poset. A chain in D is a totally ordered subset of D. A maximal chain in D is a chain that is not a proper subset of any other chain in D. The length of a chain with k elements is k − 1. We say that D is a graded poset if all maximal chains in D have the same (cid:27)nite length. If D is graded then there exists a rank function ρ : D −→ N = {0, 1, 2, . . .} that satis(cid:27)es the following. (1) The minimal elements of D map to 0. (2) For every x, y ∈ D, x < y implies ρ(x) < ρ(y). (3) If x < y and there does not exist z ∈ D such that x < z < y (i.e., if y covers x), then ρ(y) = ρ(x) + 1. We say the element x ∈ D has rank i if ρ(x) = i. The rank of the (cid:27)nite graded poset D is equal to the length of any maximal chain. It is an easy consequence of Birkho(cid:29)’s Theorem 3.47 above that every (cid:27)nite distributive lattice D is graded. Indeed, for input the order ideal I ∈ I(C) ∼= D the rank is ρ(I) = |I|, the cardinality of I. Thus, Dw ∼= I(Cw) is graded for each word w. The next result is an analogue of Theorem 5.1 in [29]. Proposition 7.2. The rank of any lattice path L ∈ Lw is the number of tiles enclosed by the symmetric di(cid:29)erence L (cid:9) L− of L with the minimal lattice path L− from De(cid:27)nition 6.6. 81 Proof. The minimal path L− has rank 0. Covering relations are given by up-(cid:30)ips, and performing an up-(cid:30)ip of a lattice path increases the number of tiles in L (cid:9) L− by one. Simply put, the rank of a lattice path is the number of tiles in the snake graph that are “below” the lattice path. De(cid:27)nition 7.3. Suppose w has length n− 1 and consider the graded distributive lattice Lw. The rank-generating function Lw(q) of the lattice Lw is the polynomial in q of degree n de(cid:27)ned by i=0 riqi, where ri equals the number of lattice paths of rank i in Lw. Lw(q) =(cid:80)n generating function ρ(q) =(cid:80)n De(cid:27)nition 7.4. Let ρ be the rank-generating function of a graded poset D of rank n. The rank- i=0 riqi is unimodal if there exists some m such that r0 ≤ r1 ≤ . . . rm−1 ≤ rm ≥ rm+1 ≥ ··· ≥ rn. We say ρ(q) is symmetric if rn−i = ri for each i. We call D a rank-unimodal poset (or just unimodal) if its rank function is unimodal, and call D a rank-symmetric poset (or just symmetric) if its rank function is symmetric. For instance, Fibonacci cubes are unimodal, and those of even order are symmetric. [28]. Example 7.5. Figure 7.1 shows three snake graphs Gw1, Gw2, and Gw3, along with their respec- tive shapes and lattices. Below these (cid:27)gures, we indicate the respective rank generating functions. Note the rank-generating functions Lwi(q) are unimodal for i = 1, 2, 3 and symmetric for i = 2 or 3. 82 Figure 7.1: Posets, shapes, and rank functions for three snake graphs ∼= Lw1 ∼= Lw2 ∼= Lw3 Gw1 = sh(Gw1) = baa Gw2 = sh(Gw2) = baab Gw3 = sh(Gw3) = aabaa Lw1(q) = 1 + q + 2q2 + 2q3 + q4 Lw2(q) = 1 + 2q + 3q2 + 3q3 + 2q4 + q5 Lw3(q) = 1 + 2q + 3q2 + 3q3 + 3q4 + 2q5 + q6 7.2 Posets of Snake Graphs and the q-binomial Coe(cid:28)cients Let Ln be the set of snake graphs with n ≥ 1 tiles. Let L = ∪Ln. Consider the equivalence relation on L de(cid:27)ned by saying that two snake graphs are equivalent if they have the same number of tiles, and are related by the following local move: Figure 7.2: Local picture for two equivalent snake graphs In particular, each straight snake graph (and each snake graph with less than three tiles) is the sole member of its equivalence class. Each Ln is a union of equivalence classes. For n ≥ 3, we parameterize any equivalence class 83 of Ln by the snake graph Gn,j− it contains which is of shape ak1−1bk2−1 = ak1−1bj, where n = k1 + k2 − 1. Let {On be the n equivalence classes of Ln. j }n−1 j=0 Re(cid:27)ne each equivalence class On j by declaring that the snake graph Gn,j− is the minimal element, and by saying that performing the swap ab (cid:55)→ ba corresponds to going up in the poset. of Ln to a poset On j Example 7.6. Figure 7.3 show the poset O5 2 from the subgroupoid L5 (cid:44)→ L. Figure 7.3: The poset O5 2 The rank functions of the posets On j are well known. 84 De(cid:27)nition 7.7. The q-binomial coe(cid:28)cients are de(cid:27)ned by = [n]q! [k]q![n − k]q! , (cid:20)n (cid:21) k q where [k]q! = (1 + q)(1 + q + q2) . . . (1 + q +··· + qk−1). Each q-binomial coe(cid:28)cient is a rational function in the indeterminate q, and is in fact a polynomial function with positive coe(cid:28)cients. Note that taking the limit q → 1 recovers the standard binomial coe(cid:28)cients. De(cid:27)nition 7.8. The product of two posets (P,≤P ) and (Q,≤Q) is the poset whose underlying set is equal to the Cartesian product P × Q with covering relations given by (p1, q1) ≤P×Q (p2, q2) ⇐⇒ p1 ≤P p2 and q1 ≤Q q2. Let k and l be the chain posets with k and l vertices, respectively. Consider the product poset k × l. Then the rank generating function of the poset of order ideals of k × l is equal to the (cid:3) (see [40]). The q-binomial coe(cid:28)cients are also the rank generating q-binomial coe(cid:28)cient(cid:2)k+l l functions for the area under lattice paths in a rectangular Young diagram with k boxes by l boxes. Equivalently, the q-binomial coe(cid:28)cients the are rank-generating functions of Young diagrams that (cid:27)t inside a k by l rectangular grid. Here, the rank of a Young diagram is the number of boxes is contains. It is not hard to see that any q-binomial coe(cid:28)cient is symmetric (for instance see [40]). How- ever, it is a nontrivial fact that these coe(cid:28)cients are unimodal. This was (cid:27)rst proved by Sylvester in 1878 (see [40] and [3]). The (cid:27)rst combinatorial proof of unimodality was given over one hun- dred years later by O’Hara in [32]. 85 Example 7.9. For instance, the rank generating function of O7 3 ∼= I(3 × 3) is equal to 1 + q + 2q2 + 3q3 + 3q4 + 3q5 + 3q6 + 2q7 + q8 + q9. This is visualized in the next (cid:27)gure. Figure 7.4: The poset 3 × 3 (bottom), its lattice of order ideals I(3 × 3) (top left), and the rank function of O7 3 ∼= I(3 × 3) (top right) 1 1 2 3 3 3 3 2 1 1 I(3 × 3) . 3 × 3 7.3 The Embeddings Lw (cid:44)→ On j Recall that a partition of a positive number m is a weakly decreasing sequence λ = (λ1, λ2, . . . , λl) such that m = λ1 + λ2 +··· + λl. For example, λ = (4, 3) is one partition of 7. A Young diagram 86 is a way to visualize a partition as a left-justi(cid:27)ed collection of rows of boxes. For instance, to form the Young diagram associated to the partition (4, 3) of 7, we draw an array of 7 boxes, consisting of a row of 4 boxes followed by a row of 3 boxes. Figure 7.5: The Young diagram associated to the partition (4, 3) of 7 De(cid:27)nition 7.10. Let P be a poset. Let x, y ∈ P. The closed interval [x, y] is the subposet of P de(cid:27)ned by z ∈ [x, y] if and only if x ≤ z ≤ y. Young’s lattice is the in(cid:27)nite poset whose nodes are Young diagrams of partitions, ordered by inclusion (see [35]). The minimal element is the empty set, and there is no maximal element. Each On j is isomorphic to a (cid:27)nite closed interval [∅, λ] in Young’s lattice (see Theorem 7.12 for a proof), whose minimal element is the empty set and with maximal element a rectangular array of boxes λ (indeed, λ is the smallest rectangular array of boxes containing the minimal snake graph Gn,j− ). Consider the dual cluster variable x∗ w on the snake graph Gw with n ≥ 1 tiles. Let xM be any Laurent monomial of x∗ w, represented by the lattice path L on Gw. We can naturally associate to L a word by labeling any E step in L by a, and any N step in L by b. Let GL be the snake graph whose shape is determined by the assignment just described. Note that GL has two more tiles than Gw. The above remarks give a map φ : Supp(x∗ w) −→ Ln+2, xM (cid:55)→ GL. 87 Figure 7.6: Snake graphs from lattice paths If we apply φ to the monomial weight of each node in Lw we obtain an isomorphic poset Iw ∼= Lw, where each node of Iw is a snake graph in Ln+2. The covering relation in Iw is the one shown in Figure 7.2 above. Example 7.11. Figure 7.7 shows the poset Lab on the left, and the isomorphic poset Iab on the right. Figure 7.7: The posets Lab and Iab ∼= Lab The above discussion leads to the next result, which states that each poset On+2 j can be built from gluing together the lattice path posets corresponding to the snake graphs in some On k . 88 Theorem 7.12. Suppose the words w, w1, and w2 are each of length n − 1. Let Lw be the poset of lattice paths on Gw. Let L1 . = Lw1 and L2 . = Lw2 be the posets of lattice paths on G1 ∼= I1 and L2 . = Gw1 and ∼= I2. . = Gw2, respectively. Label their snake graph representations by L1 G2 (a) Each poset On+2 j is isomorphic to the poset of lattice paths in a rectangular grid. (b) The rank generating function of the graded poset On+2 j is equal to a q-binomial coe(cid:28)cient. is isomorphic to the closed interval [∅, λ] in Young’s lattice. (c) Each poset On+2 (d) Each lattice Lw ∼= Iw is isomorphic to a closed interval in one of the posets On+2 j j . (e) The two posets L1 ∼= I1 and L2 ∼= I2 are embedded as intervals into the same On+2 j if and only if G1 and G2 are both elements of the same poset On i . Moreover, each On+2 j is covered by the collection of such embeddings. Proof. (a) Suppose the minimal element of On+2 Note that the covering relations in On+2 j has word ak1bk2, where k1 + k2 − 1 = n. j preserve the number of a’s and b’s in the shape are precisely those snake graphs whose word of a snake graph. That is, the nodes of On+2 j has k1 instances of the symbol a, and k2 instances of the symbol b. This description makes clear the isomorphism between On+2 and the lattice paths in a k1 × k2 grid. j (b) As mentioned above, each poset of lattice paths in a rectangular grid is isomorphic to a closed interval [∅, λ] in Young’s lattice. Now the claim follows from part (a). (c) As mentioned above, the rank generating function of lattice paths in a grid is equal to some q-binomial coe(cid:28)cient. The result now follows from (a). (d) Embed the underlying snake graph Gw into the minimal rectangular grid containing it. This realizes the poset Lw as the interval [L−, L+] inside the poset of lattice paths in this 89 grid. As was indicated in part (a), the latter poset is isomorphic to On+2 j for some j. Thus the claim holds. (e) The snake graphs G1 and G2 are nodes in the same poset if and only both snake graphs are contained within the same minimal rectangular grid. This is true if and only if the lattice path posets L1 and L2 are embedded as intervals into the same poset of lattice paths in this minimal rectangular grid. By part (a), this is true if and only if L1 and L2 are embedded is covered by the collection of these embeddings follows into the same On+2 . That On+2 j j from the fact that any rectangular grid has a covering by snake graphs. Example 7.13. Figure 7.8 shows three copies of the same poset, each of which is isomorphic to . In each copy, we display one of the intervals (i.e., poset of lattice paths) in the cover from O6 2 Theorem 7.12. Note that the three distinct snake graphs corresponding to each embedded interval shown are precisely the elements of O4 1 . Figure 7.8: Three lattice path posets embedded into O6 2 90 Remark 7.14. There is a "dual" equivalence relation that one can impose on L, de(cid:27)ned by the local move shown in the next (cid:27)gure. Figure 7.9: Local picture for two snake graphs related under the dual equivalence relation Consider the cluster variable xw∗ on the dual snake graph Gw∗. This cluster variable is com- puted via perfect matchings on Gw∗. We can associate to each (monomial weight of the) perfect matching P a snake graph GP . This is done by arranging the edges in P into a sequence, from which we read o(cid:29) a word whose bit values depend on whether an edge is vertical or horizontal. We now explain how to order the edges of P to form the aforementioned sequence. Recall the ordering of tiles T1 < T2 < ··· < Tn. The edges of P are arranged into a sequence by (cid:27)rst ordering them according to which tile Ti with minimal i that they lie on. That is, any edge from tile Ti must come before any edge on tile Ti+1 in this sequence. Note that if two edges are associated to the same tile Ti, then they are both vertical or both horizontal. Thus, this gives a well-de(cid:27)ned sequence of vertical and horizontal edges, built from the matching P on Gw∗. From this sequence, we obtain a word by declaring that any vertical edge maps to a, and any horizontal edge maps to b. An example of this assignment is shown in Figure 7.10 below. 91 Figure 7.10: Snake graphs from perfect matchings Let L be the image of P under the map P ∼=−→ Lw. It is immediate from this construction that GP is the snake graph dual of GL, the snake graph constructed from the lattice path L on Gw. For example, the lattice path shown at the left of Figure 7.6 is the image of the perfect ∼=−→ Lw. Furthermore, the snake matching shown at the left of Figure 7.10 under the map P graph shown at the right of Figure 7.6 is the dual of the snake graph at the right of Figure 7.10. w∗ w∗ The above observations make it possible to formulate most of the results from Theorem 7.12 in terms of perfect matchings. Example 7.15. Below we show the “dual” of the poset O5 2 together the two posets Paa and Pbb, after realizing each perfect matching as a snake graph. Note that each node of this poset is dual (in the sense of snake graphs) to its respective node from . This poset can be obtained by gluing Figure 7.3. 92 Figure 7.11: The poset dual to O5 2 93 Chapter 8 A Recursion and Two Rank Formulas The (cid:27)rst goal of this chapter is to give a recursive formula for the computation of Lw(q). Our second goal is to give a closed formula for Lw(q) in terms of products of hooks, snake graphs whose shape is either ak1bk2 or ak2bk1 for k1, k2 ≥ 2. Thirdly, we combine this hook expansion with an interpretation of a snake graph as the central lattice path on a “stretched” zigzag snake graph to obtain a closed formula for Lw(q) in terms of the entries of the dual continued fraction CF(w∗). 8.1 Lattice Path Recursion A straight segment is maximal if it is not contained in any other straight segment. Decompose Gw into a union of d maximal overlapping straight segments as follows. Let k1 be the number of tiles in the (cid:27)rst maximal straight segment of Gw, kd the number of tiles in the last maximal straight segment of Gw, and ki + 1 the number of tiles in the ith maximal straight segment of Gw for 1 < i < d. Consider the dual continued fraction CF(w∗) = [K1, K2, . . . , Kd], and assume Kd ≥ 2 (this is no loss of generality, by the formula [a1, a2, . . . , am, 1] = [a1, a2, . . . , am + 1]). Form the continued fraction(cid:99)CF(w∗) = [(cid:98)K1, (cid:98)K2, . . . , (cid:98)K(cid:98)d ] as follows: 94 Figure 8.1: The maximal straight segments of Gw k3 + 1 tiles . . . . . . . . . k2 + 1 tiles ... . . . k1 tiles (1) If K1 = 1, then(cid:98)d = d−1. In this case, the (cid:27)rst entry of(cid:99)CF(w∗) is (cid:98)K1 = K1 +K2 = 1+K2. The last entry of(cid:99)CF(w∗) is (cid:98)K(cid:98)d−1 = Kd. The rest of the entries are (cid:98)Ki = Ki+1 + 1 for (2) If K1 (cid:54)= 1, then(cid:98)d = d. In this case, the (cid:27)rst entry of(cid:99)CF(w∗) is (cid:98)K1 = K1, and the last entry is (cid:98)Kd = Kd. The rest of the entries are (cid:98)Ki = Ki + 1. i (cid:54)= 1, d − 1. The next lemma follows from the previous de(cid:27)nition, duality, and the fact that the entries in CF(w) give a decomposition of Gw into maximal zigzag segments. Lemma 8.1. De(cid:27)ne (cid:98)k1 = k1, (cid:98)kd = kd, and (cid:98)ki = ki + 1 for i such that 1 < i < d. Consider the ] de(cid:27)ned above. Then for each i, we have (cid:98)ki = (cid:98)Ki. continued fraction(cid:99)CF(w∗) = [(cid:98)K1, (cid:98)K2, . . . , (cid:98)K(cid:98)d This result says that the entries in(cid:99)CF(w∗) are the lengths of maximal straight segments in the snake graph Gw. 95 Let the tiles of Gw be T1, T2, . . . , where T1 is the (cid:27)rst tile of Gw. We now recursively de(cid:27)ne for each w a weight function ρw on the vertices of the snake graph Gw which assigns to each vertex of Gw a polynomial in q with positive integer coe(cid:28)cients. This weighting is such that if Gw(cid:48) is a connected subsnake graph of Gw which contains T1 and whose shape contains a total w(cid:48)(q). By Lemma 8.1, these of r instances of “a” and u instances of “b”, then ρw(r + 1, u + 1) = L weights are functions of the entries in CF(w∗). Suppose that Gw begins by going right. Initialize the recurrence with the conditions ρw(0, 0) = 0 and ρw(0, 1) = ρw(x, 0) = 1, for x > 1. Figure 8.2: Initial step in the recurrence ... 1 . . . 0 1 1 1 1 1 1 The remaining vertices in the (cid:27)rst maximal straight segment are determined by the condition ρw(x, 1) = ρw(x, 0) + qρw(x − 1, 1). The outputs of ρw de(cid:27)ned so far are displayed below in Figure 8.3. Recall that each [m]q = 1 + q + ··· + qm−1 is the q-analog of the integer m. Next, ρw(k1 − 1, y) = ρw(k1 − 1, 1) = [k1]q, for each y > 1, and ρw(k1, y) = ρw(k1, y − 1) + qyρw(k1 − 1, y) 96 Figure 8.3: The recurrence for the (cid:27)rst maximal straight segment of Gw ... 1 [2]q [3]q [4]q [k1]q [k1 + 1]q . . . 0 1 1 1 1 1 1 for y > 1. The (cid:27)rst few outputs ρw(k1 − 1, y) = [k1]q and ρw(k1, y) for y > 1 are shown in Figure 8.4. Figure 8.4: The recurrence for the second maximal straight segment of Gw ... [k1]q [k1 + 1]q + q2[k1]q +q3[k1]q . . . [k1]q [k1 + 1]q + q2[k1]q [k1]q [k1 + 1]q . . . 1 1 To compute the weights of the vertices in the third (horizontal) straight segment, we use the same recurrence relation that was used to compute the weights in the (cid:27)rst straight segment, only the initial values are di(cid:29)erent. Similarly, the vertices in the fourth (vertical) straight segment are 97 computed using the second recurrence rule given above, except qy is replaced with qy−k2+1. We continue along in this fashion until all outputs have been computed. A similar recurrence holds when Gw starts by going up. Example 8.2. We use the recurrence just given to compute the lattice path rank function of the snake graph Gw3 from 7.1 above. Figure 8.5: Recursive computation of the rank function Lw3(q) Lw3(q) = [4]q + q[4]q + q2[4]q + q4[3]q = 1 + 2q + 3q2 + 3q3 + 3q4 + 2q5 + q6 [3]q [4]q + q2[3]q [4]q + q[4]q + q3[3]q 1 [2]q [3]q [4]q [4]q [4]q 0 1 1 1 8.2 Hook Rank Formula Now we provide a closed formula for any Lw(q). We continue to assume that Gw starts by going right. Suppose Gw has d straights segments. Say tile Ti has an exposed NW corner if there is one tile glued to its S edge, and one tile glued to its E edge (these three tiles correspond to a subword ba in sh(Gw)). Similarly, we say tile Ti has an exposed SE corner if there is one tile glued to its N edge, and one tile glued to its W edge (corresponding to a subword ab in sh(Gw)). Let NW(Gw) 98 (cid:106) d−1 (cid:107) . For each Ti ∈ NW(Gw), let T SE i 2 be the set of tiles of Gw with an exposed NW corner, and let SE(Gw) be the set of tiles with an exposed SE corner. If Gw starts by going right, then u = |NW(Gw)| = . NW and T i respectively denote the SE and NW corner of Ti. For each i, any lattice path in Lw must pass through either T SE i NW or T i (but not both). This allows us to partition Lw into 2u sets of lattice paths by specifying which corner in each Ti ∈ NW(Gw) a path must pass through. Consider the natural ordering on the tiles NW(Gw) inherited from the ordering of the tiles of Gw. If ti is one of the two corners of some Ti ∈ NW(Gw), then the assignment ti (cid:55)→ 0 if SE induces a poset isomorphism from u-tuples (t1, t2, . . . , tu) ti = T i to Bu, the Boolean lattice of rank u. Here, one element σ2 in Bu covers another σ1 if σ2 can be obtained from σ1 by switching one bit “0” in σ1 to the bit “1”. and ti (cid:55)→ 1 if ti = T NW i We now build another poset H, and give an explicit isomorphism from it to a Boolean lattice. Introduce the following notation: • Hi,i+1 = 1 + q[ki]q[ki+1]q • Hi = [ki]q, • De(cid:27)ne qki+ki+1+1 qki+ki+1 Hi,i+1 = if i (cid:54)= 1 and i + 1 (cid:54)= d if i = 1 or i + 1 = d. 99 De(cid:27)ne a multiplication ◦ on the symbols Hi,i+1. For i < j, de(cid:27)ne Hi,i+1Hj,j+1 q−1(Hi,i+1Hj,j+1) Hi,i+1 ◦ Hj,j+1 = if j (cid:54)= i + 2 if j = i + 2. This new multiplication can be extended to products of more than two symbols.. If no confu- sion will result, we omit the comma appearing in the subscripts and superscripts of these symbols (e.g., we write H23 instead of H2,3). We also omit the symbol “◦” from the computations. Starting with the minimal element if d is odd, or H12H34 . . . Hd−2,d−1Hd H12H34 . . . Hd−3,d−2Hd−1,d if d is even, and interpreting the local procedures HiHi+1 (cid:55)→ HiHi+1, Hi,i+1Hi+2 (cid:55)→ HiHi+1,i+2, HiHi+1,i+2 (cid:55)→ Hi,i+1Hi+2, and Hi,i+1Hi+2,i+3 (cid:55)→ HiHi+1,i+2Hi+3 as covering relations, gives a poset H with additional node structure. 100 We now give an explicit isomorphism between the poset H and the Boolean lattice Bu. Sup- pose for the moment that d is even, so that the minimal element of the poset above is H12H34 . . . Hd−1,d. Send this element H12H34 . . . Hd−1,d to (0, 0, . . . , 0) ∈ Bn. Now sending H1H23H4H56 ··· (cid:55)→ (1, 0, 0, . . . ), H12H3H45H6H78 ··· (cid:55)→ (0, 1, 0, 0, . . . ), etc. induces the aforementioned isomorphism. In other words, each weight in H is given coordinates based on the symbols with upper subscripts that it contains. The assignment is similar when i is odd. Thus, the nodes Hσ of H are indexed by σ ∈ Bu. The next result follows from the above constructions. Theorem 8.3. Fix the word w and consider the rank function Lw(q) of lattice paths on the snake graph Gw. Let Bu be the Boolean lattice of rank u. Recall the symbols Hσ, each parameterized by σ ∈ Bu and representing a polynomial in q with positive integer coe(cid:28)cients. Then we have (cid:88) σ∈Bu Lw(q) = Hσ. Example 8.4. Consider the snake graph Gw and the lattice Lw with its rank function Lw(q). (1) If sh(Gw) = ak1−1bk2ak3−1, then Lw(q) = H12H3 + H1H23. (2) If sh(Gw) = ak1−1bk2ak3bk4−1, then Lw(q) = H12H34 + H1H23H4. 101 (3) If sh(Gw) = ak1−1bk2ak3bk4ak5−1, then Lw(q) = H12H34H5 + H1H23H4H5 + H12H3H45 + H1H23H45. (4) If sh(Gw) = ak1−1bk2ak3bk4ak5bk6−1, then Lw(q) = H12H34H56 + H1H23H4H56 + H12H3H45H6 + H1H23H45H6. Similar formulas can be derived for when Gw starts by going up, e.g., for Gw such that sh(Gw) = bk1−1ak2bk3−1, we have Lw(q) = H1H23 + H12H3. 8.3 Fibonacci Rank Formula The hook expansion formula from the previous section can be re(cid:27)ned to an explicit closed for- mula for Lw(q), as a sum over “face-weighted” products of q-deformations of the entries ki from CF(w)∗. Each term in this formula is the weight of a lattice path L on a zigzag snake graph Gw with d − 1 tiles. By the weight of L, we mean the product of the weights attached to the edges of L, multiplied by the product of face weights in the symmetric di(cid:29)erence L (cid:9) L− (recall L− is the minimal lattice path from De(cid:27)nition 6.6 above). Each edge weight is either equal to 1 or [ki]q for some i, and each [ki]q is used precisely once. Each face weight is either equal to q, or equal to a power of q with exponent equal to the number of tiles in some hook of Gw. The snake graph Gw is built from Gw by (cid:27)rst re(cid:30)ecting Gw about the antidiagonal a1, and then treating Gw as the “middle” lattice path on Gw. This construction in the case that Gw is built from four maximal straight segments is illustrated below. 102 Figure 8.6: The construction of Gw from Gw Gw = qk3+k4−1 [k4]q 1 Gw = 1 1 [k4]q qk3+k4−1 [k3]q 1 qk1+k2−1 [k2]q q 1 [k1]q 1 [k3]q [k2]q q qk1+k2−1 [k1]q Summing over the weights of the paths on this zigzag snake graph gives a closed expression for the rank function Lw(q). Figure 8.7: The poset Gab, its node weights, and the rank function Lw(q) qk1+k2+k3+k4−1 qk1+k2[k3]q[k4]q qk3+k4[k1]q[k2]q q[k1]q[k2]q[k3]q[k4]q [k1]q[k4]q Lw (q) = [k1]q[k4]q + q[k1]q[k2]q[k3]q[k4]q + qk1+k2[k3]q[k4]q + qk3+k4[k1]q[k2]q + qk1+k2+k3+k4−1 In particular, each such rank function expansion has a Fibonacci number of terms, which are arranged into a Fibonacci cube. As mentioned above, the snake graph Gw is canonically 103 associated to the node labeled by aaa . . . a in this Fibonacci cube (see Example 3.45). Let L(Gw) denote the poset of lattice paths on Gw. For any element L ∈ L(Gw), let its weight as described above be denoted qL. Theorem 8.5. Let w be any word. Suppose the snake graph Gw is built from d maximal straight segments. Then the rank function Lw(q) can be written as (cid:88) Lw(q) = qL L∈L(Gw) where Gw is the snake graph with d − 1 tiles de(cid:27)ned above, and L(Gw) is its poset of lattice paths. Proof. This is essentially the hook expansion formula above, except we decompose the set of lattice paths using the corners in NW(Gw) ∪ SW(Gw) instead of just NW(Gw). 104 Chapter 9 Unimodality and Symmetry Recently, Morier-Genoud and Ovsienko gave a new notion of q-deformed continued fractions and rational numbers [27]. The q-deformation [ r is a rational function s ]q is a rational function with in q de(cid:27)ned by a continued fraction formula. It turns out that [ r positive integer coe(cid:28)cients. s ]q of a rational number r s The next result follows from Corollary B.4 in [27] and Theorem 6.22. Theorem 9.1. Recall the notation introduced directly before Theorem 4.5. Then for any w we have and (cid:2)CF(w)(cid:3) q = Pw(q) Pk1 w (q) = L w∗(q) Lk1 w∗(q) (cid:2)CF(w∗)(cid:3) q = P w∗(q) PK1 w∗ (q) = Lw(q) LK1 w (q) . In [27] it was conjectured that the numerator and denominator of any q-deformed rational is a unimodal polynomial (see De(cid:27)nition 7.4). The unimodality of Lw is known to be true in some special cases. For instance, Lw is unimodal if (1) sh(Gw) is straight (trivial), or (2) sh(Gw) is zigzag (Fibonacci cubes are unimodal, see [28]), or 105 (3) Cw∗ is an up-down poset (see [17], and [16] for a relation to Alexander polynomials of 2-bridge knots), a certain class of posets de(cid:27)ned by the division algorithm. Our (cid:27)rst goal in this chapter is to prove that Lw(q) is unimodal in the case that Gw is built from at most four maximal straight segments (in fact, we prove something stronger than unimodality holds). Our second goal is to say when a poset Pw or Lw is symmetric, based on the shape of the underlying snake graph. 9.1 Rank Unimodality We say the sequence (rj) has a plateau if there exists p ≥ 1 such that rj = rj+1 = ··· = rj+p. A plateau is small if p = 1. The sequence (rj) is trapezoidal if (rj) is symmetric and r0 < r1 < ··· < rj = ··· = rn−j > ··· > rn. Say the sequence (rj) is weakly trapezoidal if there exists some t such that r0 < r1 < ··· < rj = ··· = rj+t > ··· > rn such that if n is odd then at least one of the middle two terms r(cid:106) n 2 instead n is even then at least the middle term r n 2 sequence is not assumed to be symmetric. A sequence is almost weakly trapezoidal if is maximal. In particular, a weakly trapezoidal (cid:107) or r(cid:108) n 2 (cid:109) is maximal, and if r0 ≤ r1 < r2 < ··· < rj = ··· = rj+t > ··· > rn−2 > rn−1 ≥ rn. and the subsequence (rj)n−1 j=1 is weakly trapezoidal. Say the sequence (rj) has unimodal growth 106 if the sequence (rj+1 − rj) has one of the two following forms: (a) (1, θ1, . . . , θf , 1, 1, . . . , 1,−1,−1, . . . ,−1, κ1, . . . , κs). (b) (1, θ1, . . . , θf , 1, 1, . . . , 1, 0, 0, . . . , 0,−1,−1, . . . ,−1, κ1, . . . , κs). Here, (θj) forms a positive unimodal sequence with θj ≥ 2 for all j, and similarly for (−κj). The polynomial ρ(q) =(cid:80)n i=0 riqi is said to have a plateau if its sequence of coe(cid:28)cients does, etc. Consider the hook snake graph Gw of shape sh(Gw) = ak1bk2. Let k = min{k1, k2}, and let be the subsnake graph of Gw of shape sh(Gw0) = ak−1bk−1. Let n0 = 2k − 1 be the (odd) Gw0 number of tiles of Gw0 Proposition 9.2. Consider the hook snake graph Gw of shape sh(Gw) = ak1−1bk2−1. Then for k1 ≤ k2 we have . Lw(q) = 1 + q + 2q2 + ··· + k1qk1 + ··· + k1qk2 + ··· + 2qk1+k2−2 + qk1+k2−1. Proof. By Theorem 8.3 we have Lw(q) = 1+q[k1]q[k2]q. Now the claim follows from Proposition 1.5 (1) in [7]. Corollary 9.3. Consider the hook snake graph Gw with n = k1 + k2 − 1 tiles and of shape sh(Gw) = ak1−1bk2−1. Let k = min(k1, k2). (a) The (cid:27)rst and last coe(cid:28)cients of Lw(q) are both equal to 1. (b) The maximum value of the coe(cid:28)cients of Lw(q) is equal to k. (c) The number of times the maximum value occurs is equal to n − n0 + 1 = n − 2k + 2, in degrees k, k + 1, . . . , n − k + 1. 107 (d) The polynomial Lw(q) has at least one small plateau, consisting of the (cid:27)rst two coe(cid:28)cients. If Lw(q) has a second plateau, then each entry of this plateau is equal to the maximum value. There are no other plateaus. (e) The polynomial Lw(q) is almost weakly trapezoidal. In particular, Lw(q) is unimodal. Proof. All parts (a)-(e) follow directly from Proposition 9.2. Example 9.4. Consider Gw with sh(Gw) = a2b5, shown in the leftmost illustration in Figure 9.1 below. The subsnake graph G0 is shown shaded inside G. The middle (cid:27)gure is isomorphic to Lw0, and the rightmost lattice shown is isomorphic to Lw. The maximal coe(cid:28)cient in the polynomial Lw(q) is equal to 3, and this maximal coe(cid:28)cient occurs 4 times. Here, n = 8, n0 = 5, k = k1 = 3, and k2 = 6. Figure 9.1: The snake graphs Gw and G0, and the associated posets Lw0 and Lw n0 + 1 2 = 3 Gw = G0 ∼= Lw0 Lw ∼= |n − n0| + 1 = 4 It is useful to visualize any rank function from a snake graph in terms of stacking square tiles. Each coe(cid:28)cient rj of such a rank function is represented by rj tiles stacked vertically. Figure a2b5(q) from the previous example is built, according to the 9.2 shows how the rank function L expression L a2b5(q) = 1 + q[3]q + q2[3]q + ··· + q6[3]q. 108 Figure 9.2: The rank function L a2b5(q) via block stacking L a2b5(q) = degree 0 1 2 3 4 5 6 7 8 Let n, m ≥ 1, and suppose n = k1 + k2 − 1. Let k = min(k1, k2). De(cid:27)ne the hook subsnake graphs H = Hk1,k2,m of Gw to be of shape ak1−1b a sh(H) = min(m−1,k2−1) min(m−1,k1−1)bk2−1 if k = k1 if k = k2 Let the coe(cid:28)cients of the rank function of lattice paths on Hk1,k2,,m be called Hj(k1, k2, m). that Gw is built from, then sh(H) = sh(Gw). In other words, writing Lw(q) =(cid:80)n Note that when m is equal to or exceeds the length of the longer of the two straight segments j=0 rjqj we have that Hj(k1, k2, m) = rj for m su(cid:28)ciently large. De(cid:27)ne χ = χ(k1, k2, m) by 109  χ = k + m − 1 if m ≤ n − 2k + 2 (cid:98) n+m 2 (cid:99) n if n − 2k + 2 < m < n if n < m and the coe(cid:28)cients 1, (cid:101)Hj(k1, k2, m) = Proposition 9.5. Consider the rank function Lw(q) = (cid:80)n Hj(k1, k2, m), else. if n − 2k + 2 < m < n and 2 | (n + m) and j = n+m 2 j=0 rjqj of the hook snake graph Gw of shape sh(Gw) = ak1−1bk2−1 built from two maximal straight segments of length k1 ≥ 2 and k2 ≥ 2. Let the number of tiles of Gw be n = k1 + k2 − 1. Let k = min(k1, k2) and m ≥ 1. Then we have [m]qLw(q) = [m]q + χ(cid:88) j=1 (cid:101)Hj(k1, k2, m)[n + m − 2j + 1]qqj. In any case, [m]qLw(q) is weakly trapezoidal, and has unimodal growth for m ≥ 2. Furthermore, (a) If m < n− 2k + 2, then [m]qLw(q) has a unique plateau consisting of maximal values, which is of length (n− 2k + 1)− (m− 2) and is situated in degrees k + (m− 1), k + m, . . . , n− k + 1 (b) If m = n − 2k + 2, then [m]qLw(q) has a maximum at degree n − k + 1, and no plateau. (c) If n− 2k + 2 < m < n and 2 (cid:45) n + m, then [m]qLw(q) has a unique (small) plateau, situated in degrees(cid:4) n+m (cid:5) and(cid:6) n+m (cid:7). 2 2 110 (d) If n − 2k + 2 < m < n and 2 | n + m, then [m]qLw(q) has a maximum at degree n+m 2 . (e) If m = n, then [m]qLw(q) has a unique (small) plateau, situated in degrees n − 1 and n. (f) If m = n + 1, then [m]qLw(q) has a maximum at degree n, and no plateau. (g) If m > n + 1, then [m]qLw(q) has a unique plateau, which is of length m − n and situated in degrees n, n + 1, . . . , m − 1. Proof. Write the rank function Lw(q) as Lw(q) = [1]q + q[n]q + q2[n − 2]q + ··· + qk[n − 2k + 2]q, so that the product [m]qLw(q) is [m]qLw(q) = [m]q + q[m]q[n]q + q2[m]q[n − 2]q + ··· + qk[m]q[n − 2k + 2]q. (9.1) min(m,n)(cid:88) [m + n − 2j + 1]qqj−1. j=1 [m]q[n]q = (9.2) From [7] we have Explicitly, • If m < n, then [m]q[n]q = [n + (m − 1)]q + q[n + (m − 3)]q + ··· + qm−1[n − (m − 1)]q. 111 • If m = n, then • If m > n, then [m]q[n]q = [n]2 q = [2n − 1]q + q[2n − 3]q + ··· + qn−1[1]q. [m]q[n]q = [m + (n − 1)]q + q[m + (n − 3)]q + ··· + qn−1[m − (n − 1)]q. We consider seven cases, based on the value of m relative n − 2k + 2 and n, and the parity of the sum n + m. In each case we use Equation 9.3 above to expand each product of q-numbers in Equation 9.1 and collect like terms to obtain the formula. This is shown explicitly in the (cid:27)rst case only, as the rest are similar. (a) m < n − 2k + 2 : Here, the statement is [m]qLw(q) = [m]q + Hj(k1, k2, m)[n + m − 2j + 1]qqj. k+m−1(cid:88) j=1 112 Using (2) to expand each term qj[m]q[n − 2j]q in (1) and collecting like terms gives the desired expression for [m]qLw(q): 1 + q j=1 (cid:16) (cid:16) (cid:16) 1 + 1 + [m]qLw(q) = [m]q = [m]q = [m]q = [m]q + = [m]q + = [m]q + k+m−1(cid:88) j=1 ρ(q) . = Now let j=1 [(k1 + k2) − 2j + 1]qqj−1(cid:17) k(cid:88) [(k1 + k2 − 1) − 2j + 2]qqj(cid:17) k(cid:88) [n − 2j + 2]qqj(cid:17) k(cid:88) k(cid:88) m(cid:88) k(cid:88) [n − 2(i + j − 1) + 1]qqi+j−1 k+m−1(cid:88) [m]q[n − 2j + 2]qqj j=1 i=1 j=1 j=1 j=1 Hj(k1, k2, m)[n + m − 2j + 1]qqj. Hj(k1, k2, m)[n + m − 2j + 1]qqj (9.3) Note that when we increment j in this sum, the power of q goes up by one, while the term inside the bracket decreases by two. This fact, along with the fact that the coe(cid:28)cients Hj(k1, k2, m) form a weakly trapezoidal sequence, shows that ρ(q) is weakly trapezoidal with unimodal growth. In particular, the degrees of the terms whose coe(cid:28)cients make up the unique plateau of ρ(q) are exactly the powers of q occurring in the last term qk+m−1[n − m − 2k + 3]. Thus we read o(cid:29) that ρ(q) has a plateau of maximal coe(cid:28)cients of length (n− 2k + 1)− (m− 2) situated in degrees k + (m − 1), k + m, . . . , n − k + 1. 113 Since k > 1 we have m− 1 < m < n− 2k + 2 < n− k + 1, so that adding the chain [m]q to ρ(q) does not disturb the plateau of maximal coe(cid:28)cients of ρ(q). In other words, [m]q +ρ(q) has the same plateau of maximal coe(cid:28)cients as ρ(q). Since the coe(cid:28)cients Hj(k1, k2, m) form a weakly trapezoidal sequence, no other plateaus are created by adding the chain [m]q to ρ(q). Hence [m]qLw(q) is weakly trapezoidal with unimodal growth, as claimed. (b) m = n − 2k + 2: In this case the formula can be computed to be [m]qLw(q) = [n − 2k + 2]q + Hj(k1, k2, m)[2n − 2k − 2j + 3]qqj, n−k+1(cid:88) = (cid:80)n−k+1 j=1 . j=1 Hj(k1, k2, m)[2n − 2k − 2j + 3]qqj is and the last term in the sum ρ(q) [1]qqn−k+1. Thus, ρ(q) has a maximum at degree n − k + 1. Just as before, adding the chain [n − 2k + 2]q to ρ(q) does not disturb the unique plateau of maximal coe(cid:28)cients of ρ(q). Since the coe(cid:28)cients Hj(k1, k2, m) are weakly trapezoidal, no other plateaus are created by adding [m]q to ρ(q). Thus the claim holds in this subcase as well. (c) n − 2k + 2 < m < n and 2 (cid:45) n + m : If n and m have opposite parity then there exists some c such that n − 2c < m = n − 2c + 1 < n − 2c + 2. Using Equation 9.3, we see that [m]qLw(q) = [m]q + n−c(cid:88) j=1 Hj(k1, k2, m)[n + m − 2j + 1]qqj. This matches the form given in the statement, since 2 (cid:45) n + m implies 114 2 (cid:99) = n+m−1 (cid:98) n+m that [m]qLw(q) is weakly trapezoidal with unimodal growth. = n+(n−2c+1)−1 2 2 = n − c. Again by using a degree argument we see (d) n − 2k + 2 < m < n and 2 | n + m : If 2 | m + n then there exists some c such that m = n − 2c. As in the previous case we use 9.3 to write [m]qLw(q) = [m]q + Hj(k1, k2, m)[n + m − 2j + 1]qqj, n−c(cid:88) j=1 except that now 2 | n + m so that n+m degree n+m can be seen by computing the last term [1]qq 2 2 = n − c. That the maximum of Lw(q) occurs in n+m 2 in the sum. (e) m = n : Using Equation 9.3 gives n(cid:88) [m]qLw(q) = [n]q + rj[2n − 2j + 1]qqj. j=1 The last term in the above sum (cid:80)n (cid:80)n j=1 rj[2n − 2j + 1]qqj is [1]qqn, which shows that j=1 rj[2n − 2j + 1]qqj has a maximum in degree n. That the last two terms are [1]qqn and 2[3]qqn−1 implies that whatever the maximum coe(cid:28)cient is, the previous coe(cid:28)cient is one less. Now adding [n]q = [n− 1]q + qn−1 to the sum(cid:80)n j=1 rjqj[2n− 2j + 1]q and again considering the term [3]qqn−1 shows that the small plateau in question exists, in degrees n− 1 and n as claimed. That it is unique follows easily, as does the fact that the polynomial [m]qLw(q) is weakly trapezoidal with unimodal growth. (f) m = n + 1 : In this case we have [m]qLw(q) = [n + 1]q + 115 n(cid:88) j=1 rj[2n − 2j + 2]qqj. . =(cid:80)n To see that [m]qLw(q) has a unique maximum coe(cid:28)cient, consider the last term qn[2]q j=1 rjqj[2n − 2j + 2]q. It follows that ρ(q) has a unique maximal from the sum ρ(q) plateau in degrees n and n+1. Now adding the chain [n+1]q = [n]q +qn to ρ(q) shows that [n + 1]qLw(q) has a unique maximum coe(cid:28)cient, in degree n. That [m]qLw(q) is weakly trapezoidal with unimodal growth follows immediately. (g) The formula here is [m]qLw(q) = [m]q + n(cid:88) j=1 rj[n + m − 2j + 1]qqj. Again, the last coe(cid:28)cient [m − n + 1]qqn tells us the behavior of the plateau of the sum above, and the claim follows. Example 9.6. In Figure 9.3 below, we show the e(cid:29)ect of multiplying the rank function L by [m]q for 1 ≤ m ≤ 12. We have indicated each plateau of maximal coe(cid:28)cients of [m]qL for 1 ≤ m ≤ 9 = n + 1 with a bold line. a2b5(q) a2b5(q) Theorem 9.7. Consider the snake graph Gw and the rank generating function Lw(q). (a) Suppose the snake graph Gw with n = k1 + k2 + k3 − 1 tiles has the shape sh(Gw) = ak1−1bk2ak3−1, where k1 ≥ 2, k2 ≥ 1, and k3 ≥ 2. Then the polynomial Lw(q) is weakly trapezoidal with unimodal growth. In particular, Lw(q) is unimodal. (b) Suppose the snake graph Gw with n = k1 + k2 + k3 + k4 − 1 tiles has the shape sh(Gw) = ak1−1bk2ak3bk4−1. Then the polynomial Lw(q) = (cid:80)n j=1 is weakly trapezoidal with uni- modal growth. In particular, Lw(q) is unimodal. 116 Figure 9.3: The rank function [m]qL a2b5(q) for 1 ≤ m ≤ 12 Proof. (a) By Theorem 8.3 we can write Lw(q) = [k3]q By Proposition 9.5 we have (cid:16) (cid:17) + qk2+k3[k1]q. 1 + q[k1]q[k2]q Lw(q) = ρ(q) + qk2+k3[k1]q where ρ(q) is the weakly trapezoidal polynomial ρ(q) . = [k3]q + with unimodal growth. (cid:101)Hj(k1, k2, k3)[n − 2j + 1]qqj χ(cid:88) j=1 117 Note that the highest power occurring in qk2+k3[k1]q is qk1+k2+k3−1, which is one higher than the degree of ρ(q). This remark, along with the fact that the coe(cid:28)cients Hj(k1, k2, k3), have unimodal growth, implies that adding the chain qk2+k3[k1]q to ρ(q) does not create any new plateaus. In particular, Lw is unimodal. (b) Let Gw(cid:48) be the subsnake graph of Gw obtained by deleting the (cid:27)rst k1 tiles from Gw, and Gw(cid:48)(cid:48) the subsnake graph of Gw(cid:48) obtained by deleting the (cid:27)rst k1 + k2 − 1 tiles from Gw. Set ρ(cid:48)(q) = L w(cid:48)(q) and ρ(cid:48)(cid:48)(q) = L w(cid:48)(cid:48)(q). By the recurrence relation above we can write (cid:18) (cid:19) Lw(q) = [k1]qq ρ(cid:48)(q) + ρ(cid:48)(cid:48)(q). By part (a), ρ(cid:48)(q) is weakly trapezoidal with unimodal growth. It is clear that multiplying ρ(cid:48)(q) by q[k1]q preserves these properties. Note that ρ(cid:48)(q) = [k2]q 1 + q[k3]q[k4]q + qk2+k3[k4]q. (cid:18) (cid:19) In particular ρ(cid:48)(q) is built from ρ(cid:48)(cid:48)(q) = 1 + q[k3]q[k4]q by (cid:27)rst multiplying by [k2]q and then adding to the result the chain qk2+k3[k4]q. Since k2 ≥ 2, the degree of the (cid:27)rst entry of the plateau of ρ(cid:48)(q) is weakly larger than the degree of the (cid:27)rst entry of the plateau of ρ(cid:48)(cid:48)(q). Multiplying ρ(cid:48)(q) by [k1]qq can only shift the start of the plateau of ρ(cid:48)(q) further to the right, implying that the start of the plateau of(cid:0)[k1]qq(cid:1)ρ(cid:48)(q) is to the right of the start of the plateau of ρ(cid:48)(cid:48)(q). If the two plateaus in question overlap or are adjacent, then we are done. Otherwise, the lowest degree occurring in the plateau of(cid:0)[k1]qq(cid:1)ρ(cid:48)(q) is strictly larger than max(k3, k4). In this case, the unimodal growth of the coe(cid:28)cients of(cid:0)[k1]qq(cid:1)ρ(cid:48)(q) ensures that the addition 118 of ρ(cid:48)(cid:48)(q) (whose consecutive coe(cid:28)cients are at most one apart) preserves the two properties in question. Hence, Lw is unimodal in this case. 9.2 Rank Symmetry De(cid:27)nition 9.8. Fix a word w = w1w2 . . . wn−1 of length l(w) = n − 1. De(cid:27)ne the three words wT = w∗ 1w∗ 2 . . . w∗ n−1, w◦ = wn−1wn−2 . . . w1, and w = w∗ n−1w∗ n−2 . . . w∗ 1. We say that w is symmetric if w◦ = w, and self-conjugate if w = w. We say that Gw is symmetric if sh(Gw) is symmetric, and self-conjugate if sh(Gw) is self-conjugate. Example 9.9. The word w1 = sh(Gw1)∗ = aab from Example 7.5 is neither symmetric nor self-conjugate, while w2 = sh(Gw2)∗ = aabb is self-conjugate and w3 = sh(Gw3)∗ = baaab is symmetric. The word sh(Gw1) = w∗ 1 = baa is neither symmetric nor self-conjugate, while the words sh(Gw2) = w∗ Proposition 9.10. Fix the word w of length l(w) = n− 1. Recall the internal edges e1, e2, . . . en−1 2 = baab and sh(Gw3) = w∗ 3 = aabaa are both symmetric. of the snake graph Gw (see the discussion before De(cid:27)nition 3.25 above). (a) Suppose l(w) is odd. Then the word w = sh(Gw)∗ is symmetric if and only if the word w∗ = sh(Gw) is symmetric. 119 (b) If l(w) is odd and w is symmetric, then Gw has 180◦ rotational symmetry about the midpoint of its middle internal edge, and the same is true for G∗ w. (c) Suppose l(w) is even. Then the word w = sh(Gw)∗ is symmetric if and only if the word w∗ = sh(Gw) is self-conjugate, and w = sh(Gw)∗ is self-conjugate if and only if w∗ = sh(Gw) is symmetric. (d) If l(w) is even and w is symmetric, then Gw is symmetric about the diagonal of its center tile , and G∗ w has 180◦ rotational symmetry about the center of its middle tile T n+1 2 . T n+1 2 (e) The snake graph Gw has 180◦ rotational symmetry if and only if Cw∗ has 180◦ rotational symmetry. In this case, the graded poset Lw is order-theoretically self-dual. Proof. (a) If w is symmetric of odd length, then setting m = l(w)+1 2 we can write w = w1w2 . . . wm−1wmwm−1 . . . w2w1. If m is even, then taking the dual of w gives w∗ = w∗ 1w2 . . . w∗ m−1wmw∗ m−1 . . . w2w∗ 1, which is symmetric. Similarly, if m is odd then taking the dual gives w∗ = w∗ 1w2 . . . wm−1w∗ mwm−1 . . . w2w∗ 1, which is also symmetric. Taking dual words now gives (a). (b) Follows directly from (a). 120 (c) If l(w) is even and symmetric, then for m = l(w) 2 we can write w = w1w2 . . . wm−1wmwmwm−1 . . . w2w1. Suppose m is even. Then taking the dual gives w∗ = w∗ 1w2 . . . w∗ m−1wmw∗ mwm−1 . . . w∗ 2w1, which is self-conjugate. Similarly, if m is odd, then taking the dual of w gives w∗ 1w2 . . . wm−1w∗ mwmw∗ m−1 . . . w∗ 2w1, which is again self-conjugate. (d) Follows directly from (c). (e) By construction, Gw has 180◦ symmetry if and only if C∗ w be Gw rotated by 180◦. The result now follows from noting that the order-theoretic dual of Lw is isomorphic to the poset of lattice paths on G◦ w. w does. Let G◦ Corollary 9.11. Consider the words w and w∗ of length n− 1, the associated snake graphs Gw and w with n tiles, and the distributive lattices Dw ∼= Pw ∼= L G∗ w∗ of rank n. w∗ and Dw∗ ∼= Lw ∼= P (a) If sh(Gw) is symmetric, then the poset Lw is symmetric. (b) If either l(w) is odd and sh(Gw) is symmetric, or l(w) is even and sh(Gw) is self-conjugate, then the poset Pw is symmetric 121 Proof. Follows directly from Proposition 9.10. Example 9.12. (a) The lattice path expansion on a zigzag snake graph with an even number of tiles is isomorphic to a Fibonacci cube of even order, and so is symmetric (this was shown in [28]). Trivially, the perfect matching expansion poset on this snake graph is symmetric, since it is a chain. (b) Consider the snake graph Gw with the word CF(w) = [a1, a2, . . . , ak]. Following [6], the palindromi(cid:27)cation of Gw is the snake graph G↔ with associated continued fraction [an, an−1, . . . , a2, a1, a2, . . . , an−1, an]. Every palindromi(cid:27)cation G↔ has 180◦ symmetry about its center tile (see Theorem A in [6]). Let L↔ be the poset of lattice paths on G↔. Then by Corollary 9.11, we know that L↔ are symmetric. Since l(w) is even, the poset P↔ of perfect matchings on the palindromi(cid:27)cation is not symmetric. (c) Consider a p by q grid, where p and q are relatively prime positive integers with p < q. The Christo(cid:29)el path is the unique lattice path from (0, 0) to (p, q) which has no lattice points between it and the line segment between (0, 0) and (p, q). The Markov snake graph is built , "on top" of this path (see De(cid:27)nition 4.1.in by placing tiles, each with side length equal to 1 2 [34]). For more on Markov snake graphs, see [33], [6], and [34]. Figure 9.4 shows one example of a Markov snake graph. The number of perfect matchings on any Markov snake graph is equal to a Markov number. Every Markov snake graph is a palindromi(cid:27)cation (see [6]), so the conclusions in (b) hold here as well. 122 Figure 9.4: A Markov snake graph (d) It is well-known that the in(cid:27)nite continued fraction expansion of √ 2 is equal to √ 2 = [2, 2, 2, 2, . . . ]. The latter in(cid:27)nite fraction is [1, 2, 2, 2, . . . ]. Thus, we may write 1 + called the silver mean. Consider any of the continued fractions obtained by truncating the continued fraction expansion of the silver mean after an odd number (larger than 1) of 2’s. An example of a snake graph associated to such a continued fraction is shown below. Figure 9.5: The snake graph with continued fraction [2, 2, 2, 2, 2] By Corollary 9.11, the perfect matching poset on the associated snake graph is symmetric, while the lattice path expansion poset on this snake graph is not symmetric. 123 Chapter 10 Expansion Posets as Groupoid Orbits In this short chapter, we give an interpretation of the support of the cluster variable xw as an orbit of a groupoid. This implies that the support of any two distinct cluster variables written with respect to the same initial seed are disjoint, so that in particular any xw can be completely reconstructed from any one of its monomials. De(cid:27)nition 10.1. A groupoid is a category such that every morphism is invertible. Consider the set of Laurent monomials from the extended cluster (x1, x2, . . . , xn, xn+1, . . . , x2n+3). For each k with 1 ≤ k ≤ n, de(cid:27)ne the element ˆyk = (see [15]). (cid:81) (cid:81) i→k xi k→j xj . (10.1) De(cid:27)ne a groupoid F whose objects are the Laurent monomials from the extended cluster above. There is a morphism xM −→ xM(cid:48) between two Laurent monomials xM and xM(cid:48) if xM(cid:48) = ˆykxM or xM(cid:48) = ˆyk (cid:48) has the following properties: −1xM for some ˆyk, such that the reduced fraction x M 124 (1) No frozen variable appears in the denominator of xM(cid:48). (2) No frozen variable which appears in the numerator of xM(cid:48) is squared. The rest of the morphisms in F are compositions of such multiplications. For any xw, let Supp(xw) be the set of Laurent monomials in the Laurent expansion of xw. Theorem 10.2. Consider the cluster variable xw. Let xM ∈ Supp(xw), and let O(xM ) be the connected component of F containing xM . Then Supp(xw) = O(xM ). Proof. Let xM(cid:48) ∈ Supp(xw). If we represent both xM and xM(cid:48) as T-paths, then there is some sequence of T-path twists that takes xM to xM(cid:48). Notice that if two T-paths are related by a twist then there is a morphism between their respective weights. Indeed, T-path twists algebraically are multiplication by some ˆyk as in Equation 11.8, and furthermore a T-path has no red boundary edges nor does it use the same (blue) edge twice. Thus, there is a morphism xM(cid:48) −→ xM and so xM(cid:48) ∈ O(xM ). The reverse inclusion is similar. Corollary 10.3. Any cluster variable xw is completely determined by any one of its monomials. 125 Chapter 11 Some T -paths for Con(cid:27)gurations of Flags The work in this chapter is joint with Nicholas Ovenhouse. In [9], a generalization of the decorated Teichmüller spaces was introduced, called higher Teichmüller spaces. These moduli spaces take as input in their construction a Lie group G and a marked surface S. It was shown in [9] that when G = SLn, the coordinate ring of this moduli spaces has a cluster structure. Here we focus on the case when G = SL3 and S is a disc with marked points on the boundary. In this case, the moduli space reduces to the moduli space of con(cid:27)gurations of a(cid:28)ne (cid:30)ags. In this (cid:27)nal chapter, our (cid:27)rst goal is to give a Laurent expansion formula which generalizes the T-path formula from Section 4.3, in the special case when the initial seed is constructed from a fan triangulation. Our second goal is to describe the poset structure of some of these Laurent expansions. 11.1 Decorated Teichmüller Spaces De(cid:27)nition 11.1. Let Σ be a marked surface of genus g with b boundary components and m marked points located on boundary components, where each boundary component has at least one marked point. The Teichmüller space is the space of marked complete metrics on Σ having constant negative curvature −1 and a (cid:27)nite area, modulo the action of the connected component of the identity in the group of di(cid:29)eomorphisms of Σ. Denote this space by T m g,b. 126 De(cid:27)nition 11.2. Let Σ, g, b, m be as above. Let p be a marked point which is a cuspidal point on the boundary of Σ. A horocycle centered at p is a circle orthogonal to any geodesic passing through p. Any horocycle centered at p can be parameterized by a positive real number called the and is de(cid:27)ned as the height of the horocycle. The decorated Teichmüller space is denoted by(cid:103)T m total space of the trivial (cid:27)ber bundle(cid:103)T m where the projection map is forgetting about g,b g,b horocycles. Each (cid:27)ber is isomorphic to Rm + (cid:16) T m . g,b We now recall the construction of Penner coordinates on the decorated Teichmüller space. Let ∆ be an ideal triangulation of Σ triangulated by geodesic arcs. Each edge e of the ideal triangulation has in(cid:27)nite hyperbolic length. However, we can de(cid:27)ne the length l(e) of e to be the signed (cid:27)nite length of the segment between the two horocycles centered at the endpoints of e, where the sign of l(e) is positive if the two horocycles don’t intersect, and negative if they do. De(cid:27)ne f (e) = exp(cid:16) l(e) (cid:17) . The functions f (e) where e ranges over the edges in the triangu- lation ∆ give a homeomorphism from the decorated Teichmüller space to R6g+3b+2m−6. The functions f (e) are called Penner coordinates, or lambda lengths. 2 Any two Penner coordinates attached to the two arcs p and q involved in a (cid:30)ip of the under- lying ideal triangulation are related by a generalized Ptolemy relation: f (p)f (q) = f (a)f (c) + f (b)f (d), where arcs a and c (respectively, b and d) are opposite one another in the unique quadrilateral with edges from ∆ determined by the arcs p and q. De(cid:27)nition 11.3. The cluster algebra structure on (cid:103)T m , denoted A((cid:103)T m g,b g,b), is given by building a quiver, depending on ∆ as before, but with nodes now labeled by Penner coordinates. When Σ is a disc with marked points on the boundary, we have the following correspon- 127 dences: cluster variables in A((cid:103)T m seeds of A((cid:103)T m seed mutations in A((cid:103)T m g,b) ←→ Penner coordinates of arcs in ∆ g,b) ←→ triangulations of ∆ g,b) ←→ (cid:30)ips in ∆ 11.2 Higher Teichmüller Spaces We recall in this section a generalization of Teichmüller spaces introduced in [9]. De(cid:27)nition 11.4. Let G be a Lie group, and S a marked surface. The space of G-local systems on S is the character variety Hom(π1(S), G)/G, where the quotient is by conjugation. The moduli space M de(cid:27)ned in [9] parameterizes local systems on S with some additional structure, namely a choice of element in the quotient G/U for each marked point. Here, U = [B, B] is the unipotent radical of a Borel subgroup B ⊂ G. When G = SLn, the quotient G/U parameterizes a(cid:28)ne (cid:30)ags. De(cid:27)nition 11.5. An a(cid:28)ne (cid:30)ag in a vector space V is a saturated chain of subspaces V1 ⊂ V2 ⊂ ··· ⊂ Vn−1 ⊂ Vn = Rn, along with a choice of nonzero vector vi ∈ Vi+1/Vi in each successive quotient for 1 < i < n−1. When G = SL2, the space M parameterizes con(cid:27)gurations of a(cid:28)ne (cid:30)ags in R2. Note that an a(cid:28)ne (cid:30)ag in R2 is simply a choice of non-zero vector. The surface type cluster algebras we have considered in the previous chapters may be interpreted as rings of functions on M. 128 Fix G = SL3 for the remainder of this chapter. In [9], it was shown that in this case the coordinate ring of M has a cluster algebra structure. We now describe how to construct a seed for this cluster algebra. As we have seen, when G = SL2 the nodes of the quiver associated to a triangulation are in one-to-one correspondence with the arcs (and boundary segments) of the triangulation, and the arrows of this quiver form clockwise 3-cycles inside the triangles of the triangulation. Instead, when G = SL3, each arc has two quiver nodes associated to it, and furthermore there is a vertex of the quiver for each triangle cut out by the triangulation. Now, each ideal triangle cut out by the triangulation has three 3-cycles contained within it, each having the internal face vertex in common. This quiver is called a 3-triangulation. Figure 11.1: A 3-triangulation Flips of the triangulation are now governed not by a single quiver mutation, but by a sequence of four mutations. More precisely, to perform a (cid:30)ip of the triangulation at the diagonal δi, one must (cid:27)rst mutate at both quiver vertices along the diagonal δi, and then subsequently mutate at the two vertices inside the triangles on either side of the diagonal δi. As for traditional surface cluster algebras, any cluster variable we are now considering may be expressed in terms of the initial cluster variables attached to this initial triangulation, via the (cid:30)ips and their governing mutation sequences just described. 129 11.3 Colored SL3 Diagrams Refer to the two initial cluster variables attached to any edge δi of the triangulation as directed edges, and call any cluster variable attached to the interior of a triangle a face. Each edge variable is visualized as a directed edge which is directed away from the endpoint of δi that it is closest to. Each face variable is visualized as a “(cid:27)lling” of the triangle containing it. We visualize Laurent monomials in the initial cluster variables by representing each variable in such a monomial as just described, and superimposing each such representation onto the same diagram. Variables occurring in the numerator of a Laurent monomial will be pictured as blue, and those in the denominator will be pictured as red. Figure 11.2: Visualization of a Laurent monomial c b a ab c Any non-initial cluster variable may now be resolved with respect to the initial triangulation. That is, it can be expressed as a sum over products of directed edges and faces from the initial triangulation. Figure 11.3 shows the result of resolving a non-initial face in a triangulated square. 130 Figure 11.3: Face resolution = + Figure 11.4 shows the result of resolving a non-initial directed edge in a triangulated square. Figure 11.4: Edge resolution = + + + A general non-initial variable may be resolved by choosing an internal diagonal from ∆ that it crosses (explained in the next subsection), and resolving this crossing inside the quadrilateral determined by the non-initial variable and the internal diagonal. This process is repeated until all elements are part of ∆. De(cid:27)nition 11.6. Fix a triangulation ∆ of the polygon Σ. A colored SL3 diagram is a multiset of colored directed edges and triangular faces from ∆ drawn superimposed on the same polygon, where each such element is colored either blue or red. By the above discussion, colored SL3 diagrams are in bijection with the set of Laurent mono- mials built from the initial cluster variables attached to the triangulation ∆. The weight of the SL3 diagram π is the associated Laurent monomial xπ. 11.4 Crossings in Colored SL3 Diagrams From now on, we restrict to fan triangulations ∆ (see De(cid:27)nition 3.14). 131 In this section, we say what it means for two colored SL3 diagrams inside a fan triangulation to be “crossing”. De(cid:27)nition 11.7. Two directed arcs i → j and k → l are said to be crossing if the underlying directed arcs are crossing in the usual sense. De(cid:27)nition 11.8. A directed arc i → j and a face pqr are said to be crossing if i = p and q < j < r cyclically, i.e., (1) i → j begins at one of the vertices of the triangle pqr, and (2) i → j has nontrivial intersection with the interior of pqr. See the next (cid:27)gure for an illustration of De(cid:27)nition 11.8. Figure 11.5: A directed edge and a face which cross p = i j r p r q q j i 11.5 Fork-Join Networks It is often convenient to model a simple process, algorithm, or computer program by a directed graph which encodes precedence. That is, the vertices are the states, and the edges are directed so that i → j means that i must happen before j. In this way, a directed path i1 → i2 → ··· → in models an algorithm which is totally sequential (the steps have a de(cid:27)nite order). 132 In an algorithm which utilizes parallelism, such as multithreading, the main procedure may fork, creating a child process. After this, the main procedure and the child process may execute in parallel. It may be necessary for the parent and child to join at some point before continuing. This means that the parent and child must each (cid:27)nish their concurrent tasks before the main algorithm carries on in a sequential manner. The next (cid:27)gure shows an example of a general fork-join network. Figure 11.6: A fork-join network We will only consider fork-join networks with the following two properties: (A1) any fork must later be accompanied by a join, and (A2) there are no nested forks. From now on, whenever we say “fork-join network” we will mean a fork-join network satis- fying these two restrictions. See the next (cid:27)gure for an example of such a fork-join network. Figure 11.7: A fork-join network satisfying conditions (A1) and (A2) N De(cid:27)nition 11.9. An alternating fork-join network is a directed graph Ω with the same underlying undirected graph as some fork-join network N such that 133 (1) For any directed path through N from beginning to end, the odd-numbered edges of Ω are oriented the same as the corresponding edge in N, and the even-numbered edges are oriented opposite. (2) For any fork in N, the edge going into the fork must be inverted in Ω. (3) For any join in N, the edge leaving after the join must not be inverted in Ω. We color each directed edge of an alternating fork-join network blue or red, according to the following rules. (1) The (cid:27)rst arrow is colored blue. (2) Away from the fork and join, colors alternate along paths. (3) At a fork or join, the three edges incident that vertex are all colored the same color. Figure 11.8: Construction of an alternating fork-join network Ω N Ω We say that a fork-join pair in an alternating fork-join network Ω is triangular if at least one edge from the fork is immediately followed by one edge from the join. An alternating fork-join network in which every fork-join pair is triangular is called triangular. For instance, the fork-join network in Figure 11.8 is triangular. 134 Let Ω1 and Ω2 be two directed graphs. A homomorphism of directed graphs g : Ω1 −→ Ω2 is a mapping of vertex sets such that if i → j in Ω1, then g(i) → g(j) is an edge of Ω2. De(cid:27)nition 11.10. A homomorphism of directed graphs g : Ω1 −→ Ω2 is called an immersion if for any vertex v ∈ Ω1, every vertex incident to v maps to a distinct vertex under g. If Ω1 is an alternating fork-join network, then we require that g preserves edge colors. De(cid:27)nition 11.11. Let Ω1 be an alternating fork-join network, and Ω2 any directed graph. Sup- pose that g : Ω1 −→ Ω2 is an immersion. The image of g is the associated multiset of edges in Ω2. That is, if i → j is an edge in Ω1, then g(i) → g(j) is an edge in Ω2, and if more than one edge from Ω1 maps to g(i) → g(j), then we count the edge g(i) → g(j) with multiplicity equal to the cardinality of its preimage. 11.6 Generalized T -paths We now generalize to our current setup the T-paths from Section 4.3. To this end, we picture each face variable as a tripod, as shown in the next (cid:27)gure. Each tripod resembles a web diagram from [10] and [11]. Figure 11.9: Faces as webs = Given the triangulation ∆, de(cid:27)ne the directed graph Ω∆ as follows. There is one vertex of Ω∆ for each vertex of ∆, and one vertex per triangle cut out by ∆. For each edge in ∆ (including boundary segments) connecting vertices i and j, there is a pair of directed edges i → j and j → i. 135 For each triangle ijk cut out by ∆, there is a tripod consisting of three edges directed from the center vertex of the triangle to the three vertices i, j, and k. Note that if g : Ω −→ Ω∆ is an immersion of a fork-join network, then the image is a colored SL3 diagram. De(cid:27)nition 11.12. Consider the fan triangulation ∆. Let k be the fan vertex of ∆, i.e., the unique vertex of the polygon which is an endpoint of every diagonal in ∆. Let a → b be the longest edge, crossing each internal diagonal of ∆. Suppose Ω is an alternating fork-join network, and Ω → Ω∆ is an immersion, which sends the source of Ω to a and the terminal vertex of Ω to b. We call the image of this immersion a T -path of edge type from a to b if the following are true. (T1) The image of any path through Ω does not use any edge of Ω∆ more than once. (T2) There are an odd number of elements in the diagram. (T3) The red elements cross the directed arc a → b. (T4) Once a path traverses an internal diagonal in ∆, it never returns to the original half of the polygon (the half determined by the diagonal in question that is closest to a). (FJ1) Any fork or join vertex of Ω maps to a vertex of Ω∆ inside a face of ∆, and the image of any other vertex does not lie inside any face of ∆. (FJ2) Ω has at most one fork-join pair, which must be triangular. (FJ3) If Ω has a fork-join pair, then one of the two blue directed boundary edges along the triangle containing the red fork must be present. The set of edge-type T-paths from a to b is denoted by Ta→b. Figure 11.10 shows two edge-type T-paths. Note that the T-path pictured on the right is an immersion of the alternating fork-join network Ω pictured in Figure 11.8. 136 Figure 11.10: Two edge-type T-paths a b a b Label the diagonals δi which are incident to k, the corresponding endpoint di (cid:54)= k of each δi, and the triangles ∆i of ∆, as indicated in the next (cid:27)gure. Figure 11.11: A generic fan triangulation with diagonals δi d0 δ0 ∆0 δ1 d1 ∆1 δ2 . . . δ5 δ3 δ4 d2 δn+1 dn+1 ∆n δn δn−1 dn dn−1 One can check that for any edge-type T-path, either there are no forks or joins and the un- derlying directed edges form a SL2 T-path from a to b; or, it can be constructed by the following algorithm: (E1) Add the blue edge a → k to the triangulation. Then, add the red edge di → k for some i (cid:54)= n, n + 1. In particular, we may have a = di so that the two edges cancel each other. 137 Figure 11.12: Step (E1) . . . (E2) Add in the red tripod inside ∆i, along with three more directed edges, two blue and one red, in either of the two ways shown in Figure 11.13. To be precise, we either add the two blue edges k → di and di → di+1 and the red edge k → di+1; or, we add the two blue edges di+1 → di and di → k and the red edge di+1 → k. Figure 11.13: The two choices in Step (E2) or If we superimpose the (cid:27)rst diagram in Figure 11.13, we obtain the diagram shown in the next (cid:27)gure. 138 Figure 11.14: The result of superimposing the edges from the left diagram in Figure 11.13 . . . If instead we superimpose the second diagram from Figure 11.13, we obtain the diagram shown in Figure 11.15 instead. Figure 11.15: The result of superimposing the edges from the right diagram in Figure 11.13 . . . (E3) Lastly, choose any triangle ∆j such that j > i, and add to the diagram constructed thus far the blue tripod inside ∆j, along with the two red edges k → dj and k → dj+1, and the two blue edges k → dn+1 and k → di+1. If we superimpose this collection onto the diagram in Figure 11.14, we obtain the diagram in the next (cid:27)gure. 139 Figure 11.16: The result of superimposing onto the diagram from Figure 11.14 the edges from (E3) . . . If instead we superimpose this collection onto the diagram from Figure 11.15, we obtain the diagram in the next (cid:27)gure. Figure 11.17: The result of superimposing onto the diagram from Figure 11.15 the edges from (E3) . . . Note that the set Ta→b has (n + 1)2 elements. Indeed, the number of T-paths without a fork-join pair (which resemble the T-paths from Section 4.3) is n + 1. Furthermore, it is clear from the construction that any other edge-type T-path (i.e., one which contains a fork-join pair) is determined by which choice from Figure 11.13 we make, along with the choice of which two triangles from ∆ to respectively place the fork and join in. Thus, there are 2(cid:0)n+1 (cid:1) = n(n + 1) 2 such T-paths. 140 11.7 An Expansion Formula for Arcs in Fan Triangulations In this section, we give an expansion formula valid for any arc in a fan triangulation. First, we give a lemma concerning the terms resulting from resolving the “fan face” in a fan triangulation. Lemma 11.13. Consider the fan triangulation ∆ with n internal diagonals. Adopt the notation from Figure 11.11. Let k be the fan vertex. Let a and b be the two vertices of the polygon which are not incident to any internal diagonal of ∆. Consider the face akb. (a) There are n + 1 terms in the resolution of akb. (b) Each term contains precisely one blue face, and no two terms use the same blue face. (c) The term that has a blue face inside the triangle ∆0 has only two more elements in its diagram, one red edge k → d1 and one blue edge k → b. Similarly, the unique term with a blue tripod in triangle ∆n has only two more edges in its diagram, the red edge k → dn, and the blue edge k → a. (d) Any term with its blue tripod inside some ∆i for i (cid:54)= 0, n has four more elements in its diagram; the two red edges k → di and k → di+1, and two blue edges k → a and k → b. Proof. Each claim follows easily from induction on the number of internal diagonals in the trian- gulation ∆. See Figure 11.24 below for an example of the four terms resulting from resolving the fan face in a hexagon equipped with a fan triangulation. Theorem 11.14. Consider the fan triangulation ∆. Suppose that ∆ has n internal diagonals. Let γ : a → b be one the two longest directed edges not in the initial triangulation, with associated cluster 141 variable xγ. Then the Laurent expansion of xγ in the initial cluster is xγ = xπ. (cid:88) π∈T ab Proof. We induct on the number of internal diagonals n in ∆. The base case is clearly true, so suppose n > 1. Resolve the arc γ over the (cid:27)rst edge it crosses. This results in four terms. We illustrate these terms for the longest edge in a hexagon below; the general case is similar. Figure 11.18: The (cid:27)rst step in the resolution of the longest edge in a hexagon + + + The (cid:27)rst term in Figure 11.19 is a T-path from a to b. By induction, any child of the last diagram shown is a T-path from a to b. Any child of either of the remaining terms can easily be seen to satisfy the de(cid:27)nition of edge- type T-path by using Lemma 11.13. Thus, any diagram obtained from resolving the arc γ is an edge-type T-path from a to b. Note that if ∆ has n internal diagonals, then there are (n + 1)2 terms in the resolution of γ. Indeed, by induction, Lemma 11.13, and Figure 11.19, we can deduce that the number of terms is 1 + n + n + n2 = (n + 1)2. Now the proof is complete, since any term obtained by resolving γ is a T-path, and there are (n + 1)2 T-paths from a to b. 142 11.8 Some Expansion Posets In this (cid:27)nal section, we describe the poset structure on the Laurent monomials in the expansion of the fan face, and for the “longest” edge, in a fan triangulation. De(cid:27)ne (cid:81) (cid:81) i→k xi k→j xj , ˆyk = valid for any k such that xk is a mutable initial cluster variable attached to a node of a 3- triangulation. By [15], these(cid:98)y-variables provide the covering relations in the poset we describe In our current context, there are two types of (cid:98)y-variables: “face-type” ˆy-variables, and “edge-type”(cid:98)y-variables (see the next (cid:27)gure). here. Figure 11.19: The two types of(cid:98)y-variables k k f ace type edge type The corresponding colored SL3 diagrams are shown directly below. 143 Figure 11.20: Covering relations f ace type edge type Consider the longest edge from a to b in a fan triangulation ∆. De(cid:27)nition 11.15. Consider the set Ta→b of all edge-type T-paths from a to b. The poset structure on Ta→b is de(cid:27)ned as follows. The minimal element of Ta→b coincides with the corresponding minimal element in the SL2 case, except its edges are directed. Similarly, the maximal element of Ta→b coincides with the corresponding maximal element in the SL2 case, except its edges are directed. We say that the T-path T is obtained from τ by an up-twist if xT = (cid:98)yxτ for some (cid:98)y-variable such that (1) No frozen variable appears in the denominator of the reduced fraction xT =(cid:98)yxτ, and (2) No frozen variable which appears in the numerator of xT =(cid:98)yxτ is squared. The T-path T covers τ if T is obtained from τ by performing a single up-twist. 144 We now describe the isomorphism class of each edge-type T-path. Consider the lattice path L in Z2 which starts at the origin and has associated word (ab2)n = ab2ab2 . . . . Figure 11.21: The lattice path abbabbabb . . . L = Let Lγ be the set of points in Z2 that are on or below L and weakly above the horizontal axis of Z2. Figure 11.22: The construction of Lγ L = Lγ = Make Lγ into (the Hasse diagram of) a poset by declaring a node (x2, y2) covers another (x1, y1) i(cid:29) either x2 = x1 + 1 or y2 = y1 + 1 (but not both). 145 Proposition 11.16. Let γ = a → b be the longest edge in a fan triangulation, and let xγ be the associated cluster variable. Then the poset Ta→b is isomorphic to Lγ. Proof. We induct on n. The claim is true for the base case by the resolution rule given in Figure 11.4, so suppose n > 1. Resolve the arc γ over the (cid:27)rst diagonal it crosses to obtain four diagrams (see Figure 11.19). One of these terms will consist of three directed edges that are contained within the triangu- lation; this is the minimal element. Call this minimal element M. Two diagrams in the resolution consist of (cid:27)ve terms (see the middle two terms shown in Fig- ure 11.19). Both of these diagrams consist of a cycle around the (cid:27)rst triangle, a red face inside the (cid:27)rst triangle, and a blue face not contained in the triangulation. The only di(cid:29)erence between these two diagrams is whether the initial 3-cycle around the (cid:27)rst triangle goes clockwise or coun- terclockwise. Call the term with the counterclockwise cycle F1, and call the other F2. As we have seen, each of these two diagrams expands into a chain poset with n terms. The terms from each of these posets are pairwise related by the face covering relation in the (cid:27)rst triangle. Moreover, one can check that the minimal term in F1 is connected to the minimal element M by the edge covering relation about the (cid:27)rst internal diagonal. Gluing together M and the elements from F1 and F2 gives a poset. Call this poset P1, and embed it into the discrete plane by sending M to (0, 0), and situating F1 and F2 in the (cid:27)rst quadrant, along the lines y = 0 and y = 1, respectively. The remaining diagram from the resolution of γ consists of three directed edges, two of which are elements in the triangulation (see the rightmost diagram in Figure 11.19). The remaining third element is the longest arc γ(cid:48) in a subfan of ∆ with n−1 diagonals. By induction, this poset, which we call P2, is isomorphic to Lγ(cid:48). One can check that each of the n elements along the bottom row of P2 is related to the corresponding element in F2 by an edge covering relation about the (cid:27)rst 146 diagonal that γ crosses. Thus, the posets P1 and P2 glue together to form Lγ. This completes the proof. Example 11.17. Figure 11.23 shows how the expansion poset of the longest edge in a pentagon is constructed via the gluing procedure given in the proof of the previous result. Figure 11.23: The gluing construction of the expansion poset of the longest edge in a pentagon The next result follows immediately from Lemma 11.13 and induction. Proposition 11.18. Consider the fan face γ. Then the poset of terms of the corresponding cluster variable xγ is isomorphic to a chain with n + 1 vertices. Example 11.19. Figure 11.24 shows the expansion poset of the fan face in a hexagon. The min- imal element is the leftmost element shown, and the maximal element is the rightmost element shown. 147 Figure 11.24: Expansion poset of a fan face Remark 11.20. There is a bijection between the terms in the expansion poset of a fan face, and the terms in the “SL2” T-path poset obtained from expanding the longest (undirected) edge in the same triangulation. Namely, given a term in the fan face poset, deleting the unique blue face and replacing it with the unique blue boundary edge boarding the deleted face, which is not adjacent to the fan vertex, gives the bijection. An example of this is indicated below. Figure 11.25: The bijection between a fan face poset and the corresponding SL2 T-path poset SL3 SL2 148 REFERENCES 149 REFERENCES [1] Rachel Bailey and Emily Gunawan. Cluster algebras and binary words. [2] Garrett Birkho(cid:29) et al. Rings of sets. Duke Mathematical Journal, 3(3):443–454, 1937. [3] Petter Brändén. Unimodality, log-concavity, real-rootedness and beyond. Handbook of enu- merative combinatorics, 87:437, 2015. [4] Francesco Brenti. Log-concave and unimodal sequences in algebra, combinatorics, and ge- ometry: an update, jerusalem combinatorics’ 93, 71–89. Contemp. Math, 178. [5] İlke Çanakçı and Ralf Schi(cid:31)er. Cluster algebras and continued fractions. Compositio math- ematica, 154(3):565–593, 2018. [6] İlke Çanakçı and Ralf Schi(cid:31)er. Snake graphs and continued fractions. European Journal of Combinatorics, 86:103081, 2020. [7] Zhiyun Cheng, Sujoy Mukherjee, Jozef H Przytycki, Xiao Wang, and Seung Yeop Yang. Strict unimodality of q-polynomials of rooted trees. arXiv preprint arXiv:1601.03465, 2016. [8] Anna Felikson, Michael Shapiro, and Pavel Tumarkin. Cluster algebras and triangulated orbifolds. Advances in Mathematics, 231(5):2953–3002, 2012. [9] Vladimir Fock and Alexander Goncharov. Moduli spaces of local systems and higher teich- müller theory. Publications Mathématiques de l’IHÉS, 103:1–211, 2006. [10] Sergey Fomin and Pavlo Pylyavskyy. Tensor diagrams and cluster algebras. arXiv preprint arXiv:1210.1888, 2012. [11] Sergey Fomin and Pavlo Pylyavskyy. Webs on surfaces, rings of invariants, and clusters. Proceedings of the National Academy of Sciences, 111(27):9680–9687, 2014. [12] Sergey Fomin, Michael Shapiro, and Dylan Thurston. Cluster algebras and triangulated surfaces. part i: Cluster complexes. arXiv preprint math/0608367, 2006. [13] Sergey Fomin and Dylan Thurston. Cluster algebras and triangulated surfaces part II: Lambda lengths, volume 255. American Mathematical Society, 2018. [14] Sergey Fomin and Andrei Zelevinsky. Cluster algebras i: foundations. Journal of the Amer- ican Mathematical Society, 15(2):497–529, 2002. [15] Sergey Fomin and Andrei Zelevinsky. Cluster algebras iv: coe(cid:28)cients. Compositio Mathe- matica, 143(1):112–164, 2007. 150 [16] Rob Gaebler. Alexander polynomials of two-bridge knots and links. Undergraduate Thesis, 2004. [17] Emden R Gansner. On the lattice of order ideals of an up-down poset. Discrete Mathematics, 39(2):113–122, 1982. [18] Michael Gekhtman, Michael Shapiro, Alek Vainshtein, et al. Cluster algebras and weil- petersson forms. Duke Mathematical Journal, 127(2):291–311, 2005. [19] Michael Gekhtman, Michael Zalmanovich Shapiro, and Alek D Vainshtein. Cluster algebras and poisson geometry. Moscow Mathematical Journal, 3(3):899–934, 2003. [20] Emily Gunawan. Combinatorics of cluster algebras from surfaces. 2016. [21] Emily Gunawan, Gregg Musiker, and Hannah Vogel. Cluster algebraic interpretation of in(cid:27)nite friezes. European Journal of Combinatorics, 81:22–57, 2019. [22] H Höft and M Höft. A (cid:27)bonacci sequence of distributive lattices. Fibonacci Quart, 23(3):232– 237, 1985. [23] W-J Hsu. Fibonacci cubes-a new interconnection topology. and Distributed Systems, 4(1):3–12, 1993. IEEE Transactions on Parallel [24] Sandi Klavžar. Structure of (cid:27)bonacci cubes: a survey. Journal of Combinatorial Optimization, 25(4):505–522, 2013. [25] Kolja Knauer, Leonardo Martínez-Sandoval, and Jorge Luis Ramírez Alfonsín. On lattice path matroid polytopes: integer points and ehrhart polynomial. Discrete & Computational Geometry, 60(3):698–719, 2018. [26] Kyungyong Lee and Ralf Schi(cid:31)er. Cluster algebras and jones polynomials. Selecta Mathe- matica, 25(4):58, 2019. [27] Sophie Morier-Genoud and Valentin Ovsienko. q-deformed rationals and q-continued frac- tions. arXiv preprint arXiv:1812.00170, 2018. [28] Emanuele Munarini and Norma Zagaglia Salvi. On the rank polynomial of the lattice of order ideals of fences and crowns. Discrete mathematics, 259(1-3):163–177, 2002. [29] Gregg Musiker and Ralf Schi(cid:31)er. Cluster expansion formulas and perfect matchings. Journal of Algebraic Combinatorics, 32(2):187–209, 2010. [30] Gregg Musiker, Ralf Schi(cid:31)er, and Lauren Williams. Positivity for cluster algebras from surfaces. Advances in Mathematics, 227(6):2241–2308, 2011. 151 [31] Gregg Musiker, Ralf Schi(cid:31)er, and Lauren Williams. Bases for cluster algebras from surfaces. Compositio Mathematica, 149(2):217–263, 2013. [32] Kathleen M O’Hara. Unimodality of gaussian coe(cid:28)cients: a constructive proof. Journal of Combinatorial Theory, Series A, 53(1):29–52, 1990. [33] James Propp. The combinatorics of frieze patterns and marko(cid:29) numbers. arXiv preprint math/0511633, 2005. [34] Michelle Rabideau and Ralf Schi(cid:31)er. Continued fractions and orderings on the markov numbers. arXiv preprint arXiv:1801.07155, 2018. [35] Bruce E Sagan. The symmetric group: representations, combinatorial algorithms, and symmet- ric functions, volume 203. Springer Science & Business Media, 2013. [36] Ralf Schi(cid:31)er. A cluster expansion formula (a_n case). the electronic journal of combinatorics, 15(1):R64, 2008. [37] Ralf Schi(cid:31)er. On cluster algebras arising from unpunctured surfaces ii. Advances in Math- ematics, 223(6):1885–1923, 2010. [38] Ralf Schi(cid:31)er and Hugh Thomas. On cluster algebras arising from unpunctured surfaces. International Mathematics Research Notices, 2009(17):3160–3189, 2009. [39] Richard P Stanley. Di(cid:29)erential posets. 1(4):919–961, 1988. Journal of the American Mathematical Society, [40] Richard P Stanley. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Ann. New York Acad. Sci, 576(1):500–535, 1989. [41] A Muhammed Uludağ and Hakan Ayral. Jimm, a fundamental involution. arXiv preprint arXiv:1501.03787, 2015. [42] Toshiya Yurikusa. Combinatorial cluster expansion formulas from triangulated surfaces. arXiv preprint arXiv:1808.01567, 2018. [43] Toshiya Yurikusa. Cluster expansion formulas in type a. Algebras and Representation Theory, 22(1):1–19, 2019. 152