Characteristic vector of independent points in a graph

Question

I'm trying to understand vertex packing polytopes, and have run into some definitions that I don't understand properly.

In the summary of this paper, the authors say that the vertex packing polytope is "the convex hull of incidence vectors of independent points in a graph."

As I understand it, independent points in a graph have no edge connecting them.

As defined in this stackexchange answer, the $i^{th}$ element in the incidence vector $\chi^F$ is 1 if edge $e_i \in F$, and 0 otherwise.

Doesn't this imply that the incidence vector of independent points in a graph is always the zero vector?

Answer 1

The StackExchange link defines an incidence vector of a set of edges.

In general, if we are dealing with subsets of a set $S$, we can give each $A \subseteq S$

• A characteristic function $\chi_A : S \to \mathbb R$, defined as $\chi_A(x) = \begin{cases}1 & x \in A \\ 0 & x \notin A\end{cases}$;
• An incidence vector (or indicator vector) in $\mathbb R^{|S|}$, whose $i^{\text{th}}$ element is $1$ if $A$ contains the $i^{\text{th}}$ element of $S$.

(The second definition seems to require an ordering of $S$, but it usually will not matter which ordering we pick, as long as we stick to it.)

Independent sets in graphs are subsets of the vertex set, and we treat them that way. So the incidence vectors we'll get will be subsets of $\mathbb R^{|V|}$.

Here is an example. Suppose we are dealing with the graph

v1 -- v2 -- v3

The independent sets here are $\emptyset$, $\{v_1\}$, $\{v_2\}$, $\{v_3\}$, and $\{v_1,v_3\}$. Their incidence vectors are $(0,0,0)$, $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, and $(1,0,1)$. The vertex packing polytope lives in $\mathbb R^3$; it is defined as the convex hull of these five points.