Return to Question

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polytope in terms of the underlying graph. In particular, when are two vertices adjacent?

Edit : I think that the face lattice embeds in $\{0,1\}^A$ via the support of a vector function ($x \in P$ goes to $\{ i : x_i > 0\}$), and this makes the face lattice isomorphic to the lattice of directed subgraphs of $G$ that are unions of directed simple cycles. This is pretty much the description I'm looking for, although based on the link it seems like more is probably known in the right references -- if I can verify the details I'll update the question with an answer.

*The circulation polytope of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polyhedron* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polyhedron in terms of the underlying graph. In particular, when are two vertices adjacent?

Edit : I think that the face lattice embeds in $\{0,1\}^A$ via the support of a vector function ($x \in P$ goes to $\{ i : x_i > 0\}$), and this makes the face lattice isomorphic to the lattice of directed subgraphs of $G$ that are unions of directed simple cycles. This is pretty much the description I'm looking for, although based on the link it seems like more is probably known in the right references -- if I can verify the details I'll update the question with an answer.

*The circulation polyhedron of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polytope in terms of the underlying graph. In particular, when are two vertices adjacent?

*The circulation polytope of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polytope in terms of the underlying graph. In particular, when are two vertices adjacent?

Edit : I think that the face lattice embeds in $\{0,1\}^A$ via the support of a vector function ($x \in P$ goes to $\{ i : x_i > 0\}$), and this makes the face lattice isomorphic to the lattice of directed subgraphs of $G$ that are unions of directed simple cycles. This is pretty much the description I'm looking for, although based on the link it seems like more is probably known in the right references -- if I can verify the details I'll update the question with an answer.

*The circulation polytope of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the faces of this polytope in terms of the underlying graph. In particular, when are two vertices adjacent?

*The circulation polytope of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.

I know how to show that the vertices correspond to directed simple cycles, but I am looking for a combinatorial description of the higher dimensional faces of this polytope in terms of the underlying graph. In particular, when are two vertices adjacent?

*The circulation polytope of a directed graph $(G,A)$ is defined by:

$\{ x \in \mathbb{R}^E : x \geq 0, \nabla \cdot x = 0 \}$, where $\nabla : \mathbb{R}^E \to \mathbb{R}^V$ is the "graph divergence" operator, $(\nabla \cdot e)(v) =\sum_{ (i,v) | (i,v) \in E} x_{(i,v)} - \sum_{ (v,i) \in E} x_{(v,i)}$.