Proving a Face is a Facet
John E. Mitchell
We show how the dimension of a face can be determined using the construction of affinely independent points. This approach can be used to prove that a face of a polyhedron is a facet. Later, we will demonstrate another method for the MaxCut problem.
Recall two equivalent definitions of affine independence:
Definition 1 The k+1 points a0,a1,…,ak ∈ ℝn are affinely independent if the k vectors a1 - a0,a2 - a0,…,ak - a0 are linearly independent.
is λ0 = λi = … = λk = 0.
Note that Definition 2 implies that if k + 1 points are linearly independent then they are also affinely independent. (The converse does not necessarily hold.)
We also have the following proposition:
Proposition 1 If a set S ⊆ ℝn contains k+1 affinely independent points then the dimension of S is at least k.
Thus, constructing a sufficiently large set of affinely independent points in S provides a lower bound on the dimension of S. If we can construct valid equalities Ax = b that are satisfied by all points in S then we obtain an upper bound of n - rank(A) on the dimension of S. Getting these bounds to agree would then give the dimension of S.
When S is a set of integer (or binary) points, the first step is to determine the dimension d of S. To then show that an inequality gT x ≥ h defines a facet of S, we need to:
This approach is used for node packing in a graph on n vertices.
First, the convex hull of the set S of feasible packings can be shown to have dimension n: we have n + 1 affinely independent points in S, namely the origin and all the unit vectors.
Then there exist n affinely independent points in S satisfying xi = 0 for any i = 1,…,n. Further, there exist n affinely independent points in S satisfying ∑ i∈Cxi = 1 for any maximal clique C in the graph.