Re: (non)complete graphs of polytopes and (non)unique decomposition as a convex combination of vertices

* Erik Quaeghebeur <equaeghe@xxxxxxxxxxxxxx>:
I think (but am not sure) that when one has a polytope with a complete
graph as adjacency graph (of its vertices), any point of the polytope
can be written as a unique convex combination of these vertices _and_ that
the converse also holds: a polytope with a noncomplete graph as adjacency
graph does not have this property,

Yes, you are correct on both counts. Radon's theorem says that
the vertex set of a polytope of dimension d with more than d+1
points can be partitioned into two blocks whose convex hulls
intersect, implying your second claim above. This theorem is
discussed in A. Barvinok's book _A Course in Convexity_, among
other places.

A polytope whose vertex adjacency graph is complete is a simplex.
There is a geometric proof that points in a simplex admit a unique
decomposition as a convex combination of vertices. Any simplex of
positive dimension is a pyramid over a simplex of smaller
dimension. Each point in a pyramid lies on a unique line segment
from the apex to the base, and any point on a line segment can be
written as a convex combination of the endpoints in a unique way.
The result follows from the fact that the apex and (by induction)
all points of the base have unique decompositions as convex
combinations of vertices.

Radon's theorem can be proved by translating it into linear
algebra. Form the matrix whose columns are the vertices of a
polytope, and augment it by adding an initial row of 1s. Call the
resulting matrix A. Applying A to a vector x yields a vector
whose first coordinate is the sum of the coordinates of x and
whose remaining coordinates are the appropriate linear combination
of the vertices of the polytope. Thus if x is nonnegative and the
first coordinate of Ax is 1, the rest of Ax gives the coordinates
of the convex combination of the vertices using the coordinates of
x as coefficients. If the polytope has more vertices than a
simplex, the nullspace of A is nontrivial. Each nonzero vector x
in the nullspace of A corresponds to a partition of the vertex set
of the polytope satisfying the conclusion of Radon's theorem. The
partition can be read off directly from x: vertices in one block
correspond to nonnegative coordinates of x, while vertices in the
other block correspond to negative coordinates of x.

--
Michael Slone
.

Relevant Pages