<p>On (1): The case of stable sets in graphs may clarify the situation (a <em>stable</em> set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable sets of $G$.</p>

<p>The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called <em>rank-perfect</em> graphs (see <a href="https://www.google.fr/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;uact=8&amp;ved=0CCIQFjAAahUKEwip07-65qPHAhXGtRoKHdUzDFw&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.1439%26rep%3Drep1%26type%3Dpdf&amp;ei=R17LVemTBMbratXnsOAF&amp;usg=AFQjCNH6UEQ9JmjiiTp1Pdet2UxmKsVHyQ&amp;bvm=bv.99804247,d.d2s" rel="nofollow">Wagler</a>). They include line graphs (by Edmonds' matching polytope theorem), perfect graphs, series-parallel graphs and more. Wheels with an even number of at least 6 vertices provide a basic example of non-rank-perfection.</p>

<p>To my knowledge, no characterization of rank-perfect graphs is known, and the problem of their recognition may be difficult. <a href="https://www.google.fr/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;uact=8&amp;ved=0CCIQFjAAahUKEwihgd3t5aPHAhWGfhoKHXzkCFY&amp;url=http%3A%2F%2Flink.springer.com%2Farticle%2F10.1007%252Fs10107-005-0655-7&amp;ei=pl3LVaGWBIb9afzIo7AF&amp;usg=AFQjCNFzHyhc1OZfz1g5c7Yt3pB3sW9w9g&amp;bvm=bv.99804247,d.d2s" rel="nofollow">Pêcher and Wagler</a> have several partial results on rank-perfect webs. By contrast, Wagler showed that the complements of webs are all rank-perfect.</p>

<p>On (2): the answer is negative as shows the following example. Let $G$ be the claw (i.e the complete bipartite graph $K_{1,3}$). It is well-known that since $G$ is bipartite, the non-trivial facets of $P(V(G),\mathcal{S}(G))$ are the edge-inequalities and hence are rank-facets.</p>

<p>Now, suppose by contradiction that $\mathcal{S}(G)$ is the set of common independent sets of two matroids. Using the weak circuit axiom of matroids in each matroid (that is, for each distinct circuits $C_1$ and $C_2$ of a matroid $M$ and each $e\in C_1\cap C_2$, there is a circuit in $(C_1\cup C_2)-e$), it is straightforward to check that a clique of size 2 must belong to $\mathcal{S}(G)$: a contradiction.</p>

<p>The same argument shows an example with more vertices but no claw: the circuit with 5 vertices. </p>

CC BY-SA 3.0
2015-08-12T15:06:42.610Z
2015-08-12T15:06:42.610Z
Yohann
<p>Consider an <a href="http://en.wikipedia.org/wiki/Independence_system" rel="nofollow">independence system</a> $(E,\mathcal{I})$, and the corresponding polytope:</p>

<p>$P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$</p>

<p>where $x^S \in \{0,1\}^E$ denotes the characteristic vector of $S$. A <em>rank inequality</em> has the form $\sum_{i \in S} x_i \le r(S)$, where $S\subseteq E$ and $r(S):=\max\{ |A| : A \subseteq S,~ A \in \mathcal{I}  \}$. Let's say that the nonnegativity bounds $-x_i \le 0,~i \in E$ are trivial.</p>

<p>(1) When is it true that all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities? </p>

<p>It is known, for example, that if $(E,\mathcal{I})$ is a matroid, or the intersection of two matroids, then all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities. </p>

<p>(2) Does the converse hold, i.e., if all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities, then $(E,\mathcal{I})$ can be written as the intersection of two matroids?</p>

<independence><polytope>
When are all facets rank facets? (for independence system polyhedra)
Austin Buchanan
# When are all facets rank facets? (for independence system polyhedra)

(Asked by: username_0 on 2015-06-07)

Consider an [independence system](http://en.wikipedia.org/wiki/Independence_system) $(E,\mathcal{I})$, and the corresponding polytope:

$P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$

where $x^S \in \{0,1\}^E$ denotes the characteristic vector of $S$. A *rank inequality* has the form $\sum\_{i \in S} x\_i \le r(S)$, where $S\subseteq E$ and $r(S):=\max\{ |A| : A \subseteq S,~ A \in \mathcal{I} \}$. Let's say that the nonnegativity bounds $-x\_i \le 0,~i \in E$ are trivial.

(1) When is it true that all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities?

It is known, for example, that if $(E,\mathcal{I})$ is a matroid, or the intersection of two matroids, then all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities.

(2) Does the converse hold, i.e., if all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities, then $(E,\mathcal{I})$ can be written as the intersection of two matroids?

**Tags:** independence, polytope

---

## 1 answers

### Answer by username_1 on 2015-08-12. Score: 2 | Accepted answer

On (1): The case of stable sets in graphs may clarify the situation (a *stable* set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable sets of $G$.

The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called *rank-perfect* graphs (see [Wagler](https://www.google.fr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCIQFjAAahUKEwip07-65qPHAhXGtRoKHdUzDFw&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.1439%26rep%3Drep1%26type%3Dpdf&ei=R17LVemTBMbratXnsOAF&usg=AFQjCNH6UEQ9JmjiiTp1Pdet2UxmKsVHyQ&bvm=bv.99804247,d.d2s)). They include line graphs (by Edmonds' matching polytope theorem), perfect graphs, series-parallel graphs and more. Wheels with an even number of at least 6 vertices provide a basic example of non-rank-perfection.

To my knowledge, no characterization of rank-perfect graphs is known, and the problem of their recognition may be difficult. [Pêcher and Wagler](https://www.google.fr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCIQFjAAahUKEwihgd3t5aPHAhWGfhoKHXzkCFY&url=http%3A%2F%2Flink.springer.com%2Farticle%2F10.1007%252Fs10107-005-0655-7&ei=pl3LVaGWBIb9afzIo7AF&usg=AFQjCNFzHyhc1OZfz1g5c7Yt3pB3sW9w9g&bvm=bv.99804247,d.d2s) have several partial results on rank-perfect webs. By contrast, Wagler showed that the complements of webs are all rank-perfect.

On (2): the answer is negative as shows the following example. Let $G$ be the claw (i.e the complete bipartite graph $K\_{1,3}$). It is well-known that since $G$ is bipartite, the non-trivial facets of $P(V(G),\mathcal{S}(G))$ are the edge-inequalities and hence are rank-facets.

Now, suppose by contradiction that $\mathcal{S}(G)$ is the set of common independent sets of two matroids. Using the weak circuit axiom of matroids in each matroid (that is, for each distinct circuits $C\_1$ and $C\_2$ of a matroid $M$ and each $e\in C\_1\cap C\_2$, there is a circuit in $(C\_1\cup C\_2)-e$), it is straightforward to check that a clique of size 2 must belong to $\mathcal{S}(G)$: a contradiction.

The same argument shows an example with more vertices but no claw: the circuit with 5 vertices.


---

