Category Archives: Convex polytopes

(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 , , , , | 8 Comments

How the g-Conjecture Came About

Update: Slides from a great 2014 lecture on the g-conjecture by Lou Billera in the conference celebrating Richard Stanley’s 70th birthday. This post complements Eran Nevo’s first  post on the -conjecture 1) Euler’s theorem Euler Euler’s famous formula for the … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , , , | 9 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 , , | 10 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 , , , | 8 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 , , | 6 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