Open Collections

On a hypersimplicial Van Kampen-Flores theorem

Banff International Research Station for Mathematical Innovation and Discovery

The convex dimension of a k-uniform hypergraph is the smallest dimension d for which there is an injective mapping of its vertices into R^d such that the set of k-barycenters of all hyperedges is in convex position. We completely determine the convex dimension of complete k-uniform hypergraphs. This settles an open question by Halman, Onn and Rothblum, who solved the problem for complete graphs. We also provide lower and upper bounds for the extremal problem of estimating the maximal number of hyperedges of k-uniform hypergraphs on n vertices with convex dimension d. To prove these results we restate them in terms of affine projections of the hypersimplex that preserve its vertices. More generally, we study projections that preserve higher dimensional skeleta. In particular, we obtain a hypersimplicial generalization of the linear van Kampen-Flores theorem: for each n, k and i we determine onto which dimensions can the (n,k)-hypersimplex be linearly projected while preserving its i-skeleton.

Mathematics; Geometry; Convex and discrete geometry; Discrete mathematics

video/mp4

Author affiliation: Sorbonne Université

2020-04-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73903

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/