Oberseminar

For graphs there exists a strong connection between spectral expansion and edge expansion. This is expressed, e.g., by the Cheeger inequality, which states that $\lambda(G) \leq h(G)$, where $\lambda(G)$ is the second smallest eigenvalue of the Laplacian of $G$ and $h(G)$ the Cheeger constant measuring the edge expansion of $G$. We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension. Whereas for simplicial complexes, higher dimensional Laplacians were introduced already in 1945 by Eckmann, the generalization of edge expansion is not straightforward. Recently, a topologically motivated notion analogous to edge expansion was introduced by Gromov and independently by Linial, Meshulam and Wallach and by Newman and Rabinovich. It is known that for this generalization there is no higher dimensional analogue of the lower bound of the Cheeger inequality. A different, combinatorially motivated generalization of the Cheeger constant, denoted by $h(X),$ was studied by Parzanchevski, Rosenthal and Tessler. They showed that indeed $\lambda(X) \leq h(X)$, where $\lambda(X)$ is the smallest non-trivial eigenvalue of the Laplacian, for the case of $k$-dimensional simplicial complexes $X$ with complete $(k-1)$-skeleton. Whether this inequality also holds for k-dimensional complexes with non-complete $(k-1)$-skeleton has been an open question. We give two different strengthenings of the inequality for arbitrary complexes.

The Upper Bound Theorem, conjectured by Motzkin and proved by McMullen, is one of the cornerstones of discrete geometry: Neighborly simplicial polytopes maximize the number of k-dimensional faces among all d-dimensional convex polytopes with a fixed number of vertices. Stanley vastly generalized the Upper Bound Theorem by showing that it even holds for general triangulations of spheres (and beyond). In this talk I will present a generalization of Stanley’s approach that yields an algebraic framework for treating relative upper bound problems. As showcases I will present solutions to combinatorial isometric problems and an Upper Bound Theorem for Minkowski sums. The talk will be a scenic tour from geometry to algebra and back. This is joint work with Karim Adiprasito (IHES).

We completely characterize sections of the cones of nonnegative polynomials, convex polynomials and sums of squares with polynomials supported on circuits – a genuine class of sparse polynomials. In particular, nonnegativity is characterized by an invariant, which can be immediately derived from the initial polynomial. Based on these results, we obtain a completely new class of nonnegativity certificates independent from sums of squares certificates. Furthermore, nonnegativity of such polynomials f coincides with solidness of the amoeba of f, i.e., the Log-absolute-value image of the variety of f. To the best of our knowledge this is the first connection established between amoeba theory and nonnegativity of polynomials. These results generalize earlier works both in amoeba theory and real algebraic geometry by Fidalgo, Kovacec, Reznick, Theobald and myself. This talk is based on work in progress joint with Sadik Iliman.

The Johnson-Lindenstrauss lemma says that one can embed a set of n points in a (high dimensional) Euclidean space into an m-dimensional space using a random map, while approximately preserving the distances between the points in the set. Surprisingly, the embedding dimension m does not depend on the original dimension of the data: it scales logarithmically in terms of the number of points. This result has found many applications, e.g. in nearest-neighbor search. In my talk I will present a generalization of the Johnson-Lindenstrauss lemma, which allows one to embed arbitrary data sets (i.e. also of infinite cardinality) in a low-dimensional space using a random map. The result unifies (and improves) several dimensionality reduction results for specific data sets in the literature, such as sets of sparse vectors, low rank matrices and smooth manifolds.