2018 May 23

Colloquium: Janos Pach (EPFL Lausanne, IIAS and Renyi Institute Budapest) - "The Crossing Lemma"

4:15pm to 5:15pm


Manchester Building (Hall 2), Hebrew University Jerusalem
The Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi (1982) and Leighton (1983 )states that if a graph of n vertices and e>4n edges is drawn in the plane, then the number of crossings between its edges must be at least constant times e^3/n^2. This statement, which is asymptotically tight, has found many applications in combinatorial geometry and in additive combinatorics. However, most results that were obtained using the Crossing Lemma do not appear to be optimal, and there is a quest for improved versions of the lemma for graphs satisfying certain special properties.
2018 May 02

Analysis Seminar: Bo'az Klartag "Convex geometry and waist inequalities"

12:00pm to 1:00pm


room 70, Ross Building
Abstract: We will discuss connections between Gromov's work on isoperimetry of waists and Milman's work on the M-ellipsoid of a convex body. It is proven that any convex body K in an n-dimensional Euclidean space has a linear image K_1 of volume one satisfying the following waist inequality: Any continuous map f from K_1 to R^d has a fiber f^{-1}(t) whose (n-d)-dimensional volume is at least c^{n-d}, where c > 0 is a universal constant. Already in the case where f is linear, this constitutes a slight improvement over known results.