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 a^{0},a^{1},…,a^{k} ∈ ℝ^{n} are affinely independent if the k vectors
a^{1} - a^{0},a^{2} - a^{0},…,a^{k} - a^{0} are linearly independent.

Definition 2 The k + 1 points a^{0},a^{1},…,a^{k} ∈ ℝ^{n} are affinely independent if the only solution
λ_{0},λ_{1},…,λ_{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 g^{T }x ≥ h defines a facet of S, we need to:

- Show every point x in S satisfies g
^{T }x ≥ h, so the inequality is valid. - Find d affinely independent points in S satisfying g
^{T }x = h, so the dimension of the face is at least d - 1. - Find one point x ∈ S satisfying g
^{T }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 x_{i} = 0 for any i = 1,…,n.
Further, there exist n affinely independent points in S satisfying ∑
_{i∈C}x_{i} = 1 for any maximal
clique C in the graph.