MSRI-UP 2012: Enumerative Combinatorics
| Home | Research Topic | People | Colloquia | Research Projects |
During the first two weeks of MSRI-UP, in preparation for their research, students will be introduced to several topics in enumerative combinatorics, including Möbius functions, partially-ordered sets, polyhedra, lattice-point enumeration, hyperplane arrangements, and various graph polynomials. During the remainder of the program, the students will work in teams on research projects. Below we give examples of two research projects.
Sample research project I: Graceful labellings
A graceful labelling of a graph G=(V,E) is an assignment of the vertices with distinct labels from 1 to |V| such that the absolute values of the differences of labels of adjacent vertices are the numbers 1 to |E|. A major conjecture in graph theory suggests that every tree has a graceful labelling. Study a less restrictive problem: namely, given a integer paramenter k, how many weakly graceful labellings are there of size k? Here a weakly graceful labelling of size k means that we assign (not necessarily distinct) labels from 1 to k in such a way that the absolute values of the differences of labels of adjacent vertices are distinct. This problem can be tackled from the viepoint of inside-out polytopes.
Sample research project II: Ehrhart series decompositions for rational polytopes
The Ehrhart polynomial of a lattice polytope P (the convex hull of a finite number of points in Z^d) counts the number of integer lattice points in integer dilates of P. The Ehrhart series is the generating function of the Ehrhart polynomial (and thus encodes the same information). Ehrhart's theorem says that if P is a lattice polytope then its Ehrhart series is of the form h(z)/(1-z)^{d+1} for some polynomial h(z). Alan Stapledon [http://arxiv.org/abs/0904.3035 ] used a decomposition of h(z) into two palindromic polynomials and proved inequalities for their coefficients, which in turn implied (known, famous) inequalities on the coefficients of h(z). If P is rational (i.e., a convex hull of points in Q^d) then its Ehrhart series can be written as h(z)/(1-z^p)^{d+1} for some p. Find and study a Stapledon-like decomposition of h(z) in this rational case. A first pointer could be Matthew Fiset and Alexander Kasprzyk's paper [Electronic Journal of Combinatorics 15(1), 2008, Note 18].
Sample research project I: Graceful labellings
A graceful labelling of a graph G=(V,E) is an assignment of the vertices with distinct labels from 1 to |V| such that the absolute values of the differences of labels of adjacent vertices are the numbers 1 to |E|. A major conjecture in graph theory suggests that every tree has a graceful labelling. Study a less restrictive problem: namely, given a integer paramenter k, how many weakly graceful labellings are there of size k? Here a weakly graceful labelling of size k means that we assign (not necessarily distinct) labels from 1 to k in such a way that the absolute values of the differences of labels of adjacent vertices are distinct. This problem can be tackled from the viepoint of inside-out polytopes.
Sample research project II: Ehrhart series decompositions for rational polytopes
The Ehrhart polynomial of a lattice polytope P (the convex hull of a finite number of points in Z^d) counts the number of integer lattice points in integer dilates of P. The Ehrhart series is the generating function of the Ehrhart polynomial (and thus encodes the same information). Ehrhart's theorem says that if P is a lattice polytope then its Ehrhart series is of the form h(z)/(1-z)^{d+1} for some polynomial h(z). Alan Stapledon [http://arxiv.org/abs/0904.