Combinatorics Seminar - Fall 2014
Room 209, Goldsmith building
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.
Tuesday September 30
Speaker: Yan Zhuang (Brandeis)
Title: Counting Permutations by Alternating Descents
Abstract: We find the exponential generating function for permutations with all valleys even and all peaks odd, and use it to determine the asymptotics for its coefficients, answering a question posed by Liviu Nicolaescu. We give two proofs for the generating function. The first proof uses a system of differential equations whose solution gives the generating function. For the second proof, we develop a new method for counting permutations by alternating descents using noncommutative symmetric functions. This is joint work with Ira Gessel.
Tuesday October 7
Speaker: Ira Gessel (Brandeis)
Title: Exponential generating functions modulo p
The exponential generating function for a sequence a_n is the formal power series in which the coefficient of x^n/n! is a_n. Exponential generating functions are useful in counting "labeled objects" such as permutations, partitions, and graphs. We would like to find congruences to prime moduli for these sequences; for example, the Bell numbers and the tangent and secant numbers.
Formal power series that are exponential generating functions for sequences of integers are called Hurwitz series. Hurwitz series form a ring, and they are also closed under composition. We can obtain the congruences that we want by studying the quotient ring of Hurwitz series modulo a prime p. The structure is easy to describe, but more important are derivations and their chain rules. The derivative D with respect to x is a derivation, but so is D^m whenever m is a power of p. Using these derivations we can prove that the set of Hurwitz series whose coefficients are periodic (mod p) is closed under the usual operations (including composition).
Tuesday November 4
Speaker: An Huang (Harvard)
Title: CW complex associated to digraphs
Abstract: Given a digraph with a choice of basis of certain path
space, one can construct a CW complex, and for different basis
choice, the resulting CW complexes are homotopic. This construction
provides a way to study digraphs, by familiar ideas in topology.
I will explain this construction, and some of its consequences.
This is joint work with S-T. Yau.
Tuesday November 18
Speaker: Olivier Bernardi (Brandeis)
Title: Differential equations for colored lattices
Abstract: We will present a solution to a statistical mechanics model on random lattices. More precisely, we consider the Potts model on the set of planar triangulations (embedded planar graph such that every face has degree 3). The partition function of this model is the generating function of vertex-colored triangulations counted according to the number of monochromatic edges and dichromatic edges. We characterize this partition function by a simple system of differential equations. Some special cases, such as properly 4-colored triangulations, lead to particularly simple equations waiting for a more direct combinatorial explanation.
This is joint work with Mireille Bousquet-Melou.
Tuesday December 2
Speaker: Cristobal Lemus (Brandeis)
Title: Lattice Path Factorization.
Abstract: We will present a few cases of lattice paths in the plane whose generating functions have factorizations into three parts corresponding to three types of subpaths. The method of factorization was introduced in I. Gessel’s paper “A factorization for formal Laurent series and lattice path enumeration.” We count these paths and subpaths with some added weights and as a result we obtain Delannoy, asymmetric Delannoy, Schröder and Narayana numbers.