UW Combinatorics Talk
Title: Decomposability of polytopes and the polynomial
Hirsch conjecture
Steve Klee
Seattle University
October 24, 4:00pm
Padelford C-401
refreshments at 3:30pm
Pre-Seminar at 2:30pm in Padelford C-401
ABSTRACT
|
|
The Hirsch conjecture for polytopes
proposed that if P is
a d-dimensional polytope defined by n hyperplane
inequalities,
then any two vertices in P can be joined by a path of length at
most
n-d in the graph of P. The Hirsch conjecture was originally
proposed in 1957 and was only recently disproved by Santos in 2010
with a counterexample of dimension 43 defined by 86 hyperplane
inequalities.
Dually, one can work in the polar setting and consider a d-polytope
P with n vertices and consider the maximum length of a path
between two facets of P in which one moves from one facet to
another
by crossing a codimension-one face. This maximal distance is called
the diameter of P, and it is sufficient to study simplicial
polytopes on n vertices (i.e.; polytopes in which each face is a
simplex of some dimension) when trying to bound the diameter of an
arbitrary polytope on n vertices.
Despite Santos's recent counterexample to the Hirsch conjecture, it is
still unknown whether the diameter of a polytope can be bounded by a
polynomial function of its number of vertices and dimension. In 1980,
Provan and Billera defined notions of k-decomposability for
simplicial complexes and proved that the diameter of a
k-decomposable complex can be bounded by a polynomial function of
degree k in its number of vertices and dimension. As such, it
would
be interesting to know if there is some k for which any simplicial
d-polytope is k-decomposable.
In this talk, we will review the current state of the Hirsch
conjecture and define the Provan-Billera notions of decomposability.
We will then introduce a certain family of very natural polytopes
called transportation polytopes and show that there are families of
transportation polytopes that prevent the Provan-Billera
decomposability approach from providing polynomial bounds on the
diameter of simplicial polytopes. This talk represents joint with
with Jesus De Loera, Nicolai Hahnle, and Vincent Pilaud.
|
Speaker's Contact Info:
http://www.math.ucdavis.edu/~klee/
Return to seminar home page
|
Page loaded on September 07, 2012 at 01:00 PM.
|
Copyright © 1998-99, Sara C. Billey.
All rights reserved.
|
|