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.