UW Combinatorics Talk

UW Combinatorics Seminar

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

Sara Billey, Combinatorics Seminar, Mathematics Department, University of Washington,

Page loaded on September 07, 2012 at 01:00 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.