## Seminars and Colloquia by Series

Thursday, September 2, 2010 - 12:05 , Location: Skiles 114 , Luke Postle , Math, GT , Organizer: Robin Thomas
A deep theorem of Thomassen shows that for any surface there are only finitely many 6-critical graphs that embed on that surface. We give a shorter self-contained proof that for any 6-critical graph G that embeds on a surface of genus g, that |V(G)| is at most linear in g. Joint work with Robin Thomas.
Friday, June 11, 2010 - 16:20 , Location: Skiles 254 , Paul Wollan , The Sapienza University of Rome , Organizer: Robin Thomas
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.
Friday, June 11, 2010 - 15:05 , Location: Skiles 254 , Ken-ichi Kawarabayashi , National Institute of Informatics, Tokyo , Organizer: Robin Thomas
We consider a the minimum k-way cut problem for unweighted graphs  with a bound $s$ on the number of cut edges allowed. Thus we seek to remove as few  edges as possible so as to split a graph into k components, or  report that this requires cutting more than s edges. We show that this  problem is fixed-parameter tractable (FPT) in s.  More precisely, for s=O(1), our algorithm runs in quadratic time  while we have a different linear time algorithm  for planar graphs and bounded genus graphs.  Our result solves some open problems and contrasts W[1] hardness (no  FPT unless P=NP) of related formulations of the k-way cut  problem. Without the size bound, Downey et al.~[2003] proved that  the minimum k-way cut problem is W[1] hard in k even for simple  unweighted graphs.  A simple reduction shows that vertex cuts are at least as hard as edge cuts,  so the minimum k-way vertex cut is also W[1] hard in terms of  k. Marx [2004] proved that finding a minimum  k-way vertex cut of size s is also W[1] hard in s. Marx asked about  FPT status with edge cuts, which is what we resolve here. We also survey approximation results for the minimum k-way cut problem, and conclude some open problems. Joint work with Mikkel Thorup (AT&T Research).
Tuesday, May 18, 2010 - 16:30 , Location: Skiles 270 , Sergey Norin , Princeton University , Organizer: Robin Thomas

Please note the location: Last minute room change to Skiles 270.

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.
Thursday, April 29, 2010 - 12:05 , Location: Skiles 255 , Vladimir Nikiforov , University of Memphis , Organizer: Xingxing Yu
In 1997 Kannan and Frieze defined the \emph{cut-norm} $\left\Vert A\right\Vert_{\square}$ of a $p\times q$ matrix $A=\left[ a_{ij}\right]$ as%$\left\Vert A\right\Vert _{\square}=\frac{1}{pq}\max\left\{ \left\vert\sum_{i\in X}\sum_{j\in Y}a_{ij}\right\vert :X\subset\left[ p\right],Y\subset\left[ q\right] ,\text{ }X,Y\neq\varnothing\right\} .$More recently, Lov\'{a}sz and his collaborators used the norm $\left\VertA\right\Vert _{\square}$ to define a useful measure of similarity between anytwo graphs, which they called \emph{cut-distance. }It turns out that the cut-distance can be extended to arbitrary complexmatrices, even non-square ones. This talk will introduce the basics of thecut-norm and \ cut-distance for arbitrary matrices, and present relationsbetween these functions and some fundamental matricial norms, like theoperator norm. In particular, these relations give a solution to a problem of Lov\'{a}sz.Similar questions are discussed about the related norm$\left\Vert A\right\Vert _{\boxdot}=\max\left\{ \frac{1}{\sqrt{\left\vertX\right\vert \left\vert Y\right\vert }}\left\vert \sum_{i\in X}\sum_{j\inY}a_{ij}\right\vert :X\subset\left[ p\right] ,Y\subset\left[ q\right],\text{ }X,Y\neq\varnothing\right\} .$which plays a central role in the \textquotedblleft expander mixinglemma\textquotedblright.
Thursday, February 18, 2010 - 12:05 , Location: Skiles 255 , Professor Jason Gao , School of Mathematics and Statistics Carleton University , , Organizer: Xingxing Yu
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 naturallyin the study of representation theory, algebraic geometry, and quantum gravity.In 1986 Bender and Canfield showed that the number of n-edgerooted maps on an orientable surface of genus g is asymptotic tot_g n^{5(g-1)/2}12n^n,  (n approachces infinity),where t_g is a positive constant depending only on g. Later it wasshown that many families of maps satisfy similar asymptotic formulasin 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 facesand j vertices. The formula involves a constant tg(r) (which plays thesame 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.
Tuesday, January 26, 2010 - 10:00 , Location: Skiles 255 , Sergey Norin , Princeton University , Organizer: Robin Thomas
A graph G contains a graph H as a minor if a graph isomorphic to H can be obtained from a subgraph of G bycontracting edges. One of the central results of the rich theory of graph minors developed by Robertson and Seymour is an approximate description of graphs that do not contain a fixed graph as a minor. An exact description is only known in a few cases when the excluded minor is quite small.In recent joint work with Robin Thomas we have proved a conjecture of his, giving an exact characterization of all large, t-connected graphs G that do not contain K_t, the complete graph on t vertices, as a minor. Namely, we have shown that for every integer t there exists an integer N=N(t) such that a t-connected graph G on at least N vertices has no K_t minor if and only if G contains a set of at most t- 5 vertices whose deletion makes G planar. In this talk I will describe the motivation behind this result, outline its proof and mention potential applications of our methods to other problems.
Thursday, December 3, 2009 - 12:05 , Location: Skiles 255 , Carl Yerger , Math, GT , Organizer: Robin Thomas
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.
Thursday, November 19, 2009 - 12:05 , Location: Skiles 255 , Graham Brightwell , London School of Economics , Organizer: Robin Thomas
Several interesting models of random partial orders can be described via a process that builds the partial order one step at a time, at each point adding a new maximal element. This process therefore generates a linear extension of the partial order in tandem with the partial order itself. A natural condition to demand of such processes is that, if we condition on the occurrence of some finite partial order after a given number of steps, then each linear extension of that partial order is equally likely. This condition is called "order-invariance". The class of order-invariant processes includes processes generating a random infinite partial order, as well as those that amount to taking a random linear extension of a fixed infinite poset. Our goal is to study order-invariant processes in general. In this talk, I shall focus on some of the combinatorial problems that arise. (joint work with Malwina Luczak)
Friday, October 30, 2009 - 15:05 , Location: Skiles 255 , Asaf Shapira , Math and CS, GT , Organizer: Robin Thomas
A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least logn/100logk, improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that this bound is tight (up to a constant depending on k). We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954. This is joint work with Robin Thomas.