The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.

• January 31

  Speaker: Kate Moore (Dartmouth)
  Title: Patterns in Dynamical Systems
  Abstract: Given a map f: [0, 1] -> [0, 1], we may consider finite sequences of iterates x, f(x), f(f(x)),..., f^{n-1}(x). If these n values are different, we associate a permutation \pi \in S_n to this sequence by replacing the smallest value with a 1, the second smallest with a 2, and so on. If \pi arises in this way, we say that \pi is an allowed pattern of f. It is known that if f is a piecewise monotone map, then there are permutations that are never realized by f. This surprising observation gives rise an important tool for distinguishing random from deterministic time series and for estimating the complexity of a time series.
  In general, determining the allowed patterns of a given family of maps is a difficult problem and the question has only been answered in a few specific cases. Building on work by Archer and Elizalde, I will present a method to determine the allowed patterns signed-shifts, negative shifts and negative beta-shifts.
  
  
  
  

• February 7

  Speaker: Yan Zhuang (Brandeis)
  Title: Shuffle-Compatible Permutation Statistics
  Abstract: We introduce the notion of a shuffle-compatible permutation statistic and the shuffle algebra associated to a shuffle-compatible statistic. We give a necessary and sufficient condition for the shuffle-compatibility of a descent statistic, which shows that the shuffle algebra of any shuffle-compatible descent statistic is isomorphic to a quotient of the algebra of quasisymmetric functions QSym. We also give a dual version of this condition which is obtained by exploiting the duality between QSym and the coalgebra of noncommutative symmetric functions Sym. These results are used to prove the shuffle-compatibility of several well-known descent statistics and to characterize their shuffle algebras. (Joint work with Ira Gessel.)
  
  
  
  

• February 14

  Speaker: Yan Zhuang (Brandeis)
  Title: Eulerian Polynomials and Descent Statistics
  Abstract: We present several new identities expressing polynomials counting permutations by various descent statistics in terms of Eulerian polynomials as well as refinements of type B Eulerian polynomials and flag descent polynomials, extending results of Stembridge and Petersen. We also give q-exponential generating functions for q-analogues of these descent statistic polynomials that also keep track of the inversion number or inverse major index. These results are proven by a general method involving noncommutative symmetric functions. Time permitting, we present a generalization of our result for the joint distribution of the peak number and descent number, which is proven using the modified Foata-Strehl action and extends a result of Brändén. 
  
  
  
  

• February 28

  Speaker: Mark Kempton (Harvard)
  Title: Quantum state transfer on graphs
  Abstract: A quantum walk on a graph G describes the evolution of the quantum state of a particle on the graph, and is described by a discrete version of the Schrodinger equation involving a graph Hamiltonian on G. If u and v are two vertices of a graph, then we say that there is perfect state transfer from u to v if there is some time at which a particle starting at vertex u ends up at vertex v. Considerable research has been done in recent years on perfect state transfer in graphs, particularly in the case where the graph Hamiltonian is take to be the adjacency matrix. In addition, one can include an energy potential on the vertex set, which amounts to adding a diagonal matrix to the Hamiltonian. I will present results showing how the potential can affect whether or not a graph admits perfect state transfer. In particular, for paths of length greater than 4, there is no potential that can be chosen for which the path admits perfects state transfer. However, there are infinite families of a graphs where a potential does induce perfect state transfer on the graph.
  
  
  
  

• March 7

  Speaker: Olivier Bernardi (Brandeis)
  Title: Counting lattice walks in the quarter plane
  Abstract: We consider lattice walks in the quarter plane N^2, with a fixed set of steps S. Depending on the set of steps S the enumerative properties of the class of walks can vary widely. In the past decade, various sophisticated methods have been used to derive these enumerative properties, and this has led to a rich collection of attractive results dealing with the nature (algebraic, D-finite, differentially-algebraic,...) of the associated generating function, depending on S.
  We consider a new method inspired by Tutte's work on the counting of colored triangulations. This method brings us closer to a complete classification of the enumerative properties of these walks, and a more uniform treatment of all the cases where S is contained in {-1, 0,1}^2. In particular, the infamous Gessel model, can be solved quite readily by this method.
  This is joint work with Mireille Bousquet-Melou and Kilian Raschel.
  
  
  
  

