# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, December 18, 2017

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

Lecture - 14:15

### An invariant effective description of compact non-convex polyhedra

Abstract:
It is often assumed that the only way to represent a (compact) non-convex polyhedron $X\subset \RR^d$ is by partitioning into convex polytopal pieces. Such partitions are very far from being unique or succinct; in particular in dimensions $d>2$ one might need to introduce {\sl Steiner points}---points in the inerior of $X$ which must arise as vertices of polytopal pieces.

We propose a description that is essentially unique: a rational function associated with the uniform measure $\mu(X)$ supported on $X$. It is given by an integral transform of $\mu(X)$ known as {\sl Fantappi\e transformation} $${\cal F}(\mu(X))(u):= d!\int_{\RR^{d}} {d\mu(X)(x)\over (1-\la u,x\ra)^{d+1}}={P(u)\over \prod_{v\in V}(1-\la u,v\ra)},$$ where $\la x,y\ra$ denotes the standard scalar product $\sum_i x_i y_i$. Expanding ${\cal F}$ into Taylor series gives a scaled moment generating function (m.g.f.) for $\mu(X)$, known in the univariate case as factorial m.g.f., and this allows for efficient computation of integrals over $X$, etc.

${\cal F}$ admits decompositions into `elementary'' summands with real weights, corresponding to certain simplices with vertices from $V$, which are analogous to triangulations of convex polytopes. In particular they allow an efficient way to check containment of a point in $X$. It is an interesting open question whether these weights can be chosen to be $\pm 1$.

It is natural to homogenise ${\cal F}$, an operation that corresponds to switching to the Laplace-Fourier transform of a measure supported on the conic closure of $X$ embedded into the hyperplane $\{x_0=1\}\subset\RR^{d+1}$. It allows to apply powerful machinery of Jeffrey-Kirwan residues by Brion and Vergne, used in the theory of hyperplane arrangements.

joint work with N. Gravin, B. Shapiro and M. Shapiro

* * *

Colloquium - 16:00

### On the Banach-Mazur Distance between the Cube and the Crosspolytope

Abstract:
In this note we study the Banach-Mazur distance between the n-dimensional cube and the crosspolytope. Previous work shows that the distance has order $\sqrt{n}$ , and here we will prove some explicit bounds improving on former results. Even in dimension 3 the exact distance is not known, and based on computational results it is conjectured to be $\frac{9}{5}$. Here we will also present computerbased potential optimal results in dimension 4 to 8.

Letzte Aktualisierung: 15.12.2017