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, July 6, 2009

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041

Lecture - 14:15

Vic Reiner - Minneapolis

The diameter question for galleries in hyperplane arrangements

(joint work with Y. Roichman)

An arrangement of linear hyperplanes in R^n dissects space into connected components called chambers. There is a natural connected graph structure on the set of all walks from one particular chamber to its antipodal chamber that cross each hyperplane exactly once (or equivalently, on the monotone paths in the 1-skeleton of the associated zonotope).

In this talk, we will define this graph, and discuss how little is known currently about its diameter. There is an obvious lower bound for the diameter, which we show is tight for certain classes of hyperplane arrangements (those which are _supersolvable_). We have no idea whether or not this lower bound is tight in general-- this is a question ripe for further exploration.

Colloquium - 16:00

Assaf Naor - New York

Towards a calculus for non-linear spectral gaps.

The spectral gap of a symmetric stochastic matrix is the reciprocal of the best constant in its associated Poincare inequality. This inequality can be formulated in purely metric terms, where the metric is a Hilbertian metric. This immediately allows one to define the spectral gap of a matrix with respect to other, non-Euclidean, geometries: a standard procedure which is used a lot in embedding theory, most strikingly as a method to prove non-embeddability in the coarse category. Motivated by a combinatorial approach to the construction of bounded degree graph families which do not admit a coarse embedding into any uniformly convex normed space (such spaces were first constructed by Lafforgue), we will naturally arrive at questions related to the behavior of non-linear spectral gaps under graph operations such as powering and zig-zag products. We will also discuss the issue of constructing base graphs for these iterative constructions, which leads to new analytic and geometric challenges.
Joint work with Manor Mendel

Letzte Aktualisierung: 30.06.2009