Motivating Clique Replacements
We begin by examining when a set of vectors has a linear dependence only using positive coefficients. I will call such a dependence a “cone dependence” (or “c-dep”, for short) since the condition is equivalent to the cone formed by the vectors containing an entire subspace.
| Vectors in the Plane |  |
Figure 1: Three vectors in the plane that form a cone dependence.
For the colored vectors, the dashed line represents the vector’s negative.
Consider the single c-dep above. It consists of three vectors in the plane. What freedom do we have to change the black vector without destroying the c-dep? As long as the black vector doesn’t move across the dashed line representing the negative of the red or the negative of the blue vector, the three vectors will still form a c-dep.
| Vectors in 3-Space |  |
For the colored vectors, the dashed line represents the vector’s negative.
Here the black vector is contained in the cone spanned by the negatives of the other three vectors, so the four vectors form a c-dep. We are free to move the black vector without destroying the c-dep as long as it doesn’t cross through any of the three cones spanned by the negatives of two of the other (colored) vectors. In other words, the black vector may be moved without destroying the c-dep as long as it doesn’t cross through the cone spanned by the negative of the blue and the negative of the red, or the cone spanned by the negative of the blue and the negative of the green, etc.
In the general case, given a c-dep of d-vectors you can move one vector without destroying the c-dep as long as you don’t cross through the cone spanned by the negatives of any (d-2) of the other vectors.
Let P be a polytope and let Q be its dual. We will be working with the Gale transform of the dual, i.e. the Gale transform of Q. For lack of a convenient term, I’ll use the abbreviation “GDD” to denote a Gale diagram of the dual of a polytope. Each vector in the GDD corresponds to a particular facet of the polytope. Given a set of vectors that represent a GDD, the face lattice of the corresponding polytope is completely determined by the set of c-deps.
Let P be a d-dimensional polytope with d+k facets. The GDD in this case will be a collection of d+k vectors in a (k-1)-dimensional “Gale space”. The minimal “cone dependences” in this case include k vectors and correspond to “co-vertices”. (A co-vertex is a list of all the facets not incident to a particular vertex. ) Consequently, there is a one-to-one correspondence between the vertices of the polytope and the minimal cone dependences in the GDD. Moreover, a vertex is incident to each facet whose associated vector is not included in the corresponding c-dep. For simple polytopes (i.e. d-dim polytopes for which every vertex is incident to d-facets), all c-deps require k vectors.
| Vectors on a Line | Their corresponding Polytope |
 |
 |
Now that we know how much freedom we have to move one vector of a GDD without changing any c-deps (and hence without change the combinatorics of the corresponding polytope), the question becomes what happens when we do cross one of these boundaries. Can we describe how the combinatorics change?
Let {v,w1, w2, … w k-2 , x} be the vectors of the first c-dep to be destroyed. Let v denote the vector to be moved, let C be the cone spanned by the negatives of {w1, w2, … w k-2 } and let H be the hyperplane spanned by {w1, w2, … w k-2 }. Suppose we move v until it crosses through C. Just before v crosses C, the cone spanned by the positives of v and {w1, w2, … w k-2 } approaches becoming the half-space bounded by H that contains x. Thus any vector xi on the same side of H as x must form a c-dep with {v,w1, w2, … w k-2 }. When v crosses H, all of these c-deps (which are of the form {v,w1, w2, … w k-2 , xi }) are destroyed but they are replaced by the c-deps of the form {v,w1, w2, … w k-2 , yj }) where {yj : j = 1 … n} are all the vectors on the opposite side of H as x.
Again, c-deps correspond to co-vertices of the polytope. For simple polytopes, a pair of co-vertices have (k-1) vectors in their intersection if and only if the corresponding pair of vertices are connected by an edge. Thus the vertices corresponding to the c-deps of the form {v,w1, w2, … w k-2 , xi } determine a clique in the edge graph of the polytope. By moving v across the hyperplane H, this clique is replaced by the clique determined by the c-deps of the form {v,w1, w2, … w k-2 , yj }. If a clique consisting of f vertices is replaced with one consisting of g vertices, we must have f + g = d + 1. This follows since there are (d+k) vectors total, the set {v,w1, w2, … w k-2 } has (k-1) vectors and all the remaining vectors are included in the set { x1, … xf , y1, … yg }.
Finally, I’d like to describe how the combinatorics of the polytope are changed by this “Clique Replacement”. This first diagram indicates a portion of the edge graph of an 8-polytope.
This particular clique replacement removes the six interior vertices and replaces them with three new ones. The eighteen vertices on the periphery belong to the old as well as the new polytope. In the original polytope each vertex on the periphery had one edge connecting it to a vertex of the old clique and hence in the new polytope that vertex must have one edge connecting it to the new clique. The edges are color coded to help indicate how the edges get rearranged.
Let us assume each minimal c-dep requires k vectors (where k is the dimension of the Gale space). This corresponds to the case of a simple polytope. Given a general c-dep and one vector z not included in the c-dep, there is a unique c-dep consisting of z together with all but one of the vectors of the original c-dep. One way of picturing this is that z “pushes out” exactly one vector of original c-dep to form a new one. In terms of the polytope, we start at the vertex corresponding to the original c-dep. This “pushing out” then corresponds to leaving the facet the corresponds to z. At each vertex of a simple polytope and for each facet incident to the vertex, there is exactly one edge incident to the vertex leading away from the facet. The vector “pushed out” by z corresponds to the facet reached by taking that edge.
Here is an example with a 5-polytope. A clique consisting of four (gray) vertices is replaced with a clique consisting of just two vertices. In the original polytope, the adjacent vertices, colored yellow, each has a single edge connecting it to the old clique. In the new polytope it must have a single edge connecting it to the new clique.
Within parentheses in the diagrams above I indicate some information about the c-deps corresponding to each vertex. The clique vertices have c-deps that consist of a shared “core” of (k-1) vectors – indicated as “C”, plus one additional vector (indicated as “1”, “2”, “3” or “4” in the left clique and as “x” or “y” in the right clique).
Now consider a vector z not included in any of the c-deps of our original clique. Each of these vectors must “push out” exactly one vector from each c-dep in the clique. Moreover, the vector “pushed out” by z must be one of the vectors of the “core” since otherwise there would be a co-vertex of the form {C, z} which would then be part of the clique, contradicting the hypothesis that z is not included in any of the clique’s c-deps.
The diagram above uses “?” to indicate any set of vectors that consist of all but one of the vectors of the core C. The excluded vector cannot be determined and typically will vary from one yellow vertex to the next. The important point is that we do not need to know the details of various ?’s to understand exactly how clique replacement works.
Let V represent the set of all vectors not included in any of the c-deps of the original clique. If we group together all the peripheral vertices joined to a particular vertex of the original clique -- as in the diagram on the left above -- then each element of V has exactly one vertex per group that corresponds to a c-dep including that vector. For example, in the diagram on the left, x and y are not included in any of the original clique’s c-deps and each appears once in each of the four groups of yellow vertices.
Moreover, each vector in V will be included in exactly one c-dep of the new clique. This implies that each vertex of the new clique must be connected by an edge to exactly one vertex from each group of peripheral vertices. In the diagram on the right, 1,2,3 and 4 are not included in the new clique’s c-deps, instead each c-dep includes either x or y. Each co-vertex on the periphery must include exactly one of {x, y} and exactly one of {1, 2, 3, 4} Thus all the edge assignments have been determined by the clique replacement and do not require any additional information about the combinatorics of the polytope. In this sense, we can think of clique replacement as a “local operation”.