Georgia Institute of Technology College of Sciences

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.

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.

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.

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