Let $\mathcal{S} = \{S_i\}$ be a collection of subsets of the same size $s$, all drawn from the universe $[n]$, with the property that $|S_i \cap S_j| \le 1$ for all $ i \ne j$. Let us say that $\mathcal{S}$ can be realized in $\mathbb{R}^d$ if one can place a set $X$ of $n$ points in $\mathbb{R}^d$ (identified with the universe $[n]$) such that the set of points in each $S_i$ is a face of the convex hull of $X$ (it's okay if some of the faces of the convex hull of $X$ don't correspond to an $S_i \in \mathcal{S}$, though). I would like to determine how large $d$ might need to be in the worst case.

A couple basic questions about this setup:

  • Has this problem been studied? Does it have a name I can search for?
  • Does $d=3$ always suffice? If not, does $d = C$ always suffice, for some larger absolute constant $C$? If not, are there any natural additional assumptions we can make on the structure of $\mathcal{S}$ so that $d=3$ (or $d=C$) always suffices?
  • $\begingroup$ I don't have a very clean formal argument, but it seems pretty clear that if we just take all 2 element subsets of $n$ points, we'll need $d\ge n-1$. $\endgroup$ – Christian Remling May 22 '17 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.