## The facial structure of the convex hull of a family of characteristic functions

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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$ ?

-

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$.  – Gjergji Zaimi Apr 7 2012 at 21:37
Here is a gentle introduction: arxiv.org/abs/math/9909177 – Gjergji Zaimi Apr 7 2012 at 21:38
Thank you for your reference!   – Pietro Majer Apr 7 2012 at 22:39

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 41, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9202255606651306, "perplexity_flag": "head"}