Princeton University Combinatorics Seminar

P R I N C E T O N   U N I V E R S I T Y  



Spring 2015

Unless otherwise noted, seminar meets at 1:30 pm on Wednesdays in 214 Fine Hall.

February 9 Sophie Morel
Princeton University
Kazhdan-Lusztig polynomials: an arithmetic geometer's view
The goal is to explain some ways Kazhdan-Lusztig polynomials show up in arithmetic geometry and number theory.
February 18 Richard Ehrenborg
Princeton University and University of Kentucky
Weighted enumeration of consecutive 123-avoiding permutations and the Hurwitz zeta function
A permutation π =(π1,...,πn) is consecutive 123-avoiding if there is no index i such that πi < πi+1 < πi+2. Similarly, a permutation π is cyclically consecutive 123-avoiding if the indices are viewed modulo n. We consider a weighted enumeration problem of consecutive 123-avoiding permutations where we able to to determine an asymptotic expansion of the weighted enumeration. For the cyclically weighted enumeration we are able to determine an exact expression in terms of the Hurwitz zeta function. This yields an explicit combinatorial expression for the higher derivatives of the cotangent function.
February 25 Greta Panova
University of Pennsylvania
Kronecker coefficients -- combinatorics, complexity and beyond.
The Kronecker coefficients $g(\lambda,\mu,\nu)$ are defined as the multiplicity of an irreducible representation $S_\lambda$ of the symmetric group $S_n$ in the tensor product of two other irreducibles, $S_\mu \otimes S_\nu$. Finding a positive combinatorial formula for these nonnegative integers or even criteria for their positivity has been a 75+ year old problem in representation theory and algebraic combinatorics. Recently, the Kronecker coefficients appeared as central objects in the field of Geometric Complexity Theory and more questions about their computational complexity emerged.

In this talk we will discuss a few problems of different characters involving these coefficients -- the Saxl conjecture on the tensor square $S_\delta \otimes S_\delta$ where $\delta$ is the staircase partition, the combinatorial side with the new proof of Sylvester's theorem on the unimodality of the q-binomial coefficients as polynomials in q giving effective bounds on both, and some complexity results.

March 4
Gábor Hetyei
University of North Carolina at Charlotte
Counting genus one partitions and permutations
The study of counting rooted maps was initiated by Tutte, who was motivated by the four color conjecture, and the study of hypermaps grew out of this initiative. Hypermaps are pairs of permutations that can be topologically represented by labeled maps, the genus of the underlying surface may be expressed purely algebraically in terms of these permutations. Looking at the special case of rooted hypermonopoles leads to the definition of the genus of a permutation.

In this talk we prove a conjecture of Martha Yip stating that counting genus one partitions by the number of their elements and parts yields, up to a shift of indices, the same array of numbers as counting genus one rooted hypermonopoles. Our proof involves representing each genus one permutation by a four-colored noncrossing partition. This representation may be selected in a unique way for permutations containing no trivial cycles. The conclusion follows from a general generating function formula that holds for any class of permutations that is closed under the removal and reinsertion of trivial cycles. Our method also provides another way to count rooted hypermonopoles of genus one, and puts the spotlight on a class of genus one permutations that is invariant under an obvious extension of the Kreweras duality map to genus one permutations.

This is joint work with Robert Cori.

March 11 Mark McConnell
Princeton University
Voronoi neighbors of Dn lattices
Voronoi defined a tiling of the space of positive definite quadratic forms on Rn. Each tile is determined by a perfect lattice. Examples of perfect lattices include the root lattices An and Dn. We will focus on the tiles that are neighbors of a Dn tile. These are determined by some simple combinatorics, but there are exponentially many different Dn neighbors, and only a few families of them have been understood for all n. I will report on two recent results, one due to myself, and one joint work with Noam Elkies.
March 18 No meeting
Spring Break
March 25 Sinai Robins
Brown University and Nanyang Technological University
Multiply tiling Euclidean space by translations of a convex object
We study the problem of covering Euclidean space Rd by possibly overlapping translates of a convex body P such that almost every point is covered exactly k times for a fixed integer k. Such a covering of Euclidean space by translations of P is called a k-tiling. Classical tilings by translations (which are 1-tilings in this context) began with the work of the famous crystallographer Fedorov and with the work of Minkowski, who founded the Geometry of Numbers. Some 50 years later Venkov and McMullen gave a complete characterization of all convex objects that 1-tile Euclidean space.

