Seminars and Colloquia by Series

The Complexity of Scarf's Lemma and Related Problems

Series
ACO Student Seminar
Time
Wednesday, March 4, 2009 - 13:30 for 2 hours
Location
ISyE Executive Classroom
Speaker
Shiva KintaliCS, Georgia Tech
Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking stable solutions. However, the complexity of the computational version of Scarf's lemma (Scarf) remained open. In this talk, I will prove that Scarf is complete for the complexity class PPAD. This shows that Scarf is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for Scarf unless PPAD \subseteq P. I will also talk about fractional stable paths problem, finding fractional kernels in digraphs, finding fractional stable matching in hypergraphic preference systems and finding core in an N-person balanced game with non-transferable utilities. I will show the connection between these problems through Scarf's lemma and address the complexity of these problems.

Analysis of a an Age-Structured Population Model with Monotone Birth Rate Function

Series
Mathematical Biology Seminar
Time
Wednesday, March 4, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Sean Ellermeyer Kennesaw State University
We consider a class of age-structured population models in which the central modeling assumption is simply that the birth rate depends on the size of the adult population. For the most part, we in fact assume that the birth rate is a monotone non-decreasing function of the adult population size. Despite the simplicity of our modeling assumptions (or perhaps because of it), we will see that this class of models admits a wide variety of solutions (exponentially growing, lineary growing, periodic, etc.) Much of the analysis of these models can be carried out using elementary techniques and we present some specific examples in which explicit solutions (which are elementary functions) can be generated. We also consider some questions related to the inverse problem for these models.

What we know about the two-phase Stefan problem under minimal assumptions

Series
PDE Seminar
Time
Tuesday, March 3, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Marianne KortenKansas State University, Manhattan
In this talk I will describe recent work with C. N. Moore about the two-phase Stefan problem with a degenerate zone. We start with local solutions (no reference to initial or boundary data) and then obtain intrinsic energy estimates, that will in turn lead to the continuity of the temperature. We then show existence and uniqueness of solutions with signed measures as data. The uniqueness problem with signed measure data has been open for some 30 years for any degenerate parabolic equation.

Hypergeometric functions: the GKZ-perspective

Series
Algebra Seminar
Time
Monday, March 2, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Uli WaltherPurdue University
Starting with some classical hypergeometric functions, we explain how to derive their classical univariate differential equations. A severe change of coordinates transforms this ODE into a system of PDE's that has nice geometric aspects. This type of system, called A-hypergeometric, was introduced by Gelfand, Graev, Kapranov and Zelevinsky in about 1985. We explain some basic questions regarding these systems. These are addressed through homology, combinatorics, and toric geometry.

Annulus open book decompositions and the self linking number

Series
Geometry Topology Seminar
Time
Monday, March 2, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Keiko KawamuroIAS
We introduce a construction of an immersed surface for a null-homologous braid in an annulus open book decomposition. This is hinted by the so called Bennequin surface for a braid in R^3. By resolving the singularities of the immersed surface, we obtain an embedded Seifert surface for the braid. Then we compute a self-linking number formula using this embedded surface and observe that the Bennequin inequality is satisfied if and only the contact structure is tight. We also prove that our self-linking formula is invariant (changes by 2) under a positive (negative) braid stabilization which preserves (changes) the transverse knot class.

Introduction to metric and comparison geometry

Series
Geometry Topology Working Seminar
Time
Friday, February 27, 2009 - 15:05 for 2.5 hours
Location
Skiles 269
Speaker
Igor BelegradekGa Tech
Comparison geometry studies Riemannian manifolds with a given curvature bound. This minicourse is an introduction to volume comparison (as developed by Bishop and Gromov), which is fundamental in understanding manifolds with a lower bound on Ricci curvature. Prerequisites are very modest: we only need basics of Riemannian geometry, and fluency with fundamental groups and metric spaces. In the third (2 hour) lecture I shall prove volume and Laplacian comparison theorems.

Large almost monochromatic subsets in hypergraphs

Series
Combinatorics Seminar
Time
Friday, February 27, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Benny SudakovUCLA
We show that for all \el an \epsilon>0 there is a constant c=c(\ell,\epsilon)>0 such that every \ell-coloring of the triples of an N-element set contains a subset S of size c\sqrt{\log N} such that at least 1-\epsilon fraction of the triples of S have the same color. This result is tight up to the constant c and answers an open question of Erd\H{o}s and Hajnal from 1989 on discrepancy in hypergraphs. For \ell \geq 4 colors, it is known that there is an \ell-coloring of the triples of an N-element set whose largest monochromatic subset has cardinality only \Theta(\log \log N). Thus, our result demonstrates that the maximum almost monochromatic subset that an \ell-coloring of the triples must contain is much larger than the corresponding monochromatic subset. This is in striking contrast with graphs, where these two quantities have the same order of magnitude. To prove our result, we obtain a new upper bound on the \ell-color Ramsey numbers of complete multipartite 3-uniform hypergraphs, which answers another open question of Erd\H{o}s and Hajnal. (This is joint work with D. Conlon and J. Fox.)

Introduction to metric and comparison geometry

Series
Other Talks
Time
Friday, February 27, 2009 - 15:00 for 2 hours
Location
Skiles 269
Speaker
Igor BelegradekSchool of Mathematics, Georgia Tech
Comparison geometry studies Riemannian manifolds with a given curvature bound. This minicourse is an introduction to volume comparison (as developed by Bishop and Gromov), which is fundamental in understanding manifolds with a lower bound on Ricci curvature. Prerequisites are very modest: we only need basics of Riemannian geometry, and fluency with fundamental groups and metric spaces. In the third (2 hour) lecture I shall prove volume and Laplacian comparison theorems.

Coupling in ergodic problems for Stochastic Navier--Stokes. Part II

Series
Probability Working Seminar
Time
Friday, February 27, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 268
Speaker
Sergio AlmadaSchool of Mathematics, Georgia Tech
This is a continuation of last week's seminar. The talk is based on a paper by Kuksin, Pyatnickiy, and Shirikyan. In this paper, the convergence to a stationary distribution is established by partial coupling. Here, only finitely many coordinates in the (infinite-dimensional) phase space participate in the coupling while the dynamics takes care of the other coordinates.

Fredholm operators

Series
SIAM Student Seminar
Time
Friday, February 27, 2009 - 12:30 for 2 hours
Location
Skiles 269
Speaker
Weizhe ZhangSchool of Mathematics, Georgia Tech
This talk will follow Peter Lax on the linear algebraic fact of the index of Fredholm operators such as the product formula and stability, all of which are totally elementary.

Pages