Seminars and Colloquia by Series

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 MenascoUniversity 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 SwensonUT 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 speakersGeorgia 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 KoutschanRISC 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 WandBerkeley 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 WollanThe 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.

The minimum k-way cut problem

Series
Graph Theory Seminar
Time
Friday, June 11, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Ken-ichi KawarabayashiNational Institute of Informatics, Tokyo
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).

Asymptotic extremal graph theory is non-trivial

Series
Graph Theory Seminar
Time
Tuesday, May 18, 2010 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 270
Speaker
Sergey NorinPrinceton University

Please Note: 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.

East Coast Computer Algebra Day 2010

Series
Other Talks
Time
Saturday, May 15, 2010 - 08:00 for 8 hours (full day)
Location
Emory University
Speaker
East Coast Computer Algebra Day 2010Department of Mathematics and Computer Science, Emory University

Please Note: Anton Leykin is an invited speaker presenting "Certified numerical solving of systems of polynomial equations"

East Coast Computer Algebra Day (ECCAD) is an informal one-day meeting for those active or interested in computer algebra. It provides opportunities to learn and to share new results and work in progress.  The schedule includes invited speakers, a panel discussion, and contributed posters and software demonstrations. Importantly, plenty of time is allowed for unstructured interaction among the participants.  Researchers, teachers, students, and users of computer algebra are all welcome! Visit ECCAD for more details.

Pages