Skip to main content
added 1 character in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull. Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$. That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$. It is easy to check that the following system completely describes $P(G)$. $$ 0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\ 0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$} $$$$ 0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\ 0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$}. $$ Thus, $P(G)$ has $O(V(G)+E(G))$ facets.

Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs. Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. $$ y(F) \leq z(V(G))-1, \text{ for all spanning forests $F$ of $G$}. $$

Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.

Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull. Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$. That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$. It is easy to check that the following system completely describes $P(G)$. $$ 0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\ 0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$} $$ Thus, $P(G)$ has $O(V(G)+E(G))$ facets.

Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs. Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. $$ y(F) \leq z(V(G))-1, \text{ for all spanning forests $F$ of $G$}. $$

Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.

Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull. Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$. That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$. It is easy to check that the following system completely describes $P(G)$. $$ 0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\ 0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$}. $$ Thus, $P(G)$ has $O(V(G)+E(G))$ facets.

Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs. Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. $$ y(F) \leq z(V(G))-1, \text{ for all spanning forests $F$ of $G$}. $$

Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull. Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$. That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$. It is easy to check that the following system completely describes $P(G)$. $$ 0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\ 0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$} $$ Thus, $P(G)$ has $O(V(G)+E(G))$ facets.

Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs. Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. $$ y(F) \leq z(V(G))-1, \text{ for all spanning forests $F$ of $G$}. $$

Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.