Today we know that k-tilings can be tackled by methods from Fourier analysis, though some of their aspects can also be studied using purely combinatorial means. For many of our results there is both a combinatorial proof and a Harmonic analysis proof. For k larger than 1 the collection of convex objects that k-tile is much wider than the collection of objects that 1-tile. So it's a more diverse subject with plenty (infinite families) of examples in R2 as well. There is currently no complete knowledge of the polytopes that k-tile in dimension 3 or larger, and even in dimension 2 it is still challenging. We will cover both ``ancient'' as well as very recent results concerning 1-tilings and other k-tilings. This is based on some joint work with Nick Gravin, Dmitry Shiryaev, and Mihalis Kolountzakis.

April 10 Richard Stanley
Smith normal form and combinatorics
If A is an m x n matrix over a PID R (and sometimes more general rings), then there exists an m x m matrix P and an n x n matrix Q, both invertible over R, such that PAQ is a matrix that vanishes off the main diagonal, and whose main diagonal elements e1, e2, … , em satisfy ei | ei+1 in R. The matrix PAQ is called a Smith normal form (SNF) of A. The SNF is unique up to multiplication of the ei's by units in R. We will discuss some aspects of SNF related to combinatorics. In particular, we will give examples of SNF for some combinatorially interesting matrices. We also discuss a theory of SNF for random matrices over the integers recently developed by Yinghui Wang.

Room: 224 Fine
Note change in day and location!

April 29 Dennis Stanton
University of Minnesota
Another (q,t) world
A well studied (q,t)-analogue of symmetric functions are the Macdonald polynomials. In this talk I will survey another (q,t)-analogue, where q is a prime power from a finite field and t is an indeterminate. Analogues of facts about the symmetric group Sn are given for GLn(Fq), including

(1) counting factorizations of certain elements into reflections, (2) combinatorial properties of appropriate (q,t)-binomial coefficients, (3) Hilbert series for invariants on polynomial rings.

Some new conjectured explicit Hilbert series of rings of invariants over finite fields are given. This is joint work with Joel Lewis and Vic Reiner.

May 8 Yue Cai
University of Kentucky
q-Combinatorics: A new view

The idea of q-analogues can be traced back to Euler in the 1700's who was studying q-series, especially specializations of theta functions. Recall a q-analogue is a method to enumerate a set of objects by keeping track of its mathematical structure. For example, a combinatorial interpretation of the q-analogue of the Gaussian polynomial due to MacMahon in 1916 is given by summing over all 0-1 bit strings consisting of n-k zeroes and k ones the statistic q to the inversion number. Setting q=1 returns to the familiar binomial coefficient.

In this talk we show the classical q-Stirling numbers of the second kind can be expressed more compactly as a pair of statistics on a subset of restricted growth words. The resulting expressions are polynomials in q and 1 + q. We extend this enumerative result via a decomposition of a new poset whose rank generating function is the q-Stirling number Sq[n,k] which we call the Stirling poset of the second kind. This poset supports an algebraic complex and a basis for integer homology is determined. This is another instance of Hersh, Shareshian and Stanton's homological version of the Stembridge q = -1 phenomenon. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done beginning with de Médicis and Leroux's rook placement formulation. Time permitting, we will indicate a bijective argument à la Viennot showing the (q,t)-Stirling numbers of the first and second kind are orthogonal.

This is joint work with Margaret Readdy.

Room: 214 Fine
Usual room, but note change in day!

Organizers: R. Ehrenborg and M. Readdy

Last updated April 22, 2015