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

A Diameter Problem (5)

6. First subexponential bounds. 

Proposition 1: F(d,n) \le F_k(d,n) \times F(d-k,n-k).

How to prove it: This is easy to prove: Given two sets S and T in our family \cal F, we first find a path of the form S=S_0, S_1, S_2, \dots, S_t = T where, |S_{i-1} \cap S_i| \ge k and t \le F_k(d,n). We let B_i \subset (S_{i-1} \cap S_i ) with |B_i|=k and consider the family {\cal F}'[B_i]. This is a family of (d-k)-subsets of an (n-k) set (N \backslash B_i) . It follows that we can have a path from S_{i-1} to S_i in  G({\cal F}[B_i]) of length at most F(d-k,n-k). Putting all these paths together gives us the required result. (We remind the notations at the end of this post.)

How to use it: It is not obvious how to use Proposition 1. Barnette’s argument from part 3 was about k=1, and it used something a bit more sophisticated. Applying Proposition 1 directly for k=1 does not give anything non trivial. However, when n is small compared to d and k is a small fraction of d we can say something.

Let us start with an example: n = 3d. let us choose k= d/4. Consider a path S=S_0,S_1,\dots S_t=T in G({\cal F}) from two sets S and T. Suppose also that in this path 

(*) S_i \cap T \subset S_{i+1}\cap T, for every i

Let U_1 be the last set in the path whose intersection with S has at least d/4 elements.  Let U_2 be the last set in the path whose intersection with U_1 has at least d/4 elements. I claim that S, U_1, U_2, T is a path in G_{d/4}({\cal F}).

To see this Continue reading

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 \cal F of subsets of size d of the set N= \{ 1,2,\dots, n \}.