• March 14

  Speaker: Jordan Tirell (Mount Holyoke College)
  Title: From Dyck paths to standard Young tableaux
  Abstract: In what ways can we add extra structure or restrictions to Dyck paths and standard Young tableaux to yield equinumerous sets? Perhaps the most famous answer is the bijection between Dyck paths of semilength n and standard Young tableaux of shape (n,n). In this talk we will present two newer answers. In particular, we will attach a connected matching to each ascent in our Dyck paths and give a bijection from these structures to all standard Young tableaux. Also, we will give a bijection between Dyck paths without singleton ascents and standard Young tableaux of flag shape.
  
  
  
  

• March 21

  Speaker: Everett Sullivan (Dartmouth)
  Title: Linear chord diagrams with long chords
  Abstract: A linear chord diagram of size n is a partition of first 2n integers into sets of size two. Geometrically, we consider it as a choice of parings of 2n ordered points. Linear chord diagrams have shown up in permutation patterns, knot theory, and full rook placements on Ferrers boards. The length of a chord is the difference between its start and end point.
  We explore a restriction on the set of linear chord diagrams by requiring each chord to have a minimum length k. After constructing a table of counting the number of linear chord diagrams of degree n such that every chord has length at least k, we observe that if we proceed far enough along the diagonals, that they are given by a geometric sequence. We prove that this holds for all diagonals, as well as when the effect starts.
  
  
  
  

• March 28

  Speaker: Pavel Galashin (MIT)
  Title: Zamolodchikov periodicity and integrability
  Abstract: The $T$-system is a certain discrete dynamical system associated with a quiver. Keller showed in 2013 that the $T$-system is periodic when the quiver is a product of two finite Dynkin diagrams. We prove that the $T$-system is periodic if and only if the quiver is a finite $\boxtimes$ finite quiver. Such quivers have been classified by Stembridge in the context of Kazhdan-Lusztig theory. We show that if the $T$-system is linearizable then the quiver is necessarily an affine $\boxtimes$ finite quiver. We classify such quivers and conjecture that the $T$-system is linearizable for each of them. Next, we show that if the $T$-system has algebraic entropy zero then the quiver is an affine $\boxtimes$ affine quiver, and classify them as well. For the octahedron and the cube recurrence, we prove the converse direction of each of the three statements using explicit formulas due to Speyer and Carroll combined with our general linearizability result for cylindrical networks.
  
  
  
  

• April 4

  Speaker: Ira Gessel (Brandeis)
  Title: An introduction to umbral calculus
  Abstract: The classical umbral calculus (also called Blissard’s symbolic method) involves replacing exponents with subscripts. In this talk I will explain how this makes sense and why it is useful, with examples involving derangement numbers, Hermite polynomials, Bernoulli numbers, and Bell numbers. No knowledge of combinatorics (or anything else) is needed to understand this talk.
  
  
  
  

• April 25

  Speaker: Cristobal Lemus (Brandeis)
  Title: Enumeration of paths via occurrences of distinguished strings and a proof of Touchard’s identity.
  Abstract: We will count paths by occurrences of several strings of steps in Dyck paths. There is an extensive literature on lattice path enumeration where authors count the occurrence of a particular string in Dyck paths, sometimes also keeping track of whether such a string occurs at even or odd height. This has been done, for example, by Deutsch in “Dyck path enumeration, Discrete Math. 204 (1999), no. 1-3, 167–202.” There “peaks”, “valleys”, and “doublerises” are studied and as a result give Narayana numbers. Strings of length 3 are also considered by Deutsch. The authors of “A. Sapounakis, I. Tasoulas, and P. Tsikouras, Counting strings in Dyck paths, Discrete Mathematics 307 (2007), no. 23, 2909–2924.” count paths by occurrences of any given string of length 4 and by semilength. In this talk we count three types of substrings simultaneously which together also count paths by semilength and number of peaks. Special cases of this enumeration give several well-known families of numbers such as Catalan, Motzkin, Narayana, and Schröder numbers.
  We will also give a short proof of Touchard’s identity via colored Motzkin paths.