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.

I will explain how to construct a 4-variable knot invariant which expresses a recursion for the colored HOMFLY polynomial of a knot, and its implications on (a) asymptotics (b) the SL2 character variety of the knot (c) mirror symmetry.

The k-core of a (hyper)graph is the unique subgraph where all vertices have degree at least k and which is the maximal induced subgraph with this property. It provides one measure of how dense a graph is; a sparse graph will tend to have a k-core which is smaller in size compared to a dense graph. Likewise a sparse graph will have an empty k-core for more values of k. I will survey the results on the random k-core of various random graph models. A common feature is how the size of the k-core undergoes a phase transition as the density parameter passes a critical threshold. I will also describe how these results are related to a class of related problems that initially don't appear to involve random graphs. Among these is an interesting problem arising from probabilistic number theory where the random hypergraph model has vertex degrees that are "non-homogeneous"---some vertices have larger expected degree than others.

In this talk we will discuss the definition of chaoticity and entropic chaoticity, as well as the background that led us to define these quantities, mainly Kac's model and the Boltzmann equation. We will then proceed to investigate the fine balance required for entropic chaoticity by exploring situations where chaoticity is valid, but not entropic chaoticity. We will give a general method to construct such states as well as two explicit example, one of which is quite surprising.