In this paper, we utilize the machinery of cluster algebras, quiver mutations, and brane tilings to study a variety of historical enumerative combinatorics questions all under one roof. Previous work by the second author and REU students [Zha, LMNT14], and more recently of both authors [LM17], analyzed the cluster algebra associated to the cone over dP3, the del Pezzo surface of degree 6 (CP^2 blown up at three points). By investigating sequences of toric mutations, those occurring only at vertices with two incoming and two outgoing arrows, in this cluster algebra, we obtained a family of cluster variables that could be parameterized by Z^3 and whose Laurent expansions had elegant combinatorial interpretations in terms of dimer partition functions (in most cases). While the earlier work [Zha, LMNT14, LM17] focused exclusively on one possible initial seed for this cluster algebra, there are in total four relevant initial seeds (up to graph isomorphism). In the current work, we explore the combinatorics of the Laurent expansions from these other initial seeds and how this allows us to relate enumerations of perfect matchings on Dungeons to Dragons.
Birational rowmotion is an action on the space of assignments of rational functions to the elements of a finite partially-ordered set (poset). It is lifted from the well-studied rowmotion map on order ideals (equivariantly on antichains) of a poset P [AST11, BW74, CF95, Pan09, PR13, RuSh12,RuWa15+,SW12, ThWi17, Yil17], which when iterated on special posets, has unexpectedly nice properties in terms of periodicity, cyclic sieving, and homomesy (statistics whose averages over each orbit are constant) [PR13]. In this context, rowmotion appears to be related to Auslander-Reiten translation on certain quivers [Yil17], and birational rowmotion to Y-systems of type Am×An described in Zamolodchikov periodicity. We give a formula in terms of families of non-intersecting lattice paths for iterated actions of the birational rowmotion map on a product of two chains. This allows us to give a much simpler direct proof of the key fact that the period of this map on a product of chains of lengths r and s is r+s+2 (first proved by D. Grinberg and the second author [GrRo15]), as well as the first proof of the birational analogue of homomesy along files for such posets.
We present a unified mathematical framework that elegantly describes minimally SUSY gauge theories in even dimension, ranging from 6d to 0d, and their dualities. This approach combines recent developments on graded quiver with potentials, higher Ginzburg algebras and higher cluster categories (also known as m-cluster categories). Quiver mutations studied in the context of mathematics precisely correspond to the order (m+1) dualities of the gauge theories. Our work suggests that these equivalences of quiver gauge theories sit inside an infinite family of such generalized dualities, whose physical interpretation is yet to be understood.
Counting Arithmetical Structures on Paths and Cycles
Let G be a finite, simple, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)-A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices (diag(d)-A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients (2n-1,n-1), and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.
Originally studied by Conway and Coxeter, friezes appeared in various recreational
mathematics publications in the 1970s. More recently, in 2015, Baur, Parsons, and Tschabold
constructed periodic in nite friezes and related them to matching numbers in the once-punctured
disk and annulus. In this paper, we study such infinite friezes with an eye towards cluster algebras
of type D and affine A, respectively. By examining infinite friezes with Laurent polynomials entries,
we discover new symmetries and formulas relating the entries of this frieze to one another. Lastly,
we also present a correspondence between Broline, Crowe and Isaacs's classical matching tuples and
combinatorial interpretations of elements of cluster algebras from surfaces.
Given a super-symmetric quiver gauge theory, string theorists can as-
sociate a corresponding toric variety (which is a cone over a Calabi-Yau 3-fold) as
well as an associated combinatorial model known as a brane tiling. In combinatorial
language, a brane tiling is a bipartite graph on a torus and its perfect matchings
are of interest to both combinatorialists and physicists alike.
A cluster algebra may also be associated to such quivers and in this paper we study the generators of this
algebra, known as cluster variables, for the quiver associated to the cone over the
del Pezzo surface dP3. In particular, mutation sequences involving mutations exclu-
sively at vertices with two in-coming arrows and two out-going arrows are referred
to as toric cascades in the string theory literature. Such toric cascades give rise to
interesting discrete integrable systems on the level of cluster variable dynamics. We
provide an explicit algebraic formula for all cluster variables which are reachable by
toric cascades as well as a combinatorial interpretation involving perfect matchings
of subgraphs of the dP3 brane tiling for these formulas in most cases.
We prove the equality of two canonical bases of a rank 2 cluster algebra, the greedy
basis of Lee-Li-Zelevinsky and the theta basis of Gross-Hacking-Keel-Kontsevich.
We extend a T-path expansion formula for arcs of a once-punctured polygon and use this formula
to give a combinatorial proof that cluster monomials form the atomic basis of a cluster algebra coming from a
triangulated once-punctured polygon (type D).
Bipartite, periodic, planar graphs known as brane tilings can be associated to a large class of quivers. This paper will explore new algebraic properties of the well-studied del Pezzo 3 quiver and geometric properties of its corresponding brane tiling. In particular, a factorization formula for the cluster variables arising from a large class of mutation sequences (called tau-mutation sequences) is proven; this factorization also gives a recursion on the cluster variables produced by such sequences. We can realize these sequences as walks in a triangular lattice using a correspondence between the generators of the affine symmetric group A2 and the mutations which generate tau-mutation sequences. Using this bijection, we obtain explicit formulae for the cluster that corresponds to a specific alcove in the lattice. With this lattice visualization in mind, we then express each cluster variable produced in a tau-mutation sequence as the sum of weighted perfect matchings of a new family of subgraphs of the dP3 brane tiling, which we call Aztec castles. Our main result generalizes previous work on a certain mutation sequence on the dP3 quiver in [Zha12], and forms part of the emerging story in combinatorics and theoretical high energy physics relating cluster variables to subgraphs of the associated brane tiling.
Given a framed quiver, i.e. one with a frozen vertex associated to each
mutable vertex, there is a concept of green mutation, as introduced by Keller.
Maximal sequences of such mutations, known as maximal green sequences, are
important in representation theory and physics as they have numerous
applications, including the computations of spectrums of BPS states,
Donaldson-Thomas invariants, tilting of hearts in the derived category, and
quantum dilogarithm identities. In this paper, we study such sequences and
construct a maximal green sequence for every quiver mutation-equivalent to an
orientation of a type A Dynkin diagram.
We study variants of Gale-Robinson sequences, as motivated by cluster algebras with principal coefficients. For such cases, we give combinatorial interpretations of cluster variables using brane tilings, as from the physics literature. Presented at FPSAC (Formal Power Series and Algebraic Combinatorics) 2013, and the extended abstract appeared in the conference proceedings.
We elaborate upon a bijection discovered by Cools, Draisma, Payne, and Robeva between the set of rectangular standard Young tableaux and the set of equivalence classes of chip configurations on certain metric graphs under the relation of linear equivalence. We present an explicit formula for computing the v_0-reduced divisors (representatives of the equivalence classes) associated to given tableaux, and use this formula to prove (i) evacuation of tableaux corresponds (under the bijection) to reflecting the metric graph, and (ii) conjugation of the tableaux corresponds to taking the Riemann-Roch dual of the divisor.
Because of the conjectural connection between cluster algebras and dual canonical bases, it is natural to ask whether one may construct a "good" (vector-space) basis of each cluster algebra. In this paper we construct two bases for each cluster algebra coming from a triangulated surface without punctures. We work in the context of a coefficient system coming from a full-rank exchange matrix, for example, principal coefficients. The elements of our bases have positive Laurent expansions with respect to every cluster.
This paper concerns cluster algebras with principal coefficients A(S,M) associated to bordered surfaces (S,M), and is a companion to a concurrent work of the authors with Schiffler [MSW2].
Given any (generalized) arc or loop in the surface -- with or without self-intersections -- we associate an element of (the fraction field of) A(S,M), using products of elements of PSL_2(R).
We give a direct proof that our matrix formulas for arcs and loops agree with the combinatorial formulas for arcs and loops in terms of matchings, which were given in [MSW, MSW2].
Finally, we use our matrix formulas to prove skein relations for the cluster algebra elements associated to arcs and loops.
Our matrix formulas and skein relations generalize prior work of Fock and Goncharov [FG1, FG2, FG3], who worked in the coefficient-free case.
The results of this paper will be used in [MSW2] in order to show that certain collections of arcs and loops comprise a vector-space basis for A(S,M).
This is the compendium of the cluster algebra and quiver package for
sage. The purpose of this package is to provide a platform to work
with cluster algebras in graduate courses and to further develop the
theory by working on examples, by gathering data, and by exhibiting
and testing conjectures. In this compendium, we include the relevant
theory to introduce the reader to cluster algebras assuming no prior
background; this exposition has been written to be accessible to an
interested undergraduate. Throughout this compendium, we include
examples that the user can run in the sage notebook or command line,
and then close with a detailed description of the data structures and
methods in this package.
The cyclotomic polynomial is defined to be the minimal polynial
over the rationals for any complex nth root of unity. Although
well-studied, its coefficients are mysterious. We discuss a topological
interpretations of these coefficients in terms of simplicial homology. This
work utilizes oriented matroids and simplicial spanning trees.
In this paper, we study various tropical analogues of objects from algebraic geometry. In particular, a tropical curve is a metric graph with possibly unbounded edges, and tropical rational functions are continuous piecewise linear functions with integer slopes. The complete linear system |D| of a divisor D on a tropical curve analogously to the classical counterpart. We investigate the structure of |D| as a cell complex and show that linear systems are quotients of tropical modules, finitely generated by vertices of the cell complex. Using a finite set of generators, |D| defines a map from the tropical curve to a tropical projective space, and the image can be extended to a parameterized tropical curve of degree equal to deg(D). The tropical convex hull of the image realizes the linear system |D| as an embedded polyhedral complex. We also show that curves for which the canonical divisor is not very ample are hyperelliptic. Also, we show that the Picard group of a rational tropical curve is a direct limit of critical groups of finite graphs converging to the curve.
We give combinatorial formulas for the Laurent expansion of any cluster variable in any cluster algebra coming from a triangulated surface (with or without punctures), with respect to an arbitrary seed. Moreover, we work in the generality of principal coefficients. An immediate corollary of our formulas is a proof of the positivity conjecture of Fomin and Zelevinsky for cluster algebras from surfaces, in geometric type.
We study cluster algebras with principal coefficient systems that are associated to unpunctured surfaces. We give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings a certain graph that is constructed from the surface by recursive glueing of elementary pieces that we call tiles. We also give a second formula for these Laruent polynomial expansions in terms of subgraphs of the constructed graph.
Let q be a power of a prime, and E be an elliptic curve defined over F_q. Such curves have a classical group structure, and one can form an infinite tower of groups by considering E over field extensions F_q^k for all k greater than or equal to 1. The critical group of a graph may be defined as the cokernel of L(G), the Laplacian matrix of G. In this paper, we compare elliptic curve groups with the critical groups of a certain family of graphs. This collection of critical groups also decomposes into towers of subgroups, and we highlight additional comparisons by using the Frobenius map of E over F_q.
(with Benjamin Braun, Hugo Corrales, Scott Corry, Luis David Garcia Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, and Carlos E. Valencia)
This work lies across lies across three areas of investigation that are by themselves of independent interest. A problem that arose in quantum computing led us to a link that tied the three above areas together. This link consists of a single formal power series with a multifaced interpretation. The deeper exploration of this link yielded results as well as methods for solving some numerical problems including the computation of certain Kronecker coefficients and enumeration of solutions to a Diophantine system corresponding to the hyperoctahedral group.
In this paper, we give a graph theoretic combinatorial interpretation for the cluster variables in most cluster algebras of finite type with a bipartite seed. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings encodes the numerator of the associated Laurent polynomial while decompositions of the graphs correspond to the denominator. This complements recent work by Schiffler and Carroll-Price for a cluster expansion formula for the A_n case, while providing a novel interpretation for the B_n, C_n, and D_n cases.
In 2002, Feigin and Veselov defined the space of m-quasiinvariants for any Coxeter group, building on earlier work of Chalykh and Veselov. Many properties of these spaces were proven in subsequent papers from this definition, however, an explicit computation of a basis was only done in the cases of dihedral groups and the symmetric group S_3. Felder and Veslov also computed the non-symmetric m-quasiinvariants of lowest degree for general S_n. In this paper, we provide a new characterization of the m-quasiinvariants of S_n, and use this to provide a basis for the isotypic component indexed by the partition [n-1,1]. This builds on a previous paper by the authors, in which we computed a basis for S_3 via combinatorial methods.
My Ph.D. Thesis is mostly a combination of the published papers ''Combinatorial aspects of elliptic curves'' and ''The critical groups of a family of graphs and elliptic curves over finite fields''.
Chapter 6 also contains the following; Additionally, the theory of critical groups allows us to re-interpret the group elements as the set of admissible words for a
primitive circuit in a specific deterministic finite automaton. As an application, we will then compare the zeta function of an elliptic curve and the zeta function of the corresponding cyclic
Given an elliptic curve C, we study here N_k = #C(F_q^k), the number of points of C over the finite field F_q^k. This sequence of numbers, as k runs over positive integers, has numerous remarkable properties of a combinatorial flavor in addition to the usual number theoretical interpretations. In particular, we prove that N_k = -W_k(q,-N_1), where W_k(q,t) is a (q,t)-analogue of the number of spanning trees of the wheel graph. Additionally we develop a determinantal formula for Nk, where the eigenvalues can be explicitly written in terms of q, N_1, and roots of unity. We also discuss here a new sequence of bivariate polynomials related to the factorization of N_k, which we refer to as elliptic cyclotomic polynomials because of their various properties.
Fomin and Zelevinsky show that a certain two-parameter family of
rational recurrence relations, here called the (b,c) family,
possesses the Laurentness property: for all b,c, each term of the
(b,c) sequence can be expressed as a Laurent polynomial in the two
initial terms. In the case where the positive integers b,c satisfy
bc<4, the recurrence is related to the root systems of
finite-dimensional rank 2 Lie algebras; when bc>4, the recurrence
is related to Kac-Moody rank 2 Lie algebras of general type. Here
we investigate the borderline cases bc=4, corresponding to Kac-Moody
Lie algebras of affine type. In these cases, we show that the Laurent
polynomials arising from the recurence can be viewed as generating
functions that enumerate the perfect matchings of certain graphs. By
providing combinatorial interpretations of the individual coefficients of these Laurent polynomials, we establish their positivity.
Let s_ij represent a transposition in S_n. A polynomial P in Q[x_1, x_2, ..., x_n] is said to be m-quasiinvariant with respect to S_n if (x_i - x_j)^(2m+1) divides (1 - s_ij)P for all i and j inclusively between
1 and n. We describe a method for constructing a basis for the quotient of the m-quasiinvariants of S_3 by the ring of symmetric functions in 3 variables. This leads to the evaluation of certain binomial determinants that are interesting in their own right.
In this thesis, we will investigate the theory of cluster algebras, a recently created combinatorial theory
that is still developing. Cluster algebras are not only intrinsically interesting, but have useful applications to
the theory of Somos sequences and Laurent polynomials, generalized associahedra and many other fields. We will
concentrate on an axiomatic development of cluster algebras, motivating them by their aforementioned
applications. We will end with several open problems and conjectures. This exposition will utilize semisimple
Lie algebras and root systems; however, the necessary results from these mathematical areas will be
presented here and developed as needed. This should be accessible to anyone familiar with graph theory and