The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of $d$-cycles, $d$-hypertrees and $d$-hypercuts are, respectively, $(d+1)$, $d$, and $(n
-d-1)$-vertex-connected. It is also shown that the facet graph of a $d$-cycle cannot be split into more than $s$ connected components by removing at most $s$ vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.
We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes
. We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgains theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $ell_1$-volume with distortion smaller than $tilde{Omega}(n^{1/5})$. We further address the problem of $ell_1$-dimension reduction in the context of $ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $ell_1$ metric on $n$ points can be $(1+ epsilon)$-approximated by a sum of $O(n/epsilon^2)$ cut metrics, improving over the best previously known bound of $O(n log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{u}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.
