Combinatorics seminar
Combinatorics Seminar - Fall 2013
Thursday, 3:30pm-4:30pm
Room 226, Goldsmith building
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.
-
Thursday October 3
Speaker: Olivier Bernardi (Brandeis)
Title: Counting trees using symmetries.
Abstract: I will present counting results for trees. I will start with the famous Cayley formula for trees: there are n^{n-2} trees with vertex set {1,2,...,n}. I will then discuss a generalization found in a joint work with Alejandro Morales. This generalization extends earlier results by Knuth and by Bousquet-Melou and Chapuy, and has application to the multivariate Lagrange inversion formula and to the study of the profile of random trees.
Our proof takes advantage of certain symmetries of the enumerative formulas: we first prove these symmetries by simple combinatorial arguments, and then deduce the general formulas from particular cases.
-
Thursday October 10
Speaker: Ira Gessel (Brandeis)
Title: Counting unlabeled trees.
Abstract: Last week, Olivier talked about counting labeled trees. I will talk about counting unlabeled trees, which are isomorphism classes of labeled trees. This talk will also be an introduction to the use of generating functions in enumeration.
-
Thursday October 24
Speaker: Jordan Tirrel (Brandeis)
Title: Counting Binary Trees and Hyperplane Arrangements.
Abstract:
Binary trees and regions of the Catalan hyperplane arrangement are among many objects counted by the Catalan numbers. When we count labelled binary trees by their number of left/right ascents/descents, we obtain a more general generating function which can be used to count certain subsets of binary trees. These numbers turn out to correspond to the numbers of regions of certain subarrangements of the Catalan arrangement. We will discuss the open problem of finding a bijective explanation for these correspondences.
-
Thursday October 31
Speaker: Kassie Archer (Dartmouth College)
Title: Descents in unimodal cyclic permutations.
Abstract: A unimodal permutation is one that is increasing, then decreasing. A descent occurs in a permutation when two consecutive values are in decreasing order. An interesting fact: the number of unimodal cyclic permutations with an even number of descents minus the number of those with an odd number of descents is the Mobius function at n, which depends only on the prime factorization of n! We'll see a proof of this fact and talk about why a generalization of this fact is useful in representation theory.
-
Thursday November 7
Speaker: Jair Taylor (University of Washington)
Title: Combinatorial Laguerre series.
Abstract: The Laguerre polynomials are a classical sequence of orthogonal polynomials that have a number of applications in enumerative combinatorics. In this talk I will describe the "Laguerre series" of a set of tuples of words, which is a formal sum of weighted generalized Laguerre polynomials with parameter α=−1. The product of Laguerre series has a useful combinatorial interpretation, and Laguerre series can be computed by finding an appropriate ordinary generating function and applying a certain transformation which is related to the Laplace transform. This gives a technique which allows us to count words subject to various restrictions.
-
Thursday November 21
Speaker: Nan Li (MIT)
Title:Polytopes and two counting problems.
Abstract:In this talk, I will start with a short introduction to polytopes, and explain a connection with linear programming and speech recognition. Then I talk about two counting problems for integer polytopes, which bring up the studies of f-vector and h-vector respectively.