Monday, November 16, 2009
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
Lecture - 14:15
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
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.