Georgia Institute of Technology College of Sciences

We will discuss how linear isoperimetric bounds in graph coloring lead to new and interesting results. To that end, we say a family of graphs embedded in surfaces is hyperbolic if for every graph in the family the number of vertices inside an open disk is linear in the number of vertices on the boundary of that disk. Similarly we say that a family is strongly hyperbolic if the same holds for every annulus. The concept of hyperbolicity unifies and simplifies a number of known results about coloring graphs on surfaces while resolving some open conjectures. For instance: we have shown that the number of 6-list-critical graphs embeddable on a fixed surface is finite, resolving a conjecture of Thomassen from 1997; that there exists a linear time algorithm for deciding 5-choosability on a fixed surface; that locally planar graphs with distant precolored vertices are 5-choosable (which was conjectured for planar graphs by Albertson in 1999 and recently resolved by Dvorak, Lidicky, Mohar and Postle); that for every fixed surface, the number of 5-list-colorings of a 5-choosable graph is exponential in the number of vertices. We may also adapt the theory to 3-coloring graphs of girth at least five on surface to show that: the number of 4-list-critical graphs of girth at least five on a fixed surface is finite; there exists a linear time algorithm for deciding 3-choosability of graph of girth at least five on a fixed surface; locally planar graphs of girth at least five whose cycles of size four are far apart are 3-choosable (proved for the plane by Dvorak and related to the recently settled Havel's conjecture for triangle-free graphs in the plane). This is joint work with Robin Thomas.

In this talk we first present some applied examples (coming from Economics and Finance) of Optimal Control Problems for Dynamical Systems with Delay (deterministic and stochastic). To treat such problems with the so called Dynamic Programming Approach one has to study a class of infinite dimensional HJB equations for which the existing theory does not apply due to their specific features (presence of state constraints, presence of first order differential operators in the state equation, possible unboundedness of the control operator). We will present some results on the existence of regular solutions for such equations and on existence of optimal control in feedback form.

The Green-Tao theorem says that the primes contain arithmetic progressions of arbitrary length. Tao and Ziegler extended it to polynomial progressions, showing that congurations {a+P_1(d), ..., a+P_k(d)} exist in the primes, where P_1, ..., P_k are polynomials in \mathbf{Z}[x] without constant terms (thus the Green-Tao theorem corresponds to the case where all the P_i are linear). We extend this result further, showing that we can add the extra requirement that d be of the form p-1 (or p + 1) where p is prime. This is joint work with Julia Wolf.