Category Archives: Convex polytopes

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture A convex polytope is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have … Continue reading

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

The Polynomial Hirsch Conjecture: A proposal for Polymath3

This post is continued here.  Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d. We devoted several … Continue reading

Posted in Open problems, Convex polytopes, Open discussion | Tagged , , , | 38 Comments

(Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Richard Stanley This post is authored by Eran Nevo. (It is the second in a series of five posts.) The g-conjecture: the commutative algebra connection Let be a triangulation of a -dimensional sphere. Stanley’s idea was to associate with a ring … Continue reading

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

How the g-Conjecture Came About

This post complements Eran Nevo’s first  post on the -conjecture 1) Euler’s theorem Euler Euler’s famous formula for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close … Continue reading

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

(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.) Peter McMullen The g-conjecture What are the possible face numbers of triangulations of spheres? There is only one zero-dimensional sphere and it consists … Continue reading

Posted in Combinatorics, Convex polytopes, Guest blogger, Open problems | Tagged , , | 5 Comments

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 , , | 4 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