New results on lower bounds for the number of \((\leq k)\)-facets (Q1039428): Difference between revisions

The paper is concerned with lower bounds for the number of \((\leq k)\)-facets of a set of points in a Euclidean space. An oriented simplex with vertices at points of \(S\) is said to be a \((\leq k)\)-facet of \(S\), if it has at most \(k\) points of \(S\) in the positive side of its affine hull. The paper presents two different results dealing with the number of \((\leq k)\)-facets of a set of points: (1) gives structural properties of sets in the plane that achieve the optimal lower bound \(3\binom{k+2}{2}\) of \((\leq k)\)-edges for a fixed \(0\leq k\leq \lfloor n/3\rfloor - 1\); and (2) shows that, for \(k<\lfloor n/(d+1)\rfloor \), the number of \((\leq k)\)-facets of a set of \(n\) points in general position in \(\mathbb R^d\) is at least \((d+1)\binom{k+d}{d}\), and that this bound is tight in the given range of \(k\).