Category Archives: Convex polytopes

Ziegler´s Lecture on the Associahedron

  The associahedron in 3 dimension, and James Stasheff. This picture is taken from Bill Casselman’s article on the associahedron. The article is entitled “Strange Associations” and starts with “There are many other polytopes that can be described in purely combinatorial terms. Among the … Continue reading

Posted in Convex polytopes | Tagged , , , | 7 Comments

Telling a Simple Polytope From its Graph

Peter Mani  (a photograph by Emo Welzl) Simple polytopes, puzzles   Micha A. Perles conjectured in the ’70s that the graph of a simple -polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind … Continue reading

Posted in Convex polytopes, Open problems | Tagged , , | 5 Comments

A Diameter problem (7): The Best Known Bound

  Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of  are simply the sets in . Two vertices and are adjacent if . … Continue reading

Posted in Combinatorics, Convex polytopes | Tagged , | 1 Comment

A Diameter Problem (6): Abstract Objective Functions

George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , | 7 Comments

A Diameter Problem (5)

6. First subexponential bounds.  Proposition 1: How to prove it: This is easy to prove: Given two sets and in our family , we first find a path of the form where, and . We let with and consider the family … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | Tagged | 1 Comment

Diameter Problem (4)

Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets. Recall that we consider a family of subsets of size  of the set . Let us now associate  … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | Tagged | 1 Comment

Diameter Problem (3)

3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , | 1 Comment

A Diameter Problem (2)

2. The connection with Hirsch’s Conjecture The Hirsch Conjecture asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Not even a polynomial upper bound for the diameter in terms of d and … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | 5 Comments

A Diamater Problem for Families of Sets.

Let me draw your attention to the following problem: Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of  are simply the sets in . Two vertices and are adjacent … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | 10 Comments

Euler’s Formula, Fibonacci, the Bayer-Billera Theorem, and Fine’s CD-index

  Bill Gessley proving Euler’s formula (at UMKC)   In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it. 1. Euler Euler’s theorem … Continue reading

Posted in Combinatorics, Convex polytopes | Tagged , , | 4 Comments