Georgia Institute of Technology College of Sciences

The theory of graph minors developed by Robertson and Seymour is perhaps one of the deepest developments in graph theory. The theory is developed in a sequence of 23 papers, appearing from the 80's through today. The major algorithmic application of the work is a polynomial time algorithm for the k disjoint paths problem when k is fixed. The algorithm is relatively simple to state - however the proof uses the full power of the Robertson Seymour theory, and consequently runs approximately 400-500 pages. We will discuss a new proof of correctness that dramatically simplifies this result, eliminating many of the technicalities of the original proof. This is joint work with Ken-ichi Kawarabayashi.

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. It is known that every such inequality follows from the positive semi-definiteness of a certain infinite matrix. As an immediate consequence every algebraic inequality between the homomorphism densities follows from an infinite number of certain applications of the Cauchy-Schwarz inequality. Lovasz and, in a slightly different formulation, Razborov asked whether it is true or not that every algebraic inequality between the homomorphism densities follows from a _finite_ number of applications of the Cauchy-Schwarz inequality. In this talk, we show that the answer to this question is negative by exhibiting explicit valid inequalities that do not follow from such proofs. Further, we show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Joint work with Hamed Hatami.

A map is a connected graph G embedded in a surface S (a closed 2-manifold) such that all components of S -- G are simply connected regions. A map is rooted if an edge is distinguished together with a direction on the edge and a side of the edge. Maps have been enumerated by both mathematicians and physicists as they appear naturally in the study of representation theory, algebraic geometry, and quantum gravity. In 1986 Bender and Canfield showed that the number of n-edge rooted maps on an orientable surface of genus g is asymptotic to t_g n^{5(g-1)/2}12n^n, (n approaches infinity), where t_g is a positive constant depending only on g. Later it was shown that many families of maps satisfy similar asymptotic formulas in which tg appear as \universal constants". In 1993 Bender et al. derived an asymptotic formula for the num- ber of rooted maps on an orientable surface of genus g with i faces and j vertices. The formula involves a constant tg(r) (which plays the same role as tg), where r is determined by j=i.In this talk, we will review how these asymptotic formulas are obtained using Tutte's recursive approach. Connections with random trees, representation theory, integrable systems, Painleve I, and matrix integrals will also be mentioned. In particular, we will talk aboutour recent results about a simple relation between tg(r) and tg, and asymptotic formulas for the numbers of labeled graphs (of various connectivity)of a given genus. Similar results for non-orientable surfaces will also be discussed.

A fundamental question in topological graph theory is as follows: Given a surface S and an integer t > 0, which graphs drawn in S are t-colorable? We say that a graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In 1993, Carsten Thomassen showed that there are only finitely many six-critical graphs on a fixed surface with Euler genus g. In this talk, I will describe a new short proof of this fact. In addition, I will describe some structural lemmas that were useful to the proof and describe a list-coloring extension that is helpful to ongoing work that there are finitely many six-list-critical graphs on a fixed surface. This is a joint project with Ken-ichi Kawarabayashi of the National Institute of Informatics, Tokyo.