Cyclic polytopes, hyperplanes, and Gray codes (Q1430536): Difference between revisions

A cyclic polytope is the convex hull of a finite set of points on the moment curve \(M=\{(t,t^2, \ldots, t^d): t\in {\mathbb R}\}\). A hyperplane \(H\) {bisects} a \(j\)-dimensional face \(F\) of a polytope if \(H\) contains a point of the relative interior of \(F\). In this paper is proved that for \(m=\lfloor d/2\rfloor\) and \(m<j<2m\), if \(C\) is a cyclic \(d\)-polytope with at most \(4j-2m\) vertices, then there exists a hyperplane that bisects every \(j\)-face of \(C\). (\textit{K. Bezdek, T. Bisztriczky} and \textit{R. Connelly} [Monatsh.\ Math.\ 109, 39--48 (1990; Zbl 0712.52012)] proved that no such hyperplane exists for \(0\leq j\leq m\).) The bulk of this paper concerns the following question. For fixed \(j\), \(d\), and \(\ell\), find the maximum \(n\) so that for each cyclic \(d\)-polytope \(P\) with at most \(n\) vertices, there exists a collection of \(\ell\) hyperplanes so that every \(j\)-face of \(P\) is bisected by one of the hyperplanes. Lower bounds for the maximum \(n\) are obtained by a construction of the hyperplanes based on balanced Gray codes. Upper bounds are computed by careful analysis of intersections of hyperplanes with the moment curve. The results may not extend to all polytopes combinatorially equivalent to cyclic polytopes.