Inclusion-exclusion principles for convex hulls and the Euler relation

Abstract

Consider $n$ points $X_1,\dots ,X_n$ in ${\mathbb{R}}^d$ and denote their convex hull by $\Pi$. We prove a number of inclusion-exclusion identities for the system of convex hulls ${\Pi }_I:=conv(X_i:i\in I)$, where $I$ ranges over all subsets of $\{1,\dots ,n\}$. For instance, denoting by $c_k(X)$ the number of $k$-element subcollections of $(X_1,\dots ,X_n)$ whose convex hull contains a point $X\in {\mathbb{R}}^d$, we prove that $$c_1(X)-c_2(X)+c_3(X)-\dots +(-1{)}^{n-1}{c}_n(X)=(-1{)}^{\dim \Pi }$$ for all $X$ in the relative interior of $\Pi$. This confirms a conjecture of R. Cowan [Adv. Appl. Probab., 39(3):630--644, 2007] who proved the above formula for almost all $X$. We establish similar results for the number of polytopes ${\Pi }_J$ containing a given polytope ${\Pi }_I$ as an $r$-dimensional face, thus proving another conjecture of R. Cowan [Discrete Comput. Geom., 43(2):209--220, 2010]. As a consequence, we derive inclusion-exclusion identities for the intrinsic volumes and the face numbers of the polytopes ${\Pi }_I$. The main tool in our proofs is a formula for the alternating sum of the face numbers of a convex polytope intersected by an affine subspace. This formula generalizes the classical Euler--Schläfli--Poincaré relation and is of independent interest.

14 pages, no figures