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.

Definition 2 The k + 1 points a0,a1,,ak n are affinely independent if the only solution λ01,k to the system

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:

• Show every point x in S satisfies gT x h, so the inequality is valid.
• Find d affinely independent points in S satisfying gT x = h, so the dimension of the face is at least d - 1.
• Find one point x S satisfying gT x > h, so the inequality defines a proper face of S.

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 iCxi = 1 for any maximal clique C in the graph.