- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

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.

Wednesday, March 4, 2009 - 11:00 ,
Location: Skiles 255 ,
Sean Ellermeyer ,
Kennesaw State University ,
Organizer:

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.

Series: PDE Seminar

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.

Series: Algebra Seminar

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.

Series: Geometry Topology Seminar

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.

Friday, February 27, 2009 - 15:05 ,
Location: Skiles 269 ,
Igor Belegradek ,
Ga Tech ,
Organizer: John Etnyre

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.

Series: Other Talks

Series: Probability Working Seminar

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.

Series: Combinatorics Seminar

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.)

Series: SIAM Student Seminar

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.