# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, December 4, 2017

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

### On (discrete) Brunn-Minkowski type inequalities

Abstract:
Relating the volume with the Minkowski (vectorial) addition of compact (not necessarily convex) sets, one is led to the famous and powerful Brunn-Minkowski inequality. One form of it states that $\vol(K+L)^{1/n}\geq\vol(K)^{1/n}+\vol(L)^{1/n}$ for any compact sets $K,L\subset\R^n$. In 2001, Gardner \& Gronchi moved it to the discrete setting and proved a discrete version of the Brunn-Minkowski inequality for finite subsets of the integer lattice $\Z^n$: if $A,B\subset\Z^n$ are finite with $\dim B=n$, then the cardinality $|A+B|\geq \bigl|D_{|A|}^B+D_{|B|}^B\bigr|$, where $D_{|A|}^B$ is, roughly speaking, like an intersection of a simplex with $\Z^n$. In this talk we aim also to present a new type of discrete Brunn-Minkowski inequality: if $A,B\subset\Z^n$ are finite, then
$\bigl|\bar{A}+B\bigr|^{1/n}\geq |A|^{1/n}+|B|^{1/n},$
where $\bar{A}$ is an {\it extension} of $A$ which is obtained by adding some new integer points in a particular way.

Joint work with Jesús Yepes Nicolás and David Iglesias.

* * *

Colloquium - 16:00

### Polyhedral Approximations to Nonnegative Polynomials

Abstract:
Can we approximate a semidefinite program by a linear program? Is it possible to approximately check nonnegativity of a multivariate polynomial by few pointwise evaluations? These questions fall into general framework of approximating the cone of nonnegative polynomials with polyhedral cones.

In this talk, we will show inapproximability of the cone of nonnegative polynomials in the dense case (i.e. the case of all polynomials of a fixed degree). We will also show the existence of polyhedral approximations with polynomial number of facets in the sparse case (i.e. the case of a subspace of polynomials with small dimension). Our approximation result is an application of the recent solution of Kadison-Singer problem, and hence it is not constructive. Time permits, we will also discuss randomized construction of a polyhedral approximation in the sparse case.

Letzte Aktualisierung: 15.12.2017