4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.