The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem

DOI10.1016/J.JCTB.2021.01.003MaRDI QIDQ2033908zbMATH OpenOpenAlexFDO

Authors L. Martínez-Sandoval, Arnau Padrol

Publication date 18 June 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.01189

zbMATH Keywords

\(k\)-setsconvex embeddings of hypergraphsdimensional ambiguity of polytope skeletahypersimplicesMinkowski sumsVan Kampen-Flores theorem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Convex programming (90C25)

Abstract: The convex dimension of a $k$-uniform hypergraph is the smallest dimension $d$ for which there is an injective mapping of its vertices into $mathbb{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, which 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 that preserve the vertices of the hypersimplex. More generally, we provide a full characterization of the projections that preserve its $i$-dimensional skeleton. 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. Our results have direct interpretations in terms of $k$-sets and $(i,j)$-partitions, and are closely related to the problem of finding large convexly independent subsets in Minkowski sums of $k$ point sets.

Recommendations

• Extension complexity and realization spaces of hypersimplices
• A lower bound on the crossing number of uniform hypergraphs
• scientific article; zbMATH DE number 4193691
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n
• Polytopes determined by hypergraph classes

Cites work

• k-sets and k-facets
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• An Improved Bound for k-Sets in Four Dimensions
• An improved bound for \(k\)-sets in three dimensions
• Construction and analysis of projected deformed products
• Convex combinatorial optimization
• Convex Matroid Optimization
• Convexly independent subsets of the Minkowski sum of planar point sets
• Cutting dense point sets in half
• Drawing graphs with vertices and edges in convex position
• Extension complexity and realization spaces of hypersimplices
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 2008526 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3016279 (Why is no real title available?)
• scientific article; zbMATH DE number 960150 (Why is no real title available?)
• In between k-sets, j-facets, and i-faces: (i,j)-partitions
• Large convexly independent subsets of Minkowski sums
• Lectures on Polytopes
• Maximal f-vectors of Minkowski sums of large numbers of polytopes
• Neighborly cubical polytopes
• Neighbourliness and Radon's theorem
• Non-projectability of polytope skeleta
• Normal polytopes arising from finite graphs
• On the equations of the edge cone of a graph and some applications
• On the largest convex subsets in Minkowski sums
• On the Number of Incidences Between Points and Curves
• Proceedings of the International Congress of Mathematicians (ICM 2018)
• Prodsimplicial-neighborly polytopes
• Projected products of polygons
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• The convex dimension of a graph
• The degree of point configurations: Ehrhart theory, Tverberg points and almost neighborly polytopes
• Topological obstructions for vertex numbers of Minkowski sums
• Weak separation and plabic graphs

Cited in

(2)

• Convex hulls of Grassmannians and combinatorics of symmetric hypermatrices
• van Kampen-Flores theorem and Stiefel-Whitney classes

This page was built for publication: The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033908)