×

High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. (English) Zbl 1095.52500

Summary: Let \(A\) be a \(d\) by \(n\) matrix, \(d < n\). Let \(C\) be the regular cross polytope (octahedron) in \(\mathbf {R}^{n}\). It has recently been shown that properties of the centrosymmetric polytope \(P = AC\) are of interest for finding sparse solutions to the underdetermined system of equations \(y = Ax\). In particular, it is valuable to know that \(P\) is centrally \(k\)-neighborly.
We study the face numbers of randomly projected cross polytopes in proportional-dimensional case where \(d \sim \delta n\), where the projector \(A\) is chosen uniformly at random from the Grassmann manifold of \(d\)-dimensional orthoprojectors of \(\mathbf {R}^{n}\). We derive \(\rho_{N}(\delta) > 0\) with the property that, for any \(\rho < \rho_{N}(\delta)\), with overwhelming probability for large \(d\), the number of \(k\)-dimensional faces of \(P = AC\) is the same as for \(C\), for \(0 \leq k \leq \rho d\). This implies that \(P\) is centrally \(\lfloor\rho d\rfloor\)-neighborly, and its skeleton Skel\(_{\lfloor \rho d\rfloor}(P)\) is combinatorially equivalent to Skel\(_{\lfloor \rho d\rfloor}(C)\). We display graphs of \(\rho_{N}\).
Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness; we study both. Weak \((k,\varepsilon)\)-neighborliness asks if the \(k\)-faces are all simplicial and if the number of \(k\)-dimensional faces \(f_{k}(P) \geq f_{k}(C)(1 - \varepsilon)\). We characterize and compute the critical proportion \(\rho_{W}(\delta) > 0\) such that weak \((k,\varepsilon)\)-neighborliness holds at \(k\) significantly smaller than \(\rho_{W} d\) and fails for \(k\) significantly larger than \(\rho_{W} d\). Sectional \((k,\varepsilon)\)-neighborliness asks whether all, except for a small fraction \(\varepsilon\), of the \(k\)-dimensional intrinsic sections of \(P\) are \(k\)-dimensional cross polytopes. (Intrinsic sections intersect \(P\) with \(k\)-dimensional subspaces spanned by vertices of \(P\).) We characterize and compute a proportion \(\rho_{S}(\delta) > 0\) guaranteeing this property for \(k/d \sim \rho < \rho_{S}(\delta)\). We display graphs of \(\rho_{S}\) and \(\rho_{W}\).

MSC:

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDFBibTeX XMLCite
Full Text: DOI