Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 7, 2010

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

Lecture - 14:15

Anders Björner, KTH Stockholm

A q-analogue of the FKG inequality and some applications

The FKG inequality of Fortuin, Kasteleyn and Ginibre (1971) originated as a correlation inequality in statistical mechanics. It has many applications in discrete probability and extremal combinatorics.

In this talk we present a polynomial coefficient-wise inequality that refines the original FKG inequality. This polynomial FKG inequality has applications to $f$-vectors of joins of simplicial complexes, to Betti numbers of intersection of Schubert varieties, and to power series weighted by Young tableaux. The latter case includes a correlation inequality for the poissonization of Plancherel measure on symmetric groups, a probability measure on the set of all integer partitions.
The talk will be quite elementary and no previous familiarity with these topics will be assumed.

Colloquium - 16:00

Yuri Rabinovich, Haifa


We introduce and study finite volumes, the high dimensional generalization of finite metrics. Notions, concepts and methods of the theory of finite metric spaces often extend to finite volume spaces, leading to new intriguing problems, as well as to new perspectives in the theory of simplicial complices. For example, introducing the class of L_1 volumes (an analogue of L_1 metrics), and studying how well can they approximate an arbitrary volume function, we naturally arrive at the notion of expansion of a simplicial complex. High dimensional analogues of network flows, graph spanners and spectral gaps also arrise rather naturally in this contex. We shall discuss these notions, and present some related results.

A separate issue is the dimension reduction for L_1 metrics and volumes. We introduce new tools (related to the sparsification techniques of Karger et al., and Spielman et al.), and show that there is indeed a dimension reduction phenomenon for L_1 volumes, although not to the same striking degree as in the Euclidean case. For L_1 metrics we show a linear upper bound on number of dimensions, improving the previously best known O(n log n) bound due to Schechtman.

Based on a joint work with Ilan Newman.

Letzte Aktualisierung: 25.05.2010