# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, November 16, 2009

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin

Lecture - 14:15

### Matrices of Generalized Inversion Numbers

Abstract:
For a finite reflection group $W$ and a conjugacy class $O$ of parabolic subgroups we study a $(|W| \times |W|)$-matrix $M_O$, whose entries in some sense generalize inversion numbers of permutations from the case $W = S_n$. An easily described, albeit hard and interesting, case is the following. Let $W = S_n$ and for a suitable choice of $O$ one obtains for any $1 \leq k \leq n$ the matrix $M_O = M_{n,k}$ with rows and columns indexed by permutations, where the entry in row $\pi$ and column $\tau$ is the number of sequences $(i_1, \ldots, i_k)$ of pairwise different integers in $\{1, \ldots, n\}$ such that $\sigma \pi^{-1}$ sorts the sequence (i.e., $\sigma \pi^{-1} (i_1) < \cdots < \sigma \pi^{-1}(i_k)$). We show that the $M_{n,k}$ commute, derive enumerative consequences, conjecture that they have integer spectrum, derive enumerative consequences and present general results on the matrices $M_O$. This is joint work with Vic Reiner and Franco Saliola.

Colloquium - 16:00

### Vertex Enumeration via Linear Programming?

Abstract:
Given a polytope in $\Real^d$ described by its facet-defining halfspaces, computing the vertices efficiently is a fundamental problem in algorithmic polytope theory. In this talk I will present some similarities between this problem (Vertex Enumeration) and a few other problems. I will outline a possible approach to solve the Vertex Enumeration problem via Linear Programming, and the present difficulties in such an approach.

Letzte Aktualisierung: 09.11.2009