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.

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.

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.

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.

Title: A (new?) generalization of permutations
Abstract: An inversion sequence is a sequence of positive integers (e₁, ..., 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₁, ..., e_n) satisfies e_k < s_k, where s = (s₁, ..., 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.