Combinatorics seminar

## Combinatorics Seminar - Spring 2015

### Tuesday 12.45pm-1.45pm in room 226.

• #### 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.

Previous semesters: Fall 2014, Spring 2014, Fall 2013.