Recent progress on the diameter of simplicial complexes and polyhedra

Datum

27.11.2013

Zeit

17:00 - 18:00

Sprecher

Prof. Dr. Francisco Santos

Zugehörigkeit

Universidad de Cantabria

Serie

TUD Dresdner Mathematisches Seminar

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Prof. Dr. U. Brehm

Beschreibung

The Hirsch conjecture, posed in 1957, stated that the graph of a $d$-dimensional polytope or polyhedron with $n$ facets could not have diameter greater than $n - d$. The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25% is known. In this talk we review several recent attempts and progress on the question. Some of them work in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we show that the maximum diameter of arbitrary simplicial complexes is in $n^{Theta(d)}$ and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e. g., simplicial manifolds).

Links

• Dresdner Mathematisches Seminar

Letztmalig verändert: 19.11.2013, 14:14:39