8
$\begingroup$

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:

$$e_F := \sum_{i\in F} e_i,$$

where $e_i$ denotes the $i$-th canonical vector in $\mathbb{R}^n$. Let us define the polytope $\mathscr{P}(\Delta)$ as the convex hull in $\mathbb{R}^n$ of all these $e_F$ for $F$ ranging in $\Delta$.

Why is this construction interesting? Well, it contains two famous families of polyhedra:

  1. Independence matroid polytopes. This is easy to see, since the family of independent sets of a matroid is indeed a simplicial complex.
  2. Chain polytopes of posets. This is a little bit harder, but still elementary: the vertices of the chain polytope of a poset $P$ are the antichains of $P$, and this defines a simplicial complex.

I have two questions. Has this family of polytopes already been studied? Are there any other big (or interesting) family of polytopes that fall into this category?

As a side note: there is a nice formula for the volume of chain polytopes, I do not know if this is too naive, but maybe this could help to guess a "good" formula for the volume of independence matroid polytopes.

$\endgroup$

2 Answers 2

6
$\begingroup$

For a graph $G$, the stable set polytope $\mathcal{P}(G)$ is the polytope which is the convex hull of the indicator functions of stable (i.e., independent) sets of $G$. Since the stable sets are a simplicial complex, this is another well-studied case of the class of polytopes you mention, and it includes the chain polytopes (where we choose $G$ to be the comparability graph of the poset). See, e.g., Chvátal, "On certain polytopes associated with graphs".

Another seemingly similar class of polytopes is the following. We let $\{I_1,\ldots,I_m\}$ be any (multi)set of subsets of $[n]$, and consider the polytope $\mathcal{P}=\sum_{i=1}^{m}\Delta_{I_i}$ which is the Minkowski sum of the standard simplices $\Delta_{I_i} := \mathrm{ConvHull}(e_j\colon j \in I_i)$. See Section 9 of Postinkov's "Permutohedra, associahedra, and beyond". These Minkowski sums of simplices form a large subclass of the generalized permutohedra, but do not include all generalized permutohedra. The matroid (independence) polytopes are generalized permutohedra, but are not positive Minkowski sums of simplices in general (although they are signed Minkowski sums of simplices): see Ardila--Benedetti--Doker, "Matroid polytopes and their volumes".

$\endgroup$
4
  • $\begingroup$ My thinking behind the 2nd paragraph where I say Postinkov's class is "similar" to yours: for your class you choose a collection of subsets $\{I_1,\ldots,I_m\}$ of $[n]$ and do the convex hull of the sums of $e_j$ for $j \in I_i$ (although I suppose any 0/1 polytope is of this form); while Postinkov does things in the "opposite" order: (Minkowksi) sums of convex hulls of the $e_j$ for $j \in I_i$. I'm not sure there's really any direct connection between the two. $\endgroup$ Commented Dec 7, 2020 at 18:32
  • 1
    $\begingroup$ By the way, as you'll see in the Chvátal paper, we can write down a nice facet description of the stable set polytope exactly when the graph in question is perfect; this happens for comparability graphs of posets (thus the nice description of the facets of the chain poset), but of course not for all graphs. $\endgroup$ Commented Dec 7, 2020 at 18:38
  • $\begingroup$ Thank you Sam. The example of the stable set polytope you gave is indeed interesting! As for what you said about $\mathcal{Y}$-generalized permutohedra (positive Minkowski sum of dilated simplices), I am aware of those. As you mention in your comment, probably the polytopes I defined here are a bit different. Incidentally, if I'm not mistaken, the only $\mathcal{Y}$-generalized permutohedra that have 0/1 vertices are essentially the $0/1$ simplices (i.e. only one Minkowski summand). $\endgroup$ Commented Dec 7, 2020 at 18:39
  • 1
    $\begingroup$ Yes, that's right, the $\mathcal{Y}$-generalized permutohedra are pretty distinct, I guess I just thought they had vaguely a similar flavor, and were sort of related to matroid polytopes. $\endgroup$ Commented Dec 7, 2020 at 18:40
4
$\begingroup$

Another family within your class that has been studied is matching polytopes. Here for a graph $G = (V,E)$ we work in $\mathbb{R}^E$. The matching polytopes in then the convex hull of $e_M$ for matchings of the graph (not necessarily perfect). Since any subset of a matching is a matching it fits in the simplicial complex framework.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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