Back to main page
### Talks by invited speakers

**Marcelo Aguiar**,
Cornell University

** Title: ** The ring of graphs and the chromatic polynomial

** Abstract: ** Certain basic operations among graphs resemble addition and
multiplication of ordinary numbers.
Formally, the species of graphs is a ring in an appropriate category.
We explain this fact and employ it to obtain
a novel understanding and a wide generalization of the chromatic
polynomial (and the corresponding symmetric function of Stanley) in
terms of ring theory. The talk is based on joint work with Swapneel
Mahajan and Jacob White.

**Sukhada Fadnavis**, Harvard University

** Title: ** The `shameful conjecture' and related results

** Abstract: ** Consider a random coloring *c*_{q} of the vertices of a
graph *G* on *n* vertices obtained by coloring each node independently and
uniformly with one of *q* colors. Let *p(q)* denote the proobability that
*c*_{q} is a proper coloring of *G*. The shameful conjecture (now a
theorem, proved by F. M. Dong) states that *p(q+1) ≥ p(q)* for all *q ≥ n*.
In this talk I will discuss some complementary results and also generalizations involving
non-uniform distributions.

**Michel Goemans**, MIT

** Title: ** Polynomiality for bin packing with a constant number of item types

** Abstract: **
Consider the bin packing problem with

*d* different item sizes

*s*_{i} and item multiplicities

*a*_{i}, where

*d* is fixed and all
numbers are given in binary encoding. This problem is also known as
the 1-dimensional cutting stock problem. The complexity of this
problem was open even for

*d=3*. In this talk, I will provide an
algorithm which, for any constant

*d*, solves the problem in
polynomial time.

Our approach is geometric, and the algorithm in fact solves the
following problem for constant *d* in polynomial time: given two
*d*-dimensional polytopes *P* and *Q*, find the smallest number of
integer points in *P* whose sum lies in *Q*.

If time remains, applications to *high multiplicity* scheduling
will also be discussed. In such problems, the number of copies of each
job type is given in binary encoding and each type comes with certain
parameters such as release dates, processing times and deadlines. A
variety of high multiplicity scheduling problems can be solved in
polynomial time if the number of job types is constant.

Joint work with Thomas Rothvoss, U. of Washington.

**Carly Klivans**,
Brown University

** Title: ** Scheduling Problems

** Abstract: ** We introduce the notion of a scheduling problem which is a boolean
function *S* over atomic formulas of the form *x*_{i} ≤ x_{j}.
Considering the *x*_{i} as jobs to be performed, an integer assignment
satisfying S schedules the jobs subject to the constraints of the atomic formulas.
We will look specifically at enumerating solutions to *S*. The number of solutions
is given by a polynomial function in the number of time slots allowed. These scheduling
polynomials include the chromatic polynomial of a graph, the zeta polynomial of a lattice,
the Billera-Jia-Reiner polynomial of a matroid and the newly defined arboricity polynomial
of a matroid. I will discuss the algebraic and geometric techniques used in understanding
scheduling problems. In particular, we will consider naturally associated quasisymmetric
functions and polyhedral spaces that encode scheduling solutions.

**Carla Savage**,
North Carolina State University

** Title: ** A (new?) generalization of permutations

** Abstract: **
An inversion sequence is a sequence of positive integers

*(e*_{1}, ..., e_{n}) satisfying

*e*_{k} < k. Inversion sequences are used in various ways to encode permutations, for example, Lehmer codes and inversion tables.

In this talk we focus on a generalization of inversion sequences, with statistics inherited from the theory of lecture hall partitions. An s-inversion sequence *(e*_{1}, ..., e_{n}) satisfies *e*_{k} < s_{k}, where *s = (s*_{1}, ..., s_{n}) is an arbitrary sequence of positive integers.

We will give examples of the surprising power of *s*-inversion sequences to model statistics on a variety of combinatorial families, with some applications and open questions.