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

• Tuesday February 24

  Speaker: Jordan Tirrell
  Title: Counting flawed Motzkin paths by Motzkin paths
  Abstract: We'll look at paths which start and end at zero and take up, down and flat steps. These are called Motzkin paths if they contain no flaws, or steps below zero. Otherwise we call them flawed Motzkin paths. Eu, Liu, and Yeh showed in 2002 that the number of flawed Motzkin paths with a fixed number of flaws can be enumerated as an alternating linear combination of Motzkin numbers. We give a combinatorial interpretation of this result.
  
  

• Tuesday March 3

  Speaker: Olivier Bernardi
  Title: Regions in hyperplane arrangements and trees
  Abstract: A hyperplane arrangement (of dimension n) is a collection of hyperplanes (in R^n). The hyperplanes cut the space R^n in a certain number of regions (the connected components of the complement of the hyperplanes). Given a finite set S of integers, we consider the hyperplane arrangement A(S,n) in R^n with hyperplanes x_i-x_j=s for all i< j and all s in S. For instance, for S={0} the hyperplanes are x_i=x_j for all i,j, and the number of regions is n!. It has been noticed (in particular by Ira Gessel) that for many sets S, the number of regions of A(S,n) is equal to the number of labeled trees in a certain family. I will try to explain why it is the case.
  
  

• Tuesday March 10

  Speaker: Jordan Awan
  Title: Matroid Representability
  Abstract: A matroid is a finite structure which aims to capture the similarities between linear independence in matrices and properties of subforests in graphs. An F-representable matroid M is a matroid for which there exists a matrix over the field F which has the same dependencies as M. We will discuss the problem of determining the representability of matroids over different fields.
  
  

• Tuesday March 17

  Speaker: Ira Gessel
  Title: The Malvenuto-Reutenauer algebra and permutation enumeration
  Abstract: The Malvenuto-Reutenauer algebra is an algebra spanned by permutations of {1, 2, …, n} for all n in which multiplication is a “shifted shuffle”. This operation arises very naturally when working with exponential generating functions. Quotients of the Malvenuto-Reutenauer give rise to various kinds of generating functions, including exponential, Eulerian, and quasi-symmetric, and are particularly useful in studying the enumeration of permutations by descents and peaks.
  
  

• Tuesday March 24

  Speaker: Yan Zhuang
  Title: Permutations with Parity Restrictions on Valleys and Peaks
  Abstract: Gessel and Zhuang (2014) found the exponential generating function for permutations with all valleys even and all peaks odd, which also counts permutations with all valleys odd and all peaks even. In this talk, we will present the exponential generating functions for permutations with all valleys and peaks even, and for permutations with all valleys and peaks odd. These generating functions are obtained by way of what we call "monoid networks", which allow us to count words in a free monoid corresponding to walks in weighted digraphs.
  
  

• Tuesday March 31

  Speaker: Jiaqi Gu
  Title: Algorithms for generating permutations and sorting permutations
  Abstract: We will look at two methods to generate all n-permutations with some restrictions. The motivation comes from how to write a program to test a conjecture concerning permutations. Then we will introduce how to sort permutations with stacks and enumerate how many of n-permutations are n-stack sortable and the condition that a permutation needs to satisfy to be n-stack sortable.