2
$\begingroup$

Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull of the points of $S$. Let now $T(S_n)$ be the set of all triplets $\{\mathbf{x}_i, \mathbf{x}_j, \mathbf{x}_k\}$ of points in $S_n$ for all $1\le i<j<k\le n$ such that no point of each triangle having $\mathbf{x}_i, \mathbf{x}_j, \mathbf{x}_k$ as vertices, is an interior point of $C(S_n)$.


Question: What is the maximum cardinality $m(n,d)$ of $T$ over all possible sets $S_n$ of $n$ points in $\mathbb{R}^d$?

$\endgroup$
2
  • 1
    $\begingroup$ You probably want some kind of non-degeneracy condition: if all the points $\mathbf{x}_i$ are the same then $C(S_n)$ has no interior points and so you just get $m(n,d)=\binom{n}{3}$. If you just assume that $C(S_n)$ has nonempty interior then I think you still get a fairly trivial answer. You probably want to assume that every $(d+1)$-tuple in $S_n$ is affinely independent. $\endgroup$ Feb 4, 2021 at 12:31
  • $\begingroup$ Yes, you are right @NeilStrickland, of course. I will add the assumption to the question. Thank you! $\endgroup$ Feb 4, 2021 at 12:35

1 Answer 1

5
$\begingroup$

A $3$-neighborly polytope is one in which every triple of vertices forms a face. Such $k$-neighborly polytopes exist and achieve the maximum number of $k$-faces, by the upper bound theorem of McMullen.

So your maximum bound is $\binom{n}{3}=O(n^3)$, as Neil Strickland suggests.

$\endgroup$
2
  • 4
    $\begingroup$ Slight addendum: 3-neighborly polytopes with an arbitrary number of vertices exist in dimensions 6 and greater. The only 3-neighborly polytopes in dimensions 5 and below are simplices. This is explained in the linked Wikipedia article, at any rate. $\endgroup$ Feb 4, 2021 at 14:41
  • 1
    $\begingroup$ @SamHopkins: Oh, good point---Thanks! $\endgroup$ Feb 4, 2021 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.