Seminars and Colloquia by Series

Theory/ACO Seminar - Matching in Lopsided Bipartite Graphs and a New Matching Polytope

Series
Other Talks
Time
Friday, August 20, 2010 - 14:00 for 1 hour (actually 50 minutes)
Location
Klaus 1447
Speaker
Kamal Jain – Microsoft Research, Redmond, WA

Please Note: This talk should be non-technical except the last few slides. The talk is based on a work done in collaboration with Denis Charles, Max Chickering, Nikhil Devanur, and Manan Sanghi, all from Microsoft.

Lopsided bipartite graphs naturally appear in advertising setting. One side is all the eyeballs and the other side is all the advertisers. An edge is when an advertiser wants to reach an eyeball, aka, ad targeting. Such a bipartite graph is lopsided because there are only a small number of advertisers but a large number of eyeballs. We give algorithms which have running time proportional to the size of the smaller side, i.e., the number of advertisers. One of the main ideas behind our algorithm and as well as the analysis is a property, which we call, monotonic quality bounds. Our algorithm is flexible as it could easily be adapted for different kinds of objective functions. Towards the end of the talk we will describe a new matching polytope. We show that our matching polytope is not only a new linear program describing the classical matching polytope, but is a new polytope together with a new linear program. This part of the talk is still theoretical as we only know how to solve the new linear program via an ellipsoid algorithm. One feature of the polytope, besides being intriguing, is that it has some notion of fairness built in. This is important for advertising since if an advertiser wants to reach 10 million users of type A or type B, advertiser won't necessarily be happy if we show the ad to 10 million users of type A only (though it fulfills the advertising contract in a technical sense).

Modeling and simulation of two phase flow on rough surface

Series
Applied and Computational Mathematics Seminar
Time
Friday, August 20, 2010 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 154
Speaker
Xiao-Ping Wang – Hong Kong University of Science and Technology
In this talk, I will  describe a newly developed phase field model for two phase fluid flow based on Cahn Hilliard  Navier Stokes equation with generalized Navier boundary condition.  Homogenization method is used to derive  the Wenzel's and Cassie's equations for two phase flow on rough surfaces. Efficient numerical method for the model will also be discussed. We then present some numerical results on two phase flow on rough and patterned surfaces.

Color-Critical Graphs on Surfaces

Series
Dissertation Defense
Time
Thursday, August 19, 2010 - 10:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 114
Speaker
Carl Yerger – School of Mathematics, Georgia Tech
A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring \phi of C can be extended inside the cycle, or there exists a subgraph H with at most 5^{q^3} vertices such that \phi cannot be extended to a 5-coloring of H. In Chapter 2, we provide an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. Finally, in Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface \Sigma, with Euler genus g and has no cycles of length four through ten, then |V(G)| \leq 2442g + 37.

Isotopies of links carried by Matsuda branched surfaces

Series
Geometry Topology Seminar
Time
Monday, August 16, 2010 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Bill Menasco – University of Buffalo
We introduce two related sets of topological objects in the 3-sphere, namely a set of two-component exchangable links termed "iterated doubling pairs", and a see of associated branched surfaces called "Matsuda branched surfaces". Together these two sets possess a rich internal structure, and allow us to present two theorems that provide a new characterization of topological isotopy of braids, as well as a new characterization of transversal isotopy of braids in the 3-sphere endowed with the standard contact structure. This is joint work with Doug Lafountain, and builds upon previous seminal work of Hiroshi Matsuda.

Phylogenetic Supertree Methods: tools for reconstructing the Tree of Life

Series
Mathematical Biology Seminar
Time
Monday, August 16, 2010 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 271
Speaker
Shel Swenson – UT Austin
Estimating the Tree of Life, an evolutionary tree describing how all life evolved from a common ancestor, is one of the major scientific objectives facing modern biologists. This estimation problem is extremely computationally intensive, given that the most accurate methods (e.g., maximum likelihood heuristics) are based upon attempts to solve NP-hard optimization problems. Most computational biologists assume that the only feasible strategy will involve a divide-and-conquer approach where the large taxon set is divided into subsets, trees are estimated on these subsets, and a supertree method is applied to assemble a tree on the entire set of taxa from the smaller "source" trees. I will present supertree methods in a mathematical context, focusing on some theoretical properties of MRP (Matrix Representation with Parsimony), the most popular supertree method, and SuperFine, a new supertree method that outperforms MRP.

Additive Combinatorics Mini-Conference

Series
Other Talks
Time
Saturday, June 26, 2010 - 11:00 for 6 hours
Location
Skiles 169
Speaker
Various speakers – Georgia Tech
This mini-conference will feature about six speakers on various topics in additive combinatorics.

The beneficial use of homomorphic images in computer algebra

Series
Algebra Seminar
Time
Friday, June 18, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Christoph Koutschan – RISC Austria –
In this talk we recall some modular techniques (chinese remaindering,rational reconstruction, etc.) that play a crucial role in manycomputer algebra applications, e.g., for solving linear systems over arational function field, for evaluating determinants symbolically,or for obtaining results by ansatz ("guessing"). We then discuss howmuch our recent achievements in the areas of symbolic summation andintegration and combinatorics benefited from these techniques.

Positivity of monodromies of open book decompositions

Series
Geometry Topology Seminar
Time
Tuesday, June 15, 2010 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Andy Wand – Berkeley and Max Planck Institute
I will describe some results concerning factorizations ofdiffeomorphisms of compact surfaces with boundary. In particular, Iwill describe a refinement of the well-known \emph{right-veering}property, and discuss some applications to the problem ofcharacterization of geometric properties of contact structures interms of monodromies of supporting open book decompositions.

A shorter proof for the disjoint paths algorithm

Series
Graph Theory Seminar
Time
Friday, June 11, 2010 - 16:20 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Paul Wollan – The Sapienza University of Rome
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.

Pages