Wednesday, May 23, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Jim Orlin – MIT Sloan Management
Over the past 30 years, researchers have developed successively faster
algorithms for the maximum flow problem. The best strongly polynomial
time algorithms have come very close to O(nm) time. Many researchers
have conjectured that O(nm) time is the "true" worst case running time.
We resolve the issue in two ways. First, we show how to solve the max
flow problem in O(nm) time. Second, we show that the running time is
even faster if m = O(n). In this case, the running time is O(n^2/log n).
Tuesday, May 22, 2012 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peter Winkler – Dartmouth College, Hanover, NH
We derive optimal strategies for a pursuit-and-evasion game and show that when pitted against each other, the two strategies construct a small set containing unit-length line segments at all angles. Joint work with Y. Babichenko, Y. Peres, R. Peretz, and P. Sousi.
Monday, May 21, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Chris Hillar – UC Berkeley
We discuss the theory of symmetric Groebner bases, a concept allowing
one to prove Noetherianity results for symmetric ideals in polynomial
rings with an infinite number of variables. We also explain applications
of these objects to other fields such as algebraic statistics, and we
discuss some methods for computing with them on a computer. Some of this
is joint work with Matthias Aschenbrener and Seth Sullivant.
Monday, May 21, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tianjun Ye – School of Mathematics, Georgia Tech
Classical vertex coloring problems ask for the minimum number of colors needed
to color the vertices of a graph, such that adjacent vertices
use different colors. Vertex coloring does have quite a few practical applications
in
communication theory, industry engineering and computer science. Such examples can
be
found in the book of Hansen and Marcotte.
Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem,
even for triangle-free graphs. Intutively, large girth may help reduce the chromatic
number.
However, in 1959, Erdos used the probabilitic method to prove that for any two
positive
integers g and k, there exist graphs of girth at least g and chromatic number at
least k.
Thus, restricting girth alone does not help bound the chromatic number. However, if
we
forbid certain tree structure in addition to girth restriction, then it is possible
to bound the
chromatic number. Randerath determined several such tree structures, and conjectured
that
if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a
star K1,4
with two branches subdivided once.
The main result of this thesis is that Randerath's conjecture is true for graphs
with odd
girth at least 7. We also give an outline of a proof that Randerath's conjecture
holds for
graphs with maximum degree 4.
Friday, May 18, 2012 - 14:05 for 1 hour (actually 50 minutes)
Location
006 Skiles
Speaker
Ke Chen – University of Liverpool
Both segmentation and registration are important image processing tasks in a number of real life applications. While there exist powerful and effective models,many scientific challenges remain open. In this talk, I shall first present some image segmentation work of modelsand algorithms in two and three dimensions, followed by some recent works of selective segmentationThen I introduce some new work on multimodality image registration modelling.Numerical experiments will demonstrate the advantages of our new models and algorithms over existing results. Collaborators related to this work include Noor Badshah (Peshawar, Pakistan), Jian-ping Zhang and Bo Yu (Dalian, China),Lavdie Rada (Liverpool), C Brito (Mexico) and N Chumchob (Thailand).
Friday, May 18, 2012 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Yunhui Wu – Brown University
We prove the moduli space M_{g,n} of the surface of g genus with n punctures admits no complete, visible, nonpositively curved Riemannian metric, which will give a connection between conjectures from P.Eberlein and Brock-Farb. Motivated from this connection, we will prove that the translation length of a parabolic isometry of a proper visible CAT(0) space is zero. As an application of this zero property, we will give a detailed answer toP.Eberlein's conjecture.
Monday, May 14, 2012 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Kashyap Rajeevsarathy – IISER Bhopal
Let S_g be a closed orientable surface of genus g > 1 and C a simple closed nonseparating curve in S_g. Let t_C denote a left handed Dehn twist about C. A fractional power of t_C of exponent L/n is a h in Mod(S_g) such that h^n = t_C^L. Unlike a root of a t_C, a fractional power h can exchange the sides of C. We will derive necessary and sufficient conditions for the existence of both side-exchanging and side-preserving fractional powers. We will give some applications of the main result in both cases. Finally, we give a complete classification of a certain class of side-preserving and side-exchanging fractional powers on S_5.
Monday, May 7, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Inanc Baykur – Max Planck
Surface bundles and Lefschetz fibrations over surfaces constitute a rich source of examples of smooth, symplectic, and complex manifolds. Their sections and multisections carry interesting information on the smooth structure of the underlying four-manifold. In this talk we will discuss several problems and results on surface bundles, Lefschetz fibrations, and their (multi)sections, which we will tackle, for the most part, using various mapping class groups of surfaces. Conversely, we will use geometric arguments to obtain some structural results for mapping class groups.
Friday, May 4, 2012 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Professor Bernard Chevreau – University of Bordeaux 1
In the first part of the talk we will give a brief survey of significant
results going from S. Brown pioneering work showing the existence of
invariant subspaces for subnormal operators (1978) to Ambrozie-Muller
breakthrough asserting the same conclusion for the adjoint of a
polynomially bounded operator (on any Banach space) whose spectrum
contains the unit circle (2003). The second part will try to give some
insight of the different techniques involved in this series of results,
culminating with a brilliant use of Carleson interpolation theory for
the last one. In the last part of the talk we will discuss additional
open questions which might be investigated by these techniques.