Georgia Institute of Technology College of Sciences

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties: - its edge expansion is at least c/log n; - its diameter is O(log n); - its vertex expansion is at least c/log n; - it has a linearly long path; - its mixing time is O(log^2n) All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).

The problem of extending results in extremal combinatorics to sparse random and pseudorandom structures has attracted the attention of many researchers in the last decades. The breakthroughs due to several groups in the last few years have led to a better understanding of the subject, however, many questions remain unsolved. After a short introduction into this field we shall focus on some results in extremal (hyper)graph theory and additive combinatorics. Along the way some open problems will be given.

The Erdos-Szekeres (happy ending) theorem claims that among any N points in general position in the plane there are at least log_4(n) of them that are the vertices of a convex polygon. I will explain generalizations of this result that were discovered in the last 30 years involving pseudoline arrangements and families of convex bodies. After surveying some previous work I will present the following results: 1) We improve the upper bound of the analogue Ramsey function for families of disjoint and noncrossing convex bodies. In fact this follows as a corollary of the equivalence between a conjecture of Goodman and Pollack about psudoline arrangements and a conjecture of Bisztrinsky and Fejes Toth about families of disjoint convex bodies. I will say a few words about how we show this equivalence. 2) We confirm a conjecture of Pach and Toth that generalizes the previous result. More precisely we give suffcient and necesary conditions for the existence of the analogue Ramsey function in the more general case in which each pair of bodies share less than k common tangents (for every fixed k). These results are joint work with Andreas Holmsen and Michael Dobbins.

A well-known problem in geometry, which may be traced back to the Renaissance artist Albrecht Durer, is concerned with cutting a convex polyhedral surface along some spanning tree of its edges so that it may be isometrically embedded, or developed without overlaps, into the plane. We show that this is always possible after an affine transformation of the surface. In particular, unfoldability of a convex polyhedron does not depend on its combinatorial structure, which settles a problem of Croft, Falconer, and Guy. Among other techniques, the proof employs a topological characterization for embeddings among immersed planar disks.