Separable partitions (Q1283783)

For any fixed \(d\geq 1\) and \(p\geq 2\), this paper provides tight asymptotic bounds on \(r_{p,d}(n)\), the maximal number of partitions of an \(n\)-subset of \({\mathbb{R}}^d\) into \(p\) parts withs disjoint convex hulls (``separable \(p\)-partitions of an \(n\)-subset of \({\mathbb{R}}^d\)''). Namely, \(r_{p,1}(n)=p!{n-1\choose p-1}=\Theta (n^{p-1})\) in the \(1\)-dimensional case, \(r_{p,2}(n)=\Theta(n^{3p-6})\) corresponding to the fact that a suitable planar dual graph with \(p\) vertices has at most \(3p-6\) edges, and \(r_{p,d}(n)=\Theta(n^{d{p\choose 2}})\) for \(d\geq 3\) corresponding to the existence of neighborly configurations. Similar results are given for the more general situation of \(n\)-point spaces of Vapnik-Chervonenkis dimension \(d+1\). The special case where the \(n\) points lie on a moment curve is considered as well.