Combinatorial Witnesses for Congruences of Restricted Partition Functions via Ehrhart Theory
Presenter
November 13, 2014
Keywords:
- Restricted Partition
MSC:
- 11P83
Abstract
The restricted partition function p(n,d) which counts the number of partitions of n into parts of size at most d is one of the most classic objects in combinatorics. From the point of view of Ehrhart theory, p(n,d) counts integer points in dilates of a (d-1)-dimensional simplex. In this talk, we use this geometric point of view to study arithmetic progressions of congruences of the form p(sk+r,d) = 0 mod m for all k.
Motivated by the work of Dyson, Andrews, Garvan, Kim, Stanton and others on the general partition function, we are not merely interested in arithmetic proofs of such congruences, but instead ask for combinatorial witnesses: To show divisibility we want to organize the set of partitions into disjoint cycles of length m.
It turns out that geometry is an excellent tool for constructing such combinatorial witnesses. Ehrhart theory induces a natural tiling of the partition simplex that can be used to construct natural cycles in several different ways. Following this approach, we obtain combinatorial witnesses for several infinite families of arithmetic progressions of congruences. Moreover, these cycles have a direct interpretation on the level of combinatorics, which leads us to a new type of decomposition of partitions with great potential for further applications.
One of the great benefits of the application of geometry to combinatorial problems is that one can draw pictures. Instead of using Ferrers diagrams to visualize one partition at a time, we can use the theory of lattice points in polytopes to visualize all paritions of a given number simultaneously and gain insight from their spatial relationship. In this talk, we will therefore take a very visual approach to the subject and present a new way of "looking at partitions" - literally.
This talk is about joint work with Dennis Eichhorn and Brandt Kronholm.