When are all facets rank facets? (for independence system polyhedra)

Question

Consider an 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?

Answer 1

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). 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 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.