Let us now associate  more general graphs to \cal F as follows: For an integer k 1 \le k \le d define G_k({\cal F}) as follows: The vertices of  G_k({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T| \ge k. Our original problem dealt with the case k=d-1.  Thus, G({\cal F}) = G_{d-1}({\cal F}). Barnette proof presented in the previous part refers to G_1({\cal F}) and to paths in this graph.  

As before for a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A. Of course, the smaller k is the more edges you have in G_k({\cal F}). It is easy to see that assuming that G_1({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty already implies our condition that G({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty.

Let F_k(d,n) be the maximum diameter of G_k({\cal F})  in terms of k,d and n, for all families \cal F of d-subsets  of N satisfying our connectivity relations.

Here is a simple claim:

F(d,n) \le F_k(d,n) \times F(d-k,n-k).

Can you prove it? Can you use it? 

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 to the diameter of graphs of simple d-polytopes.

All the methods I am aware of for providing upper bounds are fairly simple.

(1) You think about a strategy from moving from one set to another, 

(2) You use this strategy to get a recursive bound,

(3) You solve the recursion and hope for the best.

What I would like you to think about, along with reading these posts, is the following questions:

(a) Can I come up with a different/better strategy for moving from one set to the other?

(b) Can I think about a mathematically more sophisticated way to get an upper bound for the diameter?

(c) Can this process of finding a strategy/writing the associated recurrence/solving the recurrence be automatized? The type of proofs we will describe are very simple and this looks like a nice example for a “quasi-automatic” proof process.

Let me repeat the problem and prove to you a nice upper bound:

Reminder: Our Diameter problem for families of sets

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Associate to \cal F a graph G({\cal F}) as follows: The vertices of  G({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T|=d-1.

Continue reading

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 n is known. Finding good upper bounds for the diameter of graphs of d-polytopes is one of the central open problems in the study of convex polytopes. If d is fixed then a linear bound in n is known, and the best bound in terms of d and n is n^{\log d+1}. We will come back to these results later.

One basic fact to remember is that for every d-polytope P, G(P) is a connected graph. As a matter of fact, a theorem of Balinski asserts that G(P)$ is d-connected.

The combinatorial diameter problem I mentioned in an earlier post (and which is repeated below) is closely related. Let me now explain the connection. 

Let P be a simple d-polytope. Suppose that P is determined by n inequalities, and that each inequality describes a facet of P. Now we can define a family \cal F of subsets of {1,2,…,n} as follows. Let E_1,E_2,\dots,E_n be the n inequalities defining the polytope P, and let F_1,F_2,\dots, F_n be the n corresponding facets. Every vertex v of P belongs to precisely d facets (this is equivalent to P being a simple polytope). Let S_v be the indices of the facets containing v, or, equivalently, the indices of the inequalities which are satisfied as equalities at v. Now, let \cal F be the family of all sets S_v for all vertices of the polytope P.

The following observations are easy.  

(1) Two vertices v and w of P are adjacent in the graph of P if and only if |S_v \cap S_w|=d-1. Therefore, G(P)=G({\cal F}).

(2)  If A is a set of indices. The vertices v of P such that A \subset S_v are precisely the set of vertices of a lower dimensional face of P. This face is described by all the vertices of P which satisfies all the inequalities indexed by i \in A, or equivalently all vertices in P which belong to the intersection of the facets F_i for i \in A.

Therefore, for every A \subset N if {\cal F}[A] is not empty the graph G({\cal F}[A]) is connected – this graph is just the graph of some lower dimensional polytope. This was the main assumption in our abstract problem.

Remark: It is known that the assertion of the Hirsch Conjecture fails for the abstract setting. There are examples of families where the diameter is as large as n-(4/5)d.

1. A Diameter problem for families of sets

Let me draw your attention to the following problem:

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Continue reading

A Diamater Problem for Families of Sets.

Let me draw your attention to the following problem:

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Associate to \cal F a graph G({\cal F}) as follows: The vertices of  G({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T|=d-1.

For a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A

MAIN ASSUMPTION: Suppose that for every A for which {\cal F}[A] is not empty G({\cal F}[A]) is connected.

MAIN QUESTION:   How large can the diameter of G({\cal F}) be in terms of d and n.

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 asserts that for a 3-polytope P

V-E+F=2.  

The extension to d-dimensions asserts that for every d-polytope

The Euler Relation: f_0(P) - f_1(P) +F_2(P) + \dots + (-1)^d f_{d-1}(P) = 1 - (-1)^d.

There were several incomplete proofs of Euler’s theorem in the late 19th century, but the first complete proof came via Poincare’s work in algebraic topology and the Euler-Poincare theorem. Later, simple geometric proofs were found and the gap in certain 19th theory proofs which relied on an unproved assumption of shellability was completed when Bruggesser and Mani proved in 1970 that the boundary of every d-polytope is shellable.

 

2. Fibonacci

 Fibonacci sunflower

Let’s move now to flag numbers. Consider a d-polytopes P. for a set S \subset {-1,0,1,2,…,d-1,d}, S={ i_1,i_2,\dots,i_k} , i_1<i_2< \dots, define the flag number f_S as the number of chains of faces F_1 \subset F_2 \subset \dots F_k, where \dim F_j=i_j.  We will assume from now on that S contains both ‘-1′, and ‘d’. (Adding or deleting these entries from S does not change the value of the flag number.) Let c_d be the dth Fibonacci number. (c_1=1, c_2=2, c_3=3, c_4=5, etc.)  Bayer and Billera proved:

Theorem: the affine dimension of flag numbers of d-polytopes is c_d-1

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: f_{01}=2f_1. This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: f_{02}=f_{12}. This follows from the fact that a polygon has the same number of vertices as edges which is Euler’s formula for d=2. Here are two, more complicated, examples: f_{1569}=f_{1469}-f_{1369}+f_{1269} and f_{1679}=f_{1579}-f_{1479}+f_{1379}-f_{1279}+2f_{179}. Let’s understand the first of the two: Fix a flag of faces Continue reading

Billerafest

Lou Billera
I am unable to attend the conference taking place now at Cornell, but I send my warmest greetings to Lou from Jerusalem. The titles and abstracts of the lectures can be found here. Let me tell you about two theorems by Lou.
 
The first is the famous g-theorem: The g-theorem is a complete description of f-vectors (= vecors of face numbers) of simplicial d-polytopes. This characterization was proposed by Peter McMullen in 1970, and it was settled in two works. Billera and Carl Lee proved the sufficiency part of McMullen’s conjecture, namely for every sequence of numbers which satisfies McMullen’c conjecture they constructed a simplicial d-polytope P whose f-vector is the given sequence. Richard Stanley proved the necessity part based on the hard Lefschetz theorem in algebraic geometry. The assertion of the g-conjecture (the necessity part) for triangulations of spheres is open, and this is probably the one single problem I spent the most time on trying to solve. 
 
The second theorem is a beautiful theorem by Margaret Bayer and Billera. Consider general d-polytopes. for a set S \subset {0,1,2,…,d-1}, S={ i_1,i_2,\dots,i_k} , i_1<i_2< \dots, define the flag number f_S as the number of chains of faces F_1 \subset F_2 \subset \dots F_k, where \dim F_j=i_j.  Bayer and Billera proved that the affine dimension of flag numbers of d-polytopes is c_d-1 where c_d is the dth Fibonacci number. (c_1=1, c_2=2, c_3=3, c_4=5, etc.) The harder part of this theorem was to construct c_d d-polytopes whose sequences of flag numbers are affinely independent.  The construction is simple: It is based on polytopes expressed by words of the form PBBPBPBBBPBP  where you start with a point, and P stands for “take a pyramid” and B stands for “take a bipyramid.” And the word starts with a P (to the left) and has no two consecutive B’s.
 
Let’s practice the notions of f-vectors and flag vectors on the 24-cell   . (The figure is a 3-dimensional projection into one of the facets of the polytope.)
 
 
 
This  4-polytope has 24 octahedral facets. It is self dual.
So f_0=f_3=24. And f_1=f_2=96. And f_{02}=288, f_{03}=192, etc. 

Five Open Problems Regarding Convex Polytopes

  

The problems 

1. The 3^d conjecture

A centrally symmetric d-polytope has at least 3^d non empty faces.

2. The cube-simplex conjecture

For every k there is f(k) so that every d-polytope with d \ge f(k) has a k-dimensional face which is either a simplex or combinatorially isomorphic to a k-dimsnional cube.

3. Barany’s question

For every d-dimensional polytope P and every k, 0 \le k \le d-1,  is it true that f_k(P) \ge \min (f_0(P),f_{d-1}(P))?

(In words: the number of k-dimensional faces of P is at least the minimum between the number of vertices of P and the number of facets of P. )

4.  Fat 4-polytopes

For 4-polytopes P, is the quantity (f_1(P)+f_2(P))/(f_0(P)+f_3(P)) bounded from above by some absolute constant? 

5.  five-simplicial five-simple polytopes

Are there 5-simplicial 5-simple 10-polytopes? Or at least 5-simplicial 5-simple d-polytope for some d?

(A polytope P is k-simplicial if all its faces of dimension at most k, are simplices. A polytope P is k-simple if its dual P* is k-simplicial.)

And on a personal note: My beloved, beautiful,  and troubled country celebrates 60 today: happy birthday! 

Update (May 12): David Eppstein raised in a followup a sort of a dual question to Barany’s. For a d-polytope with n vertices and n facets what is the maximal number of k-faces. For a fixed d and large n the free join of pentagons is conjectured to give asymptotically the best upper bound.

Update (July 29) Gunter Ziegler reminded me of the following additional problem of Barany: Is the number of saturated chains in a d-polytope bounded by some constant (depending on d) times the total number of faces (of all dimensions) of the polytope. A saturated flag is a 0-face inside a 1-face inside a 2-face … inside a (d-1)-face. 

Continue reading