Combinatorics seminar
Combinatorics Seminar - Spring 2014
Monday, 12pm-1pm
Room 226, Goldsmith building
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.
-
Monday March 10
Speaker: Yiting Li
Title: Menage numbers and Menage permutation
Abstract: A straight Menage permutation is a permutation $\pi\in S_n$ such that $\pi(i)$ is neither $i$ nor $i+1$. An ordinary Menage
permutation is a permutation $\pi\in S_n$ such that $\pi(i)$ is
neither $i$ nor $i+1 \mod n$. The numbers of straight (ordinary)
Menage permutations in $S_n$ are called straight (ordinary)
Menage numbers. In this talk I'll prove two formulas for the
generating functions of straight and ordinary Menage numbers. I'll
also give the formulas which count straight and ordinary Menage
permutations by cycles.
-
Monday March 17
Speaker: Olivier Bernardi
Title: Counting the spanning trees of the hypercube
Abstract: I will present two combinatorial proofs of a counting
formula for the spanning trees of the hypercube. One of the proof highlights mysterious independence property for the directions of edges in the
uniformly random spanning tree of the hypercube.
-
Monday March 31
Speaker: Jordan Tirrell
Title:Counting Non-crossing Trees by Descents
Abstract: A non-crossing graph is a (rooted) graph with its vertices drawn on the boundary of a disk and its edges drawn in the interior without crossing. We will count non-crossing trees by their ascent and descent edges and then find some nice bijections, in particular to connected non-crossing graphs. We will also look at a symmetrization of these numbers and the corresponding combinatorial interpretations.
-
Monday April 7
Speaker: Ira Gessel
Title: Rook theory and simplicial complexes
Abstract: Rook theory deals with placements of nonattacking rooks on a board—a subset of [n] x [n], where [n]={1, 2,…, n}. The rook numbers of a board count placements of k nonattacking rooks on the board. The hit numbers of the board count placements of n nonattacking rooks on [n] x [n] in which k of the rooks lie on the board. The fundamental identity of rook theory relates the rook numbers and hit numbers of a board.
The sets of nonattacking rook positions in [n] x [n] form a pure simplicial complex with the property that any two faces of the same size are contained in the same number of facets, and this property is all we need to prove the fundamental identity. Thus we can generalize the fundamental identity to other simplicial complexes with the same property; in particular, those corresponding to matchings and to rooted forests.
We will also discuss generalizations in this context of the reciprocity theorem for factorial rook polynomials that relates the rook numbers of a board to the rook numbers of its complement.
Previous semesters:
Fall 2013.