Second topic: An extension of Brooks' Theorem. Kittikorn Nakprasit presented last winter our extension of Brooks' Theorem: If G is a K_D+1-free graph with maximum degree at most D (where D 3), and f is a proper D-coloring of G-v for some vertex v of V(G), then G has a proper D-coloring f' such that the sizes of all color classes except one are the same. I will discuss some corollaries of this result.

It has been proved that the pagenumber of a k-tree is at most k+1, and conjectured that k is in fact a valid upper bound. We present an example of a 3-tree that cannot be embedded in three pages, providing a counterexample to this conjecture. We also present a new class of k-trees for which the conjecture holds and give an algorithm to produce a k-page embedding. (This is joint work with Gexin Yu and Douglas West as part of the summer REG.)

We prove this conjecture for up to 3 colors and disprove it for larger r. That is, for every fixed k and for n sufficiently large, F(n,2,k)=2^t_k-1(n) and F(n,3,k)=3^t_k-1(n). On the other hand, for fixed r>3 and k>2, the function F(n,r,k) is exponentially bigger than r^t_k-1(n). The proofs use Szemerédi's Regularity Lemma plus additional tools in extremal graph theory and provide an rare example of a precise result proved by the Regularity Lemma. We shall review several other problems that were solved using our methods. (This is joint work with N. Alon, P. Keevash, and B. Sudakov.)

It is shown that a simple, fast "greedy" algorithm for setting up the exchanges has surprising properties: no group of agents can deviate from the recommendation, or jointly reveal false lists to the centre, to the advantage of all members of the group - EVEN IF other agents in the system are deviating / lying.

A caterpillar is a tree having a single path incident to all edges. We prove that a connected outplanar graph G with girth 4 decomposes into at most \ceil(3n/8) caterpillars, and this is sharp. This is joint work with Douglas West and Derrick Cheng.

We also present results on optimal graph pebbling. The optimal pebbling number of a graph G is the minimum k such that there exists a distribution of k pebbles to the vertices of G such that for any vertex v, there exists a sequence of pebbling moves which results in a pebble on v. We show that for any connected n-vertex graph G, the optimal pebbling number of G is at most the ceiling of 2n/3. If time permits, we may give a simplified proof of the well-known results equality holds when G is a path or a cycle. (Joint work with David Bunde, Bryan Clark, Dan Cranston, Douglas West, and Erin Wolf.)

The classic Frobenius problem for {a, b, c, ...} has two parts: (1) determine the Frobenius number, and (2) given a target M, find nonnegative coefficients x, y, z, ... such that x a + y b + z c + ... = M. I will show how a shortest-path algorithm for directed weighted graphs leads to a reasonably efficient solution for input sizes less than one million. More advanced techniques lead to a fast solution even when the integers are very large, provided that the size of A is at most 6. (Joint work with Dale Beihoffer, David Einstein, and Albert Nijenhuis.)

(This is joint work with Alexandr Kostochka.)

The speaker will describe an efficient combinatorial approach to problems of this sort, implemented with a group of scientists at Rockefeller University (Andy DeWan, Chad Hayes, Josephine Hoh, Jurg Ott, Tony Parrado, and Richard Sackler).