A High-Dimensional Extension of Wagner's Theorem and the Geometrization of Hypergraphs

Abstract

This paper introduces a geometric representation of hypergraphs by representing hyperedges as simplices. Building on this framework, we employ homotopy groups to analyze the topological structure of hypergraphs embedded in high-dimensional Euclidean spaces. Under the assumptions of the triangulation and that all $i$-th homotopy groups are trivial for $i\le d-2$, we provide a necessary and sufficient condition for a $d$-uniform hypergraph to be embeddable in ${\mathbb{R}}^d$, which can be regarded as a kind of high-dimensional extension of Wagner's Theorem for planar graphs. Specifically, we establish that a triangulated $d$-uniform topological hypergraph embeds into ${\mathbb{R}}^d$ if and only if it contains neither $K_{d+3}^d$ nor $K_{3,d+1}^d$ as a minor. Here, a triangulated $d$-uniform topological hypergraph constitutes a geometrized form of a $d$-uniform hypergraph, while $K_{d+3}^d$ and $K_{3,d+1}^d$ are the high-dimensional generalizations of the complete graph $K_5$ and the complete bipartite graph $K_{3,3}$ in ${\mathbb{R}}^d$, respectively.

28 pages, 10 figures, submitted