3
$\begingroup$

Let $S$ be a finite set and let $\mathcal{A} \subset\mathcal{P}(S)$ be a family of subsets of $S$. Consider the convex polytope spanned by the characteristic functions of members of $\mathcal{A}$ : $$C=C_ \mathcal{A}:=\operatorname{co}\{ \mathbf {1}_A \, : \, A\in\mathcal{A} \}\, .$$ It's easy to see that every $\mathbf {1} _ A$, for $A\in\mathcal{A}$, is extremal in $ C_ \mathcal{A}$ (indeed, if we have a convex combination $\mathbf {1} _ A= \sum_{B\in\mathcal{A}}\lambda _ B\, \mathbf {1} _ B $, then $B\subset A$ for any $B$ corresponding to a coefficient $\lambda _ B > 0$, so $\sum_{B\in\mathcal{A}}\lambda _ B\left(|A|-|B| \right )=0 $, whence $\lambda _ A =1 $ is the only non-zero coefficient of the convex combination).
Therefore, the vertex set of $ C_ \mathcal{A}$ is exactly $\{ \mathbf {1}_A \, : \, A\in\mathcal{A} \}$, that we may identify abstractly with $\mathcal{A}$ itself.

Question 1. How to describe the complete abstract facial structure of $C$ in terms of the combinatorics of $\mathcal{A}$?

I suspect that for a general family $\mathcal{A}$ this task may prove to be quite hard. If so, I'd like to see known examples of polytopes obtained this way, especially when $\mathcal{A}$ enjoies special regularity properties, such that the skeleton of $C_ \mathcal{A}$ admits simple description. For instance:

Let $S$ be the $r$-th Cartesian power of the set $[n]:=\{1,2,\dots,n \} $ , $S={n}^r$, and let $$\mathcal{A}:=\{B^{\, r} \, : \, B\subset R \}\, .$$ Question 2. Which polytope is the corresponding $C_ n^r:=C _ \mathcal{A}$?

The present problem, especially in the latter example, has been suggested to me by a recent interesting question, which is related to the case $r=2$ (the analogous problem of the one described there, where one consider all intersections of $r$ sets extracted from a given family of $n$, yields to the above polytope $C _ n ^ r\subset \mathbb{R}^{n^r}$).

Up-date, April 13, 2012. Thanks to the very interesting references given so far, I see that my naive suspicions about the difficulty of question 1 were after all right . So, I would like to focus the attention on question 2: what can be said about $C_n^r$, at least for $r=2$? Can we at least count the number $f_k $ of $k$-dimensional faces of $C_n^2$: which polynomial sequence do they define, $P_n(x):=\sum_{k\ge 0} f_k x^k$ ?

$\endgroup$
2
  • $\begingroup$ The combinatorics of $0/1$ polytopes is not as simple as you'd expect from looking at low dimensional examples. It would be nice if you had a specific question in mind for $C^r_n$. $\endgroup$ Apr 7, 2012 at 21:37
  • $\begingroup$ Here is a gentle introduction: arxiv.org/abs/math/9909177 $\endgroup$ Apr 7, 2012 at 21:38

1 Answer 1

2
$\begingroup$

In addition to the notes by Ziegler referenced in the comment above, there are a few general classes of 0/1 polytopes where one can say something about the facial structure.

One example is that of the independent set polytope, $P_{I(M)}$ for a matroid $M$, where one uses the independent sets of the matroid to define the characteristic vectors. In this case, there is a well-known description of the hyperplane description of $P_{I(M)}$ using the rank function for the matroid. Also, one can describe the facets of the polytope using the combinatorial structure of the matroid. See for example Jon Lee's book titled A First Course in Combinatorial Optimization, section 1.7.

Another example of polytopes of this type are permutation polytopes, where one considers the convex hull of a collection of permutation matrices arising as the representation of some finite group. The paper On Permutation Polytopes, by Baumeister, Haase, Nill, and Paffenholz, http://arxiv.org/abs/0709.1615, contains a nice introduction to this topic and investigations of the type you suggest.

$\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.