Greg’s Dinosaurs Riddle

The two-riddles post was a success, and while corresponding with Greg Kuperberg he had a riddle for me about dinosaurs, and he agreed I will share it with you.

Right before the Chixculub asteroid hit the earth, there were a variety of mammals and a wide variety of dinosaurs.  Both the mammals and the dinosaurs lived in many places, came in many sizes, etc.  Why did some of the mammals survive, but none of the dinosaurs did?

A nuch simpler question: Can you answer (without clicking or googeling or so):

How many years did the dinosaurs live? (you know,.. not a single one but them as a whole…) 1 million years, 5 millions, 20 millions, 50 millions, 100 millions?

And a deep philosophical question:

The dinosaurs perished. Should we regard them as losers??? 


A Diameter Problem (6): Abstract Objective Functions

Dantzig and Khachyan

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 these directed graphs are the directed graphs of polytopes where the direction of the edges is described by a linear objective function.  

7. Linear programming and the simplex algorithm.

Our diameter problem for families of sets was based on a mathematical abstraction (and a generalization) of the Hirsch Conjecture which asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Hirsch, in fact, made the conjecture also for graphs of unbounded polyhedra – namely the intersection of n closed halfspaces in R^d. But in the unbounded case, Klee and Walkup found a counterexample with diameter n-d+ [d/5]. The abstract problem we considered extends also to the unbounded case and  n-d+ [d/5] is the best known lower bound for the abstract case as well. It is not known if there is a polynomial (in terms of d and n) upper bound for the diameter of graphs of d-polytopes with n facets.

Hirsch’s conjecture was motivated by the simplex algorithm for linear programming.  Let us talk a little more about it: Linear programming is the problem of maximizing a linear objective function \phi(x)=b_1x_1+ b_2 x_2 \dots +b_dx_d subject to a system of n linear inequalities in the variables x_1,x_2,\dots,x_d.

 a_{11}x_1 + x_{12}x_2 + \dots + x_{1d}x_d \le c_1,

a_{21}x_1 + x_{22}x_2 + \dots + x_{2d}x_d \le c_2,

a_{n1}x_1 + x_{n2}x_2 + \dots + x_{nd}x_d \le c_n,

The set of solutions to the system of inequalities is a convex polyhedron. (If it is bounded it is a polytope.)  A linear objective function makes a graph of a polytope (or a polyhedron) into a digraph (directed graph). If you like graphs you would love digraphs, and if you like graphs of polytopes, you would like the digraphs associated with them.  

The geometric description of Dantzig’s simplex algorithm is as follows: the system of inequalities describes a convex d-dimensional polyhedron P. (This polyhedron is called the feasible polyhedron.) The maximum of \phi is attained at a face F of P. We start with an initial vertex (extreme point) v of the polyhedron and look at its neighbors in G(P). Unless v \in F there is a neighbor u of v that satisfies \phi(u) > \phi (v). When you find such a vertex move from v to u and repeat!

8. Abstract objective functions and unique sink orientation.

Let P be a simple d-polytope and let \phi be a linear objective function which is not constant on any edge of the polytope. Remember, the graph of P, G(P) is a d-regular graph. We can now direct every edge u,v from u to v if \phi (v) > \phi (u). Here are two important properties of this digraph.

(AC) It is acyclic! (no cycles)

(US’) It has a unique SINK, namely a unique vertex such that all edges containing it are directed towards it.

The unique sink property is in fact the property that enables the simplex algorithm to work!

When we consider a face of the polytope F and its own graph G(F) then again our linear objective function induces an orientation of the edges of G(F) which is acyclic and also has the unique sink property. Every subgraph of an acyclic graph is acyclic. But having the unique sink property for a graph does not imply it for a subgraph. We can now describe the general unique sink properties of digraphs of polytopes:

(US) For every face F of the polytope, the directed graph induced on the vertices of F has a unique sink.

A unique sink acyclic orientation of the graph of a polytope is an orientation of the edges of the graph which satisfies properties (AC) and (US). 

An abstract objective function of a d-polytope is an ordering < of the vertices of the polytope such that the directed graph obtained by directing an edge from u to v if  u<v is a unique sink acyclic orientation. (Of course, coming from an ordering the orientation is automatically acyclic.) 

Continue reading