A High-Dimensional Extension of Wagner’s Theorem and the Geometrization of Hypergraphs
October 02, 2025
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. Leveraging this foundation, we extend Wagner’s theorem to \(\mathbb{R}^d\). 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.
Wagner’s theorem ,embedding ,hypergraph ,homotopy group ,minor ,the Hadwiger conjecture
MSC (2020): 05C10
1 Introduction↩︎
Wagner’s theorem establishes that a finite graph is planar if and only if it contains neither \(K_5\) nor \(K_{3,3}\) as a minor, thereby characterizing the embeddability of graphs into \(\mathbb{R}^2\). This raises a natural question: Does an analogous characterization exist for higher-dimensional Euclidean spaces? However, the complexity and non-intuitive nature of higher dimensions make it challenging to define appropriate generalizations of concepts such as planarity, complete graphs, and complete bipartite graphs. To address this, we first establish a correspondence between hyperedges and simplices, thereby endowing hypergraphs with a geometric structure. Then, utilizing homotopy groups, we characterize the topological structure of hypergraphs embedded in higher-dimensional spaces and define a class of hypergraphs embeddable into \(\mathbb{R}^d\), termed \(\mathbb{R}^d\)-hypergraphs. Evidently, an \(\mathbb{R}^d\)-hypergraph serves as a higher-dimensional generalization of a planar graph. Correspondingly, we generalize the complete graph \(K_5\) and the complete bipartite graph \(K_{3,3}\) to \(\mathbb{R}^d\), denoted by \(K_{d+3}^d\) and \(K_{3,d+1}^d\), respectively. Building on these definitions, we extend Wagner’s theorem to higher dimensions and prove the following result. Here, a triangulated \(d\)-uniform topological hypergraph refers to a geometrized \(d\)-uniform hypergraph (formal definitions are provided in Section 2-3).
Theorem 1. 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.
Theorem 1 characterizes the embeddability of \(d\)-uniform hypergraphs into \(\mathbb{R}^d\), reducing the problem of determining higher-dimensional embeddability to verifying the absence of specific minors. It is important to note that higher-dimensional generalizations of Wagner’s theorem are not unique. Theorem 1 presents a concise formulation, established under the assumption of the absence of pendant simplexoids, which are the generalizations of pendant edges in higher dimensions.
Prior to this work, existing research on graph embeddings predominantly focused on two-dimensional closed surfaces and three-dimensional Euclidean space. For two-dimensional closed surfaces, the Ringel-Youngs theorem [1] states that \(\chi(G)\leq \frac{1}{2} (7+\sqrt{49-24c'})\) for any graph \(G\) embeddable in a surface \(\Sigma\) of Euler characteristic \(c'\). In 1979, Filotti et al. [2] devised a polynomial-time algorithm with complexity \(O(n^{\alpha k+\beta})\) to determine embeddability on orientable surfaces. This algorithm was subsequently optimized, culminating in Mohar’s \(O(n)\)-time solution [3], [4] in 1996. For three-dimensional space, Bothe introduced the concept of linkless embedding [5] in 1973: an embedding of an undirected graph into \(\mathbb{R}^3\) where no two cycles are linked. (The related concept of knotless embedding [6] is defined analogously.) Cohen et al. [7] proved in 1995 that every finite graph embeds into \(\mathbb{R}^3\). Since graphs are \(1\)-dimensional CW complexes, this result implies that studying graph embeddings into \(\mathbb{R}^4\) or higher dimensions is trivial. Consequently, investigating embedding problems for graphs or hypergraphs in higher-dimensional Euclidean spaces requires first representing them geometrically as higher-dimensional CW complexes. Motivated by this perspective, we initiate our study by geometrizing hypergraphs and subsequently establishing definitions and theorems for their embeddings in high-dimensional spaces. Crucially, our primary motivation stems from the profound connection between hypergraph embeddings in high dimensions and the Hadwiger Conjecture. This connection, which constitutes a key direction for our future work, will be briefly discussed in the final section.
In order to yield an intuitive structural understanding of hypergraphs embedded in higher-dimensional spaces before presenting the proof of Theorem 1, we introduce key concepts including simplices, CW complexes, skeleton, homotopy, fundamental groups, and the \(n\)-th homotopy group \(\pi_n(X)\). Standard definitions and notations not explicitly stated here follow [8]–[10]. Note: A topological space \(X\) is \(n\)-connected if \(\pi_i(X) = 0\) for all \(i \leq n\). In contrast, a graph is \(k\)-connected if its vertex connectivity is at least \(k\). These represent fundamentally distinct concepts. To avoid ambiguity, we will explicitly specify whether \(n\)-connected refers to a space or a graph in all subsequent usage. To provide intuitive insight, we briefly describe the structure of \(d\)-uniform hypergraphs embedded in \(\mathbb{R}^d\), drawing an analogy to planar graphs. Ignoring cut edges, any planar graph admits an ear decomposition; equivalently, every \(2\)-connected planar graph can be viewed as a cycle with attached paths. Generalizing this structure to higher dimensions: Interpret each \((d-1)\)-simplex as a hyperedge of a \(d\)-uniform hypergraph. View an embedding of such a hypergraph into \(\mathbb{R}^d\) as a union of: A single \((d-1)\)-dimensional sphere, and a collection of \((d-1)\)-dimensional disks, intersecting only along their boundaries.
The rest of this paper is organized as follows. Section 2 mainly talks about the definitions of hypergraphs that can be embedded in \(\mathbb{R}^d\). In Section 3, we give the definitions of closed \(\mathbb{R}^d\)-hypergraph and triangulated \(\mathbb{R}^d\)-hypergraph. In Sections 4 and 5, we prepare the groundwork for proving Theorem 1, and the proof is laid out in Section 6. Section 7 briefs the significance of this work and outlines some exploring directions.
2 \(\mathbb{R}^d\)-hypergraph: Definition and property↩︎
Topologically, a planar graph is well understood as a finite union of \(1\)-dimensional spheres (cycles) and \(1\)-dimensional balls (paths), forming a structure embeddable in \(\mathbb{R}^2\). A natural generalization involves considering a finite union of \((d-1)\)-dimensional spheres and \((d-1)\)-dimensional balls. If such a structure embeds into \(\mathbb{R}^d\), it constitutes a higher-dimensional analogue of a planar graph. To formalize this, we introduce algebraic topology tools for concise description. By interpreting \((d-1)\)-dimensional simplices as hyperedges of a \(d\)-uniform hypergraph, we extend planar graphs to higher dimensions. Just as line segments (\(1\)-simplices) in planar graphs permit topological deformation, we allow analogous flexibility for hyperedges embedded in \(\mathbb{R}^d\). To avoid ambiguity, we term these deformable hyperedges simplexoids, defined as follows.
Definition 1 (simplexoid). If \(A\) is a simplex of dimension \(k\) with vertex set \(V(A)= \{v_0, v_1, ..., v_k\}\), \(A_0\) is homeomorphic to \(A\), the images of \(V(A)\) under homeomorphism is \(V(A_0)= \{u_0, u_1, ..., u_k\}\), then we say \(A_0\) is a simplexoid* of dimension \(k\), and \(V(A_0)\) is the vertex set of \(A_0\). Furthermore, if \(B\) is an \(i\)-dimensional face of \(A\) with vertex set \(\{v_{x_0}, v_{x_1}, ..., v_{x_i} \}\) (\(\{x_0, x_1, ..., x_i\} \subseteq \{0,1,...,k\}\)), and the image of \(B\) under homeomorphism is \(B_0\), then we say \(B_0\) is an \(i\)-sub-simplexoid of \(A_0\) (or \(i\)-face).*
Building upon the aforementioned definitions, we proceed to geometrize \(d\)-uniform hypergraphs in order to examine their embedding properties in high-dimensional spaces.
Definition 2 (\(d\)-uniform-topological hypergraph). Let \(H = (X,E)\) be a \(d\)-uniform hypergraph. If each hyperedge \(e\) of \(H\) is regarded as a simplexoid of dimension \((d-1)\), each vertex \(v\in V(e)\) is regarded as a \((d-2)\)-sub-simplexoid of \(e\), we refer to such a hypergraph as a \(d\)-uniform-topological hypergraph.
Since every \((d-1)\)-dimensional simplex contains \(d\) faces, each of which is a \((d-2)\)-dimensional simplex, it follows that any \(d\)-uniform hypergraph can be geometrized. According to the above definition, after geometrization, each hyperedge \(e\in E(H)\) becomes a simplexoid of dimension \((d-1)\), while each vertex \(v\in V(e)\) becomes a \((d-2)\)-sub-simplexoid of \(e\). In subsequent discussions, a hyperedge \(e\) with \(d\) vertices is equivalent to a \((d-1)\)-dimensional simplexoid of \(e\). Since we regard the vertices of \(e\) as the \((d-2)\)-sub-simplexoids, while the simplexoid itself also contains vertices in the geometric sense, this may easily lead to confusion. To avoid ambiguity, we shall refer to each \(i\)-sub-simplexoid of \(e\) as \([i]\)-vertex. A \([0]\)-vertex \(v\) may be abbreviated as a vertex \(v\).
Definition 3 (general \(\mathbb{R}^d\)-hypergraph).
Let \(T_1, T_2, ...,T_m\) be simplexoids* of dimension \((d-1)\). We say \(K= \bigcup \limits_{i = 1}^m T_i\) is a general \(\mathbb{R}^d\)-hypergraph if the following conditions hold:*
If \(T_i\) and \(T_j\) are simplexoids* in \(\{T_1, T_2, ...,T_m\}\) and \(T' = T_i\cap T_j \neq \emptyset\), then \(T'\) must be a sub-simplexoid of both \(T_i\) and \(T_j\).*
The \(i\)-th homotopy group of \(K\) is trivial for \(i\in \{1,2,3,...,d-2\}\).
According to Definitions 2 and 3, we know that a general \(\mathbb{R}^d\)-hypergraph is a special type of \(d\)-uniform-topological hypergraph, a general \(\mathbb{R}^d\)-hypergraph may not necessarily be embeddable in \(\mathbb{R}^d\).
Definition 4 (\(\mathbb{R}^d\)-hypergraph and non-\(\mathbb{R}^d\)-hypergraph). If a general \(\mathbb{R}^d\)-hypergraph* \(K\) can be embedded in \(\mathbb{R}^d\), then \(K\) is called an \(\mathbb{R}^d\)-hypergraph; otherwise, \(K\) is called a non-\(\mathbb{R}^d\)-hypergraph.*
Note that the generalized Poincaré conjecture ensures that the \(\mathbb{R}^d\)-hypergraph can always be embedded in the \(d\)-sphere.
According to Definition 3 and 4, it is obvious that the \(\mathbb{R}^d\)-hypergraph is a special case of the general \(\mathbb{R}^d\)-hypergraph. Since the \(i\)-th homotopy group of a \(\mathbb{R}^d\)-hypergraph is trivial, we will prove it can be regarded, up to isomorphism, as a union of internally disjoint \((d-1)\)-dimensional spheres and \((d-1)\)-dimensional balls in the following part. Note that internally disjoint means that their interiors do not overlap and they intersect only at their boundaries. (An \(i\)-sphere \(S^i\) is a topological space that is homeomorphic to a standard \(i\)-sphere. The space enclosed by an \(i\)-sphere is called an \((i+1)\)-ball or \((i+1)\)-disc \(D^{i+1}\).)
In the process of triangulating a planar graph, it is often necessary to add some edges. However, in higher dimensions, such operations become much less intuitive. It is easy to observe that contracting simplexoids in an \(\mathbb{R}^d\)-hypergraph does not alter its homotopy groups. Nevertheless, when adding or removing simplexoids from an \(\mathbb{R}^d\)-hypergraph, one must impose certain constraints to ensure that the homotopy type remains unchanged. Therefore, we need to establish the following lemma.
Lemma 1 (Construction of \(\mathbb{R}^d\)-hypergraph). Every \(\mathbb{R}^d\)-hypergraph can be constructed by the following procedure.
Procedure : \(T_1, T_2, ...,T_m\) are simplexoids* of dimension \((d-1)\) in \(\mathbb{R}^d\). Starting from \(T_0\), add \(T_1, T_2, ..., T_m\) in \(\mathbb{R}^d\) one by one, and this procedure satisfies the following conditions:*
1. Let \(T_i\) and \(T_j\) be arbitrary simplexoids* in \(\{T_1, T_2, ...,T_m\}\) and \(T' = T_i\cap T_j\neq \emptyset\), then \(T'\) is a sub-simplexoid of both \(T_i\) and \(T_j\).*
2. Suppose our procedure is at step \(i\) (\(T_i\) has been added in \(\mathbb{R}^d\)). Let \(K_i= \bigcup \limits_{j = 0}^i T_j\), then \(T_{i+1}\) satisfies the following condition when adding \(T_{i+1}\) to \(\mathbb{R}^d\): \(T_{i+1} \cap K_i \cong D^{d-1}\) or \(T_{i+1} \cap K_i \cong S^{d-1}\).
Proof. We observe that attaching a \((d-1)\)-dimensional simplexoid to an \(\mathbb{R}^d\)-hypergraph is, in fact, equivalent to attaching a \((d-1)\)-cell to the \(\mathbb{R}^d\)-hypergraph along \((d-2)\)-ball or \((d-2)\)-sphere. Therefore, Lemma 2-3 directly implies Lemma 1. ◻
Lemma 2. Let \(X\) be a \(d\)-dimensional CW complex satisfying \(\pi_k(X) = 0\) for all \(k \leq d-1\). Let Y be a \(d\)-dimensional simplex and \(X \cap Y \cong S^{d-1}\), i.e., it is homeomorphic to the \((d-1)\)-dimensional sphere. Then: \(\pi_k(X \cup Y) = 0\) for all \(k \leq d-1.\)
Proof. Since \(Y \cong D^d\) and \(X \cap Y \cong S^{d-1}\) is the boundary of \(Y\), the pair \((X \cup Y, X)\) deformation retracts onto the pair \((Y, S^{d-1})\). Therefore, \[\pi_k(X \cup Y, X) \cong \pi_k(D^d, S^{d-1}).\]
It is a standard fact that the relative homotopy groups satisfy \[\pi_k(D^d, S^{d-1}) = 0 \quad \text{for all } k \leq d - 1.\]
Consider the long exact sequence [11] of homotopy groups for the pair \((X \cup Y, X)\): \[\cdots \to \pi_k(X) \xrightarrow{i_*} \pi_k(X \cup Y) \xrightarrow{\partial} \pi_k(X \cup Y, X) \xrightarrow{\delta} \pi_{k-1}(X) \to \cdots\] Since \(\pi_k(X \cup Y, X) = 0\) for \(k \leq d - 1\), and \(\pi_k(X) = \pi_{k-1}(X) = 0\) for \(k \leq d - 1\) by assumption, the sequence reduces to: \[0 \to \pi_k(X \cup Y) \to 0,\] which implies: \[\pi_k(X \cup Y) = 0 \quad \text{for all } k \leq d - 1.\] ◻
Using a similar approach, we can also prove the following lemma.
Lemma 3. Let \(X\) be a \(d\)-dimensional CW complex satisfying \(\pi_k(X) = 0\) for all \(k \leq d-1\). Let Y be a \(d\)-dimensional simplex and \(X \cap Y \cong D^{d-1}\), i.e., it is homeomorphic to the \((d-1)\)-dimensional sphere. Then: \(\pi_k(X \cup Y) = 0\) for all \(k \leq d-1.\)
In high-dimensional spaces, some common definitions can be generalized as follows.
Definition 5 (multiple simplexoids). Let \(T_1\) and \(T_2\) be \(i\)-dimensional simplexoids* of an \(\mathbb{R}^d\)-hypergraph \(G\). If \(V(T_1)= V(T_2)\), then \(T_1\) and \(T_2\) are called \(i\)-dimensional multiple simplexoids.*
Definition 6 (\(\mathbb{R}^d\)-loops). Let \(T_1\) be an \(i\)-dimensional simplexoid* of an \(\mathbb{R}^d\)-hypergraph. \(V(T_1)=\{u_0, u_1, ..., u_k\}\). If there exists \(u_i, u_j \in V(T_1)\) (\(i\neq j\)) such that \(u_i\) and \(u_j\) overlap, then \(T_1\) is called an \(\mathbb{R}^d\)-loop.*
Since higher-dimensional simplexoids have more than two vertices, the definition of the loops in higher-dimensional manifolds differs slightly from that in planar graphs. As long as two vertices of a simplexoids overlap, we consider it as an \(\mathbb{R}^d\)-loop.
Definition 7 (simple \(\mathbb{R}^d\)-hypergraph). If \(\mathbb{R}^d\)-hypergraph \(G\) does not contain multiple simplexoid* and \(\mathbb{R}^d\)-loop, then \(G\) is called a simple \(\mathbb{R}^d\)-hypergraph.*
Unless otherwise specified, all \(\mathbb{R}^d\)-hypergraphs mentioned hereafter will be simple \(\mathbb{R}^d\)-hypergraphs. Analogous to the definition of incident and adjacent in graph theory, we can define the notions of incident and adjacent in \(\mathbb{R}^d\)-hypergraphs.
Definition 8 (neighbour). Let \(G\) be an \(\mathbb{R}^d\)-hypergraph, and an \([i]\)-vertex (\(i\)-dimensional simplexoid) of \(G\) is denoted by \(a_i\), and the set of \(i\)-vertex* of \(G\) is denoted by \[A_i(G)= \{a_i| a_i \;is \;a \;simplexoid \;of \;G \;of \;dimension \;i \}.\] For convenience, we use \(V(G)\) to denote the \(0\)-vertex set of \(G\), use \(V(a_i)\) to denote the \([0]\)-vertex set of \(a_i\).*
Definition 9 (incident and adjacent). Let \(u\) and \(v\) be \([0]\)-vertices, we say \(u\) is adjacent to \(v\) if there exists \(a_{d-1} \in A_{d-1}(G)\) such that \(u, v \in V(a_{d-1})\). The set of all \([0]\)-vertices that adjacent to \(u\) is denoted by \(N_G(u)\), the degree of \(u\) is denoted by \(d_G(u)= |N_G(u)|\).
Let \(a_i\) be an \([i]\)-vertex, and \(a_j\) be a \([j]\)-vertex (\(i>0\) and \(i\leq j\)). We say \(a_i\) is incident to \(a_j\) (or \(a_j\) is incident to \(a_i\)) if \(i< j\) and \(a_i\cap a_j= a_i\); we say \(a_i\) is adjacent to \(a_j\) if \(i= j\) and \(a_i\cap a_j\) is an \([i-1]\)-dimensional simplexoid. The set of all \([j]\)-dimensional simplexoid incident (adjacent) to \(a_i\) is denoted by \(N_{Gj}(a_i)\). We say \(d_{Gj}(a_i)= |N_{Gj}(a_i)|\) is the \(j\)-dimensional degree* of \(a_i\).*
Definition 10 (merging of multiple simplexoids). Given two multiple simplexoids \(x\) and \(y\), merging of \(x\) and \(y\) refers to combining \(x\) and \(y\) into a new simplexoid \(z\), and all simplexoids incident with \(x\) or \(y\) are incident with \(z\).
Definition 11 (simplexoid deletion). Given an \(\mathbb{R}^d\)-hypergraph \(G\), there are two natural ways of deriving smaller hypergraphs from \(G\). If \(e\) is a \((d-1)\)-dimensional simplexoid of \(G\), we may obtain a hypergraph with \(m-1\) \((d-1)\)-dimensional simplexoids by deleting \(e\) from \(G\) but leaving the vertices and the remaining simplexoids intact. The resulting hypergraph is denoted by \(G\backslash e\). Similarly, if \(v\) is a vertex or an \(i\)-dimensional simplexoid (\(i<d-1\)) of \(G\), we may obtain a hypergraph by deleting from \(G\) the vertex (or simplexoid) \(v\) together with all the \((d-1)\)-dimensional simplexoids incident with \(v\). The resulting hypergraph is denoted by \(G - v\) or \(G\backslash v\).
Definition 12 (simplexoid contraction). To contract a simplexoid \(e\) of an \(\mathbb{R}^d\)-hypergraph \(G\) is to delete the simplexoid and then identify its incident vertices. The resulting hypergraph is denoted by \(G/ e\). It is important to note that, during the process of simplexoid contraction, if multiple simplexoids emerge, we need to merge them to ensure that the resulting hypergraph is a simple \(\mathbb{R}^d\)-hypergraph.
Definition 13 (\(\mathbb{R}^d\)-embedding). Let \(G\) be a \(d\)-uniform-topological hypergraph, an \(\mathbb{R}^d\)-embedding \(G'\) of \(G\) can be regarded as a hypergraph isomorphic to \(G\) and is embedded in \(\mathbb{R}^d\).
We conclude this section with a brief summary. The \(\mathbb{R}^d\)-hypergraph can be considered as an extension of the definition of the planar graph into higher-dimensional space or as a special type of CW complex. Whether it is a general \(\mathbb{R}^d\)-hypergraph, an \(\mathbb{R}^d\)-hypergraph, or a non-\(\mathbb{R}^d\)-hypergraph, they are essentially special cases of CW complex.
A general \(\mathbb{R}^d\)-hypergraph requires that this CW complex has a trivial \(i\)-th homotopy group for \(i\in \{1,2,3,...,d-2\}\). An \(\mathbb{R}^d\)-hypergraph requires that this CW complex has a trivial \(i\)-th homotopy group for \(i\in \{1,2,3,...,d-2\}\), and can be embedded in \(\mathbb{R}^d\). A non-\(\mathbb{R}^d\)-hypergraph requires that this CW complex has a trivial \(i\)-th homotopy group for \(i\in \{1,2,3,...,d-2\}\) and cannot be embedded in \(\mathbb{R}^d\). A thorough understanding of these definitions lays a solid foundation for subsequent proofs.
3 Closed \(\mathbb{R}^d\)-hypergraph and triangulated \(\mathbb{R}^d\)-hypergraph (\(d\geq 3\))↩︎
A simple connected plane graph where all faces have degree three is called a plane triangulation, or simply a triangulation. This section extends the concept of triangulation to higher-dimensional spaces. It is well known that for any planar graph, edges can be added to eliminate all pendant edges. Without pendant edges, a planar graph admits an ear decomposition. As illustrated in Figure 1, the original graph can be reconstructed by starting from a cycle \(v_1v_2v_3v_4v_5v_1\) and iteratively attaching paths \(v_1v_6v_7v_8v_3\) and \(v_8v_9v_{10}v_{11}v_{12}v_4\). As shown in Figure 2, if we generalize the initial cycle in the ear decomposition of a planar graph to a \(d\)-dimensional sphere \(S^d\), and generalize the paths to \(d\)-dimensional balls, the associated concepts can be extended to higher-dimensional spaces.
Note that every planar graph admits a triangulation; that is, we can add edges such that each face of the graph becomes a triangle. Analogously, in higher dimensions, we can add simplexoids to an \(\mathbb{R}^d\)-hypergraph \(G\) so that each maximal connected component in the set \(\mathbb{R}^d\backslash G\) is homeomorphic to a \(d\)-dimensional simplexoid. The simplexoids in \(\mathbb{R}^d\)-hypergraphs can be divided into two categories which are similar to the pendant edge and non-pendant edge in planar graphs. Next, we will extend the concept of pendant edges to higher-dimensional spaces.
Definition 14 (pendant simplexoid). Let \(T\) be a \((d-1)\)-dimensional simplexoid of an \(\mathbb{R}^d\)-hypergraph \(K\), \(N_{K(d-2)}(T)\) represent the set of all \((d-2)\)-dimensional simplexoids that are incident to \(T\). If \(\forall J \in N_{K(d-2)}(T)\), there exists a \((d-1)\)-dimensional simplexoid \(T' \subseteq K\) such that \(J= T \cap T'\), then \(T\) is called non-pendant simplexoid, if not \(T\) is called pendant simplexoid.
Similarly, following the definitions of \(2\)-connected planar graphs and triangulated planar graphs, we can introduce the notions of closed \(\mathbb{R}^d\)-hypergraphs and triangulated \(\mathbb{R}^d\)-hypergraphs.
Definition 15 (closed \(d\)-uniform topological hypergraph). The \(d\)-uniform-topological hypergraph* without pendant simplexoid is called the closed \(d\)-uniform topological hypergraph.*
Definition 16 (closed \(\mathbb{R}^d\)-hypergraph). Let \(K\) be an \(\mathbb{R}^d\)-hypergraph, then \(K\) is called a closed \(\mathbb{R}^d\)-hypergraph* if \(K\) contains no pendant simplexoid.*
Definition 17 (triangulated \(d\)-uniform topological hypergraph). The \((d-1)\)-skeleton of a closed \(\mathbb{R}^{d+1}\)-hypergraph is referred to as a triangulated \(d\)-uniform topological hypergraph.
Note that the triangulated \(d\)-uniform topological hypergraph is a special case of the closed \(d\)-uniform topological hypergraph since there is no pendant simplexoid in it.
Definition 18 (triangulated \(\mathbb{R}^d\)-hypergraph). Let \(K\) be a triangulated \(d\)-uniform topological hypergraph, then \(K\) is called the triangulated \(\mathbb{R}^d\)-hypergraph* if \(K\) can be embedded in \(\mathbb{R}^d\).*
Lemma 4. Let \(K\) be a closed \(\mathbb{R}^d\)-hypergraph. Then every connected component of the complement \(S^d\setminus K\) is homeomorphic to the open \(d\)-ball.
Proof. Note that the generalized Schoenflies theorem (Lemma 5) guarantees that no pathological cases like Alexander’s horned sphere can arise in our proof.
Since \(K\) can be viewed as a CW complex, the complement \(S^d\setminus K\) is partitioned into \(d\)-dimensional components \(D_1,D_2,...,D_x\). If there exists a \(D_i\in \{D_1,D_2,...,D_x\}\) such that \(D_i\) is not homeomorphic to the open \(d\)-ball, then the boundary of \(D_i\) (denoted by \(\partial(D_i)\)) is not \(S^{d-1}\) by Lemma 5, furthermore, \(\partial(D_i)\) is not \((d-2)-connected\). Therefore, there exists a \(j\)-dimensional sphere \(S^j\subseteq \partial(D_i)\) (\(j\leq d-2\)) such that \(S^j\) cannot continuously deform into a base point. On the other hand, it is clear that \(S^j \subseteq K\), which implies that \(K\) is not \((d-2)\)-connected, a contradiction. ◻
Lemma 4 implies that a closed \(\mathbb{R}^d\)-hypergraph can be regarded as a union of internally disjoint \((d-1)\)-dimensional spheres.
Lemma 5 (generalized Schoenflies theorem [12]). Let \(\varphi\colon S^{n-1} \hookrightarrow S^n\) be a topological embedding in a locally flat way (that is, the embedding extends to that of a thickened sphere) with \(n \geq 2\), and let \(A\) be the closure of a component of \(S^n \setminus \varphi(S^{n-1})\), then \(A\) is homeomorphic to the closed \(n\)-dimensional ball \(D^n\).
4 Bridges↩︎
In this section, we aim to establish some lemmas of bridge in higher-dimensional spaces. Let \(H\) be a proper subgraph of a connected \(\mathbb{R}^d\)-hypergraph \(G\). The set \(A_{d-1}(G) \backslash A_{d-1}(H)\) may be partitioned into classes as follows. For each component \(F\) of \(G[V(G)-V(H)]\), there is a class consisting of the \(d\)-dimensional simplexoids of \(F\) together with the \(d\)-dimensional simplexoids linking \(F\) to \(H\). Each remaining \(d\)-dimensional simplexoid \(e\) defines a singleton class \(\{e\}\). The subgraphs of \(G\) induced by these classes are the bridges of \(H\) in \(G\). It follows immediately from this definition that bridges of \(H\) can intersect only in \(i\)-dimensional simplexoids of \(H\) with \(i\leq d-2\), and that any two vertices of a bridge of \(H\) are connected by a path in the bridge that is internally disjoint from \(H\).
For a bridge \(B\) of \(H\), the projection of \(B\) is denoted by \(p(B)= B \cap H\); the elements of \(V(B \cap H)\) are called its vertices of attachment to \(H\), the remaining vertices of \(B\) are its internal vertices. A bridge is trivial if it has no internal vertices. A bridge with \(k\) vertices of attachment is called a \(k\)-bridge. Two bridges with the same vertices of attachment and same projection are equivalent bridges.
We are concerned here with bridges of \((d-1)\)-sphere, and all bridges are understood to be bridges of a given \((d-1)\)-sphere \(S^{d-1}\). Thus, to avoid repetition, we abbreviate ‘bridge of \(S^{d-1}\)’ to ‘bridge’ in the coming discussion.
Lemma 6. Let \(G\) be an \(\mathbb{R}^d\)-hypergraph, \(B\) be a bridge of \((d-1)\)-sphere \(S'\), the projection of \(B\) which is denoted by \(p(B)= B \cap S^{d-1}\) is a connected \(\mathbb{R}^{d-1}\)-hypergraph.
Proof. By Definition 4, we only need to prove that the \(i\)-th homotopy group of \(p(B)\) is trivial for \(i\in \{1,2,3,...,d-3\}\).
Lemma 4 implies that every closed \(\mathbb{R}^d\)-hypergraph can be regarded as a union of \((d-1)\)-dimensional spheres \(S^{d-1}\). Let \(S' \cup B = S_1 \cup S_2 \cup \dots \cup S_x\), where each \(S_i\) \((i \in \{1, 2, \dots, x\})\) is a \((d-1)\)-dimensional sphere. Without loss of generality, we assume that \(S' = S_1\).
It is easy to observe that for each \(S_i \in \{ S_2, S_3, \dots, S_x \}\), the intersection \(D_i = S_i \cap S'\) is either empty or an \(i\)-dimensional ball (\(i\leq d-1\)). We only need to consider the case when \(i= d-1\), otherwise there exists \(\{S_{x_1}, S_{x_2}, ...,S_{x_s}\}\subseteq \{ S_2, S_3, \dots, S_x \}\) such that for all \(S_j\in \{S_{x_1}, S_{x_2}, ...,S_{x_s}\}\), \(S_j \cap S'\) is a \((d-1)\)-dimensional ball and \(S_i \cap S' \subseteq \bigcup_{S_j\in \{S_{x_1}, S_{x_2}, ...,S_{x_s}\}}(S_j \cap S')\).
In case when \(D_i = S_i \cap S'\) is a \((d-1)\)-dimensional ball, the boundary of \(D_i\), denoted \(\partial(D_i)\), is a \((d-2)\)-dimensional sphere, note that \(p(B) = \bigcup_{i \in \{2, 3, \dots, x\}} \partial(D_i)\).
Since \(p(B)\) can be viewed as a union of finitely many \((d-2)\)-dimensional spheres, and each pair of spheres intersects only along their boundaries (i.e., for all \(i, j \in \{2, 3, \dots, x\}\), the intersection \(D_i \cap D_j\) is either empty or a contractible disk), it follows from Lemma 3 and Lemma 4 that \(\pi_k(p(B)) \cong \pi_k(S^{d-2})\) for all \(k\leq d-3\). Therefore, the \(i\)-th homotopy group of \(p(B)\) is trivial for \(i\in \{1,2,3,...,d-3\}\). ◻
The projection of a \(k\)-bridge \(B\) with \(k\geq d-1\) effects a partition of \(S^{d-1}\) into \(r\) disjoint segments, called the segments of \(B\). Two bridges avoid each other if all the vertices of attachment of one bridge lie in a single segment of the other bridge; otherwise, they overlap.
Two bridges \(B\) and \(B'\) are skew if \(p(B)\) contains a \((d-2)\)-sphere \(C(B)\) as a subgraph which effects a partition of \(S^{d-1}\) into two disjoint segments \(\{R_1, R_2\}\), and there are distinct vertices \(u,v\) in vertices of attachment of \(B'\) such that \(u\) and \(v\) are in different segment of \(\{R_1, R_2\}\), note that there is a \(uv\)-path \(P(u,v)\) in \(S^{d-1}\) such that \(P(u,v)\cap C(B) \neq \phi\) by Lemma 6 and Jordan-Brouwer Separation Theorem (Lemma 19).
We give an example of skew for \(S^2\). As shown in Figure 3, both \(u\) and \(v\) are in the inner region of \(S^2\), the bridge induced by \(\{u,u_1, u_2,...,u_5\}\) is denoted by \(B_1\), the bridge induced by \(\{v,v_1, v_2\}\) is denoted by \(B_2\). It is obvious that \(B_1\) effects a partition of \(S^2\) into two disjoint segments (two hemispheres), and \(v_1\) and \(v_2\) lie in different segments.
Lemma 7. Overlapping bridges of a closed \(\mathbb{R}^d\)-hypergraph are either skew or else equivalent \((d+1)\)-bridges.
Proof. Suppose that bridges \(B\) and \(B'\) overlap. Clearly, each of them must have at least \(d\) vertices of attachment. If either \(B\) or \(B'\) is a \(d\)-bridge, it is easily verified that they must be skew (two equivalent \(d\)-bridges cannot overlap). We may therefore assume that both \(B\) and \(B'\) have at least \((d+1)\) vertices of attachment.
If \(B\) and \(B'\) are not equivalent bridges, then all the vertices of attachment of one bridge cannot lie in a single segment of the other bridge. Without loss of generality, let \(C(B)\subseteq p(B)\) be a \((d-2)\)-sphere which effects a partition of \(S^{d-1}\) into \(2\) disjoint segments \(\{R_1, R_2\}\), then there exist distinct vertices \(u',v'\) in vertices of attachment of \(B'\) such that \(u'\) and \(v'\) are in different segment of \(\{R_1, R_2\}\). It follows that \(B\) and \(B'\) are skew.
If \(B\) and \(B'\) are equivalent \(k\)-bridges, then \(k\geq d+1\). If \(k\geq d+2\), \(B\) and \(B'\) are skew by Lemma 8; if \(k=d+1\), they are equivalent \((d+1)\)-bridges. ◻
Lemma 8. Let \(G\) be an \(\mathbb{R}^d\)-hypergraph which is homeomorphic to \(S^{d-1}\) with \(|V(G)|\geq d+2\), then there is a subgraph \(C\) of the \((d-2)\)-skeleton of \(G\) which is homeomorphic to \((d-2)\)-sphere that effects a partition of \(S^{d-1}\) into \(2\) disjoint segments \(\{R_1, R_2\}\), and there are distinct vertices \(u',v'\) in vertices of attachment of \(G\) such that \(u'\) and \(v'\) are in different segment of \(\{R_1, R_2\}\).
Proof. Firstly, we prove that there exists a vertex \(v'\in V(G)\) such that \(d_{G0}(v')\leq |V(G)|-2\), if not, we know that \(d_{G0}(v)=|V(G)|-1\) for every vertex \(v\in V(G)\), which implies that \(G\) is a complete \(d\)-uniform-topological hypergraph (see Definition 22). It is impossible since \(G\) is homeomorphic to \(S^{d-1}\).
Let \(N_{G0}(v')\) be the neighbors of \(v'\), then \(G[N_{G0}(v')]\) is homeomorphic to a \((d-2)\)-sphere by Lemma 13 and 9, note that \(G[N_{G0}(v')]\) effects a partition of \(S^{d-1}\) into \(2\) disjoint segments \(\{R_1, R_2\}\), without loss of generality, let \(v'\in R_1\).
It is easy to verify that \(V(G)\backslash [N_{G0}(v') \cup \{v'\}] \neq \phi\) since \(|V(G)|\geq d+2\), let \(u'\in V(G)\backslash [N_{G0}(v') \cup \{v'\}]\), it follows that \(u' \in R_2\). ◻
Lemma 9. In a closed \(\mathbb{R}^d\)-hypergraph \(G\), if \(G\) is homeomorphic to \(S^{d-1}\), the \(1\)-skeleton of \(G\) is \(d\)-connected.
Proof. Suppose that the 1-skeleton of \(G\) (denoted by \(G_0\)) is not \(d\)-connected. Then there exists a \((d-1)\)-cut \(\{v_1, v_2, \ldots, v_{d-1}\}\) such that removing these vertices from \(G_0\) disconnects the graph. Let \(X\) and \(Y\) be two connected components of the resulting graph.
Contract \(X\) into a single vertex \(x\), and contract \(Y\) into a single vertex \(y\). Denote the resulting graph after contraction by \(G'\). Since \(G'\) becomes disconnected after removing the set \(\{v_1, v_2, \ldots, v_{d-1}\}\), its connectivity is strictly less than \(d\).
On the other hand, because \(G_0\) is composed of \((d-1)\)-dimensional simplexoids and is homeomorphic to \(S^{d-1}\), the 1-skeleton of \(G'\) must be the complete graph \(K_{d+1}\). It follows that the connectivity of \(G'\) is \(d\), leading to a contradiction. ◻
Lemma 10. In a closed \(\mathbb{R}^d\)-hypergraph \(G\), the \(1\)-skeleton of \(G\) is \(d\)-connected.
Proof. Let \(u\) and \(v\) be any two vertices in \(G\). Let \(S^{d-1}\) be a \({d-1}\)-dimensional sphere containing both \(u\) and \(v\). By Lemma 9, the \(1\)-skeleton of \(S^{d-1}\) must contain \(d\) internally disjoint paths connecting \(u\) and \(v\).
Therefore, the \(1\)-skeleton of \(G\) must be \(d\)-connected. ◻
5 Hyper ear decomposition↩︎
In this section, we aim to establish some lemmas of ear decomposition in higher-dimensional spaces. Let \(K\) be an \(\mathbb{R}^d\)-hypergraph whose \(1\)-skeleton is \(d\)-connected. Note that the \(d\)-connected closed \(\mathbb{R}^d\)-hypergraph contains a subgraph \(G_0\) which is homeomorphic to \(S^{d-1}\). We describe here a simple recursive procedure for generating any such hypergraph starting with an arbitrary \((d-1)\)-sphere of the \(\mathbb{R}^d\)-hypergraph.
Definition 19 (hyper ear). Let \(F\) be a subgraph of an \(\mathbb{R}^d\)-hypergraph \(G\). A hyper ear* of \(F\) in \(G\) is a nontrivial \((d-1)\)-ball in \(G\) whose boundary lies in \(F\) but whose internal vertices do not.*
Definition 20 (hyper ear decomposition). A nested sequence of a closed \(\mathbb{R}^d\)-hypergraph is a sequence \((G_0,G_1,\ldots,G_k)\) of \(\mathbb{R}^d\)-hypergraphs such that \(G_i\subseteq G_{i+1}\), \(0\leq i\leq k\). A hyper ear decomposition* of a \(d\)-connected closed \(\mathbb{R}^d\)-hypergraph \(G\) is a nested sequence \((G_0,G_1,\ldots,G_k)\) of \(d\)-connected subgraphs of \(G\) such that:*
\(G_0\) is homeomorphic to \(S^{d-1}\).
\(G_{i+1}= G_i \cup P_i\) where \(P_i\) is a hyper ear of \(G_i\) in \(G\) for \(0\leq i\leq k\).
\(G_k=G\).
Lemma 11. The closed \(\mathbb{R}^d\)-hypergraph \(G\) with \(|V(G)|\geq d+1\) has a hyper ear decomposition.
Proof. On the one hand, the \(1\)-skeleton of \(G\) is \(d\)-connected by Lemma 10. On the other hand, since \(G\) contains at least \((d+1)\) vertices, it must contain at least one \((d-1)\)-dimensional sphere \(S^{d-1}\).
Since \(G\) is homeomorphic to the union of a finite collection of \((d-1)\)-spheres by Definition 4 and Lemma 4, it is obvious that \(G\) has a hyper ear decomposition. ◻
Lemma 12. In a closed \(\mathbb{R}^d\)-hypergraph \(G\) with \(|V(G)|\geq d+1\), if the \(1\)-skeleton of \(G\) is \(d\)-connected, then each maximal connected region or \(\mathbb{R}^d\backslash G\) is bounded by a \((d-1)\)-sphere.
Proof. Note that \(G\) has a hyper ear decomposition by Lemma 11. Consider an ear decomposition \((G_0,G_1,...,G_k)\) of \(G\), where \(G_0\) is homeomorphic to \(S^{d-1}\), \(G_k= G\), and, for \(0\leq i \leq k-2\), \(G_{i+1}= G_i \cup P_i\) is a \(d\)-connected subgraph of \(G\), where \(P_i\) is an ear of \(G_i\) in \(G\). Since \(G_0\) is homeomorphic to \(S^{d-1}\), the two maximal connected regions of \(G_0\) are clearly bounded by a \((d-1)\)-sphere. Assume, inductively, that all maximal connected regions of \(G_i\) are bounded by \((d-1)\)-spheres, where \(i\geq 0\). Because \(G_{i+1}\) is a \(d\)-connected \(\mathbb{R}^d\)-hypergraph, the ear \(P_i\) of \(G_i\) is contained in some maximal connected region \(f\) of \(G_i\). Each region of \(G_i\) other than \(f\) is a region of \(G_{i+1}\) as well, and so, by the induction hypothesis, is bounded by a \((d-1)\)-sphere. On the other hand, the region \(f\) of \(G_i\) is divided by \(P_i\) into two regions of \(G_{i+1}\), and it is easy to see that these regions are also bounded by \((d-1)\)-spheres. ◻
Lemma 13. In a closed \(\mathbb{R}^d\)-hypergraph \(G\), if the \(1\)-skeleton of \(G\) is \((d+1)\)-connected, the neighbors of any vertex lie on a common \((d-1)\)-sphere.
Proof. Let \(v\) be a vertex of \(G\), then the \(1\)-skeleton of \(G-v\) is \(d\)-connected, so each maximal connected region of \(G-v\) is bounded by a sphere by Lemma 12. If \(f\) is the region of \(G-v\) in which the vertex \(v\) was situated, the neighbors of \(v\) lie on its bounding sphere \(\partial(f)\). ◻
6 Recognizing \(\mathbb{R}^d\)-hypergraph↩︎
We extend the definition of \(S\)-component for graphs to higher-dimensional spaces before proving our main result.
6.1 \(S\)-component↩︎
Definition 21 (\(S\)-component). Let \(G\) be a connected \(d\)-uniform topological hypergraph which is not complete, let \(S\) be a vertex cut of \(G\), and let \(X\) be the vertex set of a component of \(G-S\). The subgraph \(H\) of \(G\) induced by \(S\cup X\) is called an \(S\)-component of \(G\). In the case where \(G\) is a closed \(d\)-uniform topological hypergraph, the \(1\)-skeleton of \(G\) is \(d\)-connected, and \(S := \{x_1,x_2, ..., x_d\}\) is a \(d\)-vertex cut of \(G\), we find it convenient to modify each \(S\)-component by adding a new \((d-1)\)-dimensional simplexoid with vertex set \(\{x_1,x_2, ..., x_d\}\). We refer to this simplexoid as a marker simplexoid and the modified \(S\)-components as marked \(S\)-components. The set of marked \(S\)-components constitutes the marked \(S\)-decomposition of \(G\). \(G\) can be recovered from its marked \(S\)-decomposition by taking the union of its marked \(S\)-components and deleting the marker edge.
As shown in Figure 4, \(S := \{x_1,x_2, x_3\}\) be a 3-cut of an \(\mathbb{R}^3\)-hypergraph \(G\), we provide an example of the \(S\)-decomposition and marked \(S\)-decomposition of an \(\mathbb{R}^3\)-hypergraph. The only difference between \(S\)-decomposition and marked \(S\)-decomposition is that marked \(S\)-decomposition must contain a simplexoid with vertex set \(S := \{x_1,x_2, x_3\}\). If this simplex does not exist in the original hypergraph, it needs to be added during the construction.
We need to establish some lemmas before proving our main results.
Lemma 14. Let \(G\) be a closed \(\mathbb{R}^d\)-hypergraph with a \(d\)-vertex cut \(\{x_1,x_2, ..., x_d\}\), then each marked \(\{x_1,x_2, ..., x_d\}\)-component of \(G\) is isomorphic to a minor of \(G\).
Proof. Let \(H\) be an \(\{x_1,x_2, ..., x_d\}\)-component of \(G\), with marker simplexoid \(e\). Let \(H'\) be another \(\{x_1,x_2, ..., x_d\}\)-component of \(G\), with marker simplexoid \(e\), then there is a \((d-1)\)-ball \(B\) such that \(B\subseteq H'\) and \(B\cup e\) is a \((d-1)\)-sphere by Lemma 11. It is easy to verify that \(H\) is isomorphic to a minor of \(G\) by contract \(H'\) into a single simplexoid \(e\). ◻
Lemma 15. Let \(G_1\) and \(G_2\) be closed \(\mathbb{R}^d\)-hypergraphs whose intersection is isomorphic to an \(\mathbb{R}^{d-1}\)-hypergraph \(K_d\) with \(V(K_d)= \{x_1,x_2, ..., x_d\}\) and \(E(K_d)= \{a_i|a_i \text{ is a (d-2)-dimensional simplexoid with vertex set }V(K_d)\backslash \{x_i \} \text{, }(i\in \{1,2,...,d\}) \}\), then \(G_1\cup G_2\) is a closed \(\mathbb{R}^d\)-hypergraph.
Proof. Let \(H\) be a hyperplane, \(V(K_d)\subseteq H\). At this point, the hyperplane \(H\) divides \(\mathbb{R}^d\) into two disconnected regions, denoted by \(R_1\) and \(R_2\), respectively. We embed \(G_1\) into \(R_1\) and \(G_2\) into \(R_2\) in such a way that \(G_1\) and \(G_2\) intersect only at \(V(K_d)\).
By contradiction, suppose the \(i\)-th homotopy group of \(G_1 \cup G_2\) is nontrivial for some \(i \in \{1, 2, \ldots, d-2\}\), then there must exist an \(i\)-sphere \(S^i\) that cannot be continuously contracted to the base point. If \(S^i\) belongs to either \(G_1\) or \(G_2\), then it can be continuously contracted to the base point, which leads to a contradiction. Therefore, \(S^i\) must intersect both \(G_1\) and \(G_2\). Let \(S^i\cap G_1= L_1\) and \(S^i\cap G_2= L_2\), respectively. We first transform \(L_1\) into \(L_3\) by homotopy, such that \(L_3\) belongs to \(H\). It is easy to verify that \(L_2\) and \(L_3\) belong to \(G_2\), thus they can be continuously contracted to the base point. By combining the two homotopy transformations, we obtain that \(S^i\) can be continuously contracted to the base point, a contradiction. In conclusion, the assumption is invalid, and the theorem is proven. ◻
Lemma 16. Let \(G\) be an \(\mathbb{R}^d\)-hypergraph with a \(d\)-vertex cut \(\{x_1,x_2, ..., x_d\}\), then \(G\) is a closed \(\mathbb{R}^d\)-hypergraph if and only if each of its marked \(\{x_1,x_2, ..., x_d\}\)-components is a closed \(\mathbb{R}^d\)-hypergraph.
Proof. Suppose, first, that \(G\) is a closed \(\mathbb{R}^d\)-hypergraph. By Lemma 14, each marked \(\{x_1,x_2, ..., x_d\}\)-component of \(G\) is isomorphic to a minor of \(G\), hence is closed \(\mathbb{R}^d\)-hypergraph.
Conversely, suppose that \(G\) has \(k\) marked \(\{x_1,x_2, ..., x_d\}\)-components each of which is a closed \(\mathbb{R}^d\)-hypergraph. Let \(e\) denote their common marker simplexoid. Applying Lemma 15 and induction on \(k\), it follows that \(G + e\) is a closed \(\mathbb{R}^d\)-hypergraph, hence so is \(G\). ◻
By Lemma 16, we know that to prove a closed \(\mathbb{R}^d\)-hypergraph can be embedded in \(\mathbb{R}^d\), it is sufficient to show that all of its marked \(\{x_1,x_2, ..., x_d\}\)-components can be embedded in \(\mathbb{R}^d\).
6.2 Connectivity↩︎
Before proving Theorem 1, we need a lemma regarding connectivity.
Lemma 17. Let \(G\) be a \((d+1)\)-connected graph on at least \((d+2)\) vertices, then \(G\) contains an edge \(e\) such that \(G/e\) is \((d+1)\)-connected.
Proof. Suppose that the theorem is false. Then, for any edge \(e = xy\) of \(G\), the contraction \(G/e\) is not \((d+1)\)-connected. By Lemma 18, there exists vertex set \(\{z_1, z_2, ..., z_{d-1}, w\}\) such that \(\{z_1, z_2, ..., z_{d-1}, w\}\) is a \(d\)-vertex cut of \(G\).
Choose the edge \(e\) and the vertex set \(\{z_1, z_2, ..., z_{d-1}, w\}\) in such a way that \(G - \{x,y,z_1, z_2, ..., z_{d-1}\}\) has a component \(F\) with as many vertices as possible. Consider the graph \(G - \{z_1\}\). Because \(G\) is \((d+1)\)-connected, \(G- \{z_1\}\) is \(d\)-connected. Moreover \(G-\{z_1\}\) has the \(d\)-vertex cut \(\{x,y, z_2, ..., z_{d-1}\}\). It follows that the \(\{x,y, z_2, ..., z_{d-1}\}\)-component \(H = G[V (F) \cup \{x,y, z_2, ..., z_{d-1}\}]\) is \(d\)-connected.
Let \(u\) be a neighbour of \(z_1\) in a component of \(G - \{x,y,z_1, z_2, ..., z_{d-1}\}\) different from \(F\). Since \(f = zu\) is an edge of \(G\), and \(G\) is a counterexample to Lemma 17, there is a vertex set \(\{v_1, v_2, ..., v_{d-1}\}\) such that \(\{z,u, v_1, v_2, ..., v_{d-1}\}\) is a \((d+1)\)-vertex cut of \(G\), too. (The vertices \(\{v_1, v_2, ..., v_{d-1}\}\) might or might not lie in \(H\).) Moreover, because H is \(d\)-connected, \(H-\{v_1, v_2, ..., v_{d-1}\}\) is connected (where, if there exists \(v_i\in \{v_1, v_2, ..., v_{d-1}\}\) such that \(v_i \in V (H)\), we set \(H- v_i = H\)), and thus is contained in a component of \(G - \{z,u, v_1, v_2, ..., v_{d-1}\}\). But this component has more vertices than \(F\) (because \(H\) has \(d\) more vertices than \(F\)), contradicting the choice of the edge \(e\) and the vertex \(v\). ◻
Lemma 18. Let \(G\) be a \((d+1)\)-connected graph on at least \((d+2)\) vertices, and let \(e = xy\) be an edge of \(G\) such that \(G/e\) is not \((d+1)\)-connected. Then there exists a vertex \(z\) such that \(\{x,y, z_1, z_2, ..., z_{d-1}\}\) is a \((d+1)\)-vertex cut of \(G\).
Proof. Let \(\{z_1, z_2, ..., z_{d-1}, w\}\) be a \(d\)-vertex cut of \(G/e\). At least \(d-1\) of these \(d\) vertices, say \(\{z_1, z_2, ..., z_{d-1}\}\), is not the vertex resulting from the contraction of \(e\). Set \(F = G- \{z_1, z_2, ..., z_{d-1}\}\). Because \(G\) is \((d+1)\)-connected, \(F\) is certainly \(2\)-connected. However \(F/e = (G - \{z_1, z_2, ..., z_{d-1}\}) /e = (G/e) - \{z_1, z_2, ..., z_{d-1}\}\) has a cut vertex, namely \(w\).
If \(w\) is not the vertex resulting from the contraction of \(e\), then \(\{z_1, z_2, ..., z_{d-1}, w\}\) must be a \(d\)-vertex cut of \(G\), a contradiction. Hence \(w\) must be the vertex resulting from the contraction of \(e\). Therefore \(G - \{x,y,z_1, z_2, ..., z_{d-1}\} = (G/e) - \{z_1, z_2, ..., z_{d-1},w\}\) is disconnected, in other words, \(\{x,y,z_1, z_2, ..., z_{d-1}\}\) is a \((d+1)\)-vertex cut of \(G\). ◻
6.3 Anti-\(d\)-dimension minor↩︎
The following proof demonstrates that there is a conclusion that holds in \(\mathbb{R}^d\) that similar to Wagner’s theorem. It is necessary to generalize the concepts of complete graphs and complete bipartite graphs to higher-dimensional spaces.
Definition 22 (complete \(i\)-uniform-topological hypergraph \(K_n^i\)). Let \(G\) be an \(i\)-uniform-topological hypergraph, \(V\) be the vertex set of \(G\) with order \(n\), \(\mathscr{V}(i)\) be the collection of all subsets of \(V\) containing \(i\) elements. If for any \(V_j\in \mathscr{V}(i)\), there exists a simplexoids \(T\) in \(G\) such that \(V(T)= V_j\), then we call \(G\) a complete \(i\)-uniform-topological hypergraph, which is denoted by \(K_n^i\). (Figure 5 is an example of \(K_4^3\). )
Definition 23 (complete bipartite \(i\)-uniform-topological hypergraph \(K_{p,q}^i\)). Let \(G\) be an \(i\)-uniform-topological hypergraph, \(V\) be the vertex set of \(G\), \(V(A:B)\) be a partition of \(V\) in which \(A=\{a_1, a_2, ..., a_p\}\) and \(B=\{b_1, b_2, ..., b_q\}\). If \(G\) satisfies the following properties, we call \(G\) a complete bipartite \(i\)-uniform-topological hypergraph, which is denoted by \(K_{p,q}^i\). (An example of \(K_{2,4}^3\) is shown in Figure [new6].)
\(G[B]\) is a complete \(i\)-uniform-topological hypergraph \(K_q^{i-1}\).
For any \(T_j\in A_{i-2}(G[B])\) and \(a_k\in A\), there exists a simplexoid \(T\) in \(G\) such that \(V(T)= V(T_j)\cup \{a_k\}\).
Next, we use the Jordan-Brouwer Separation Theorem to prove Lemma 20 and 21.
Lemma 19 (Jordan-Brouwer Separation Theorem [10]). Let \(X\) be a \(d\)-dimensional topological sphere in the \((d+1)\)-dimensional Euclidean space \(\mathbb{R}^{d+1}\) (\(d > 0\)), i.e. the image of an injective continuous mapping of the \(d\)-sphere \(S^d\) into \(\mathbb{R}^{d+1}\), then the complement \(Y\) of \(X\) in \(\mathbb{R}^{d+1}\) consists of exactly two connected components. One of these components is bounded (the interior) and the other is unbounded (the exterior). The set \(X\) is their common boundary.
Lemma 20. \(K_{d+3}^d\) is a non-\(\mathbb{R}^d\)-hypergraph.
Proof. Suppose to the contrary that \(K_{d+3}^d\) is an \(\mathbb{R}^d\)-hypergraph.
Let \(V(K_{d+3}^d)= \{v_1, v_2, ... v_{d+2}, v_{d+3}\}\). Let \(\mathscr{V}_{d+2}^{d+1}\) be the collection of all subsets of \(V(K_{d+3}^d)\backslash \{v_{d+3}\}\) containing \((d+1)\) elements.
Note that for any \(V_i\in \mathscr{V}_{d+2}^{d+1}\), \(K_{d+3}^d[V_i]\) is homeomorphic to \(S^{d-1}\).
Let \(V_i= V(K_{d+3}^d)\backslash \{v_{d+3}, v_i\}\). We assume that \(K_{d+3}^d[V(K_{d+3}^d)\backslash \{v_{d+3}\}]\) has already been embedded in \(\mathbb{R}^d\). By Lemma 19, each \(K_{d+3}^d[V_i]\) will divide \(\mathbb{R}^d\) into two disconnected regions, with one of the regions being empty. We designate the non-empty region as the external region of \(K_{d+3}^d[V_i]\) and the empty region as the internal region. Let \(In(i)\) be the internal region corresponding to \(K_{d+3}^d[V_i]\) and \(Ex(i)\) be the external region corresponding to \(K_{d+3}^d[V_i]\). (As shown in Figure 6, when embedded \(K_{d+3}^d\) in \(\mathbb{R}^d\), it is obvious that line \(v_1v_6\) intersects with \(K_{d+3}^d[V_i]\) at least at one point. )
Without loss of generality, we assume that \(v_{d+3}\) is in \(In(1)\), and it follows that \(v_1\) is in \(Ex(1)\). Since \(K_{d+3}^d\) is a complete \(d\)-uniform-topological hypergraph, there must exist a simplexoid whose vertex set includes both \(v_1\) and \(v_{d+3}\). By Lemma 19, this simplexoid must intersect with \(K_{d+3}^d[V_1]\). Therefore \(K_{d+3}^d\) cannot be embedded in \(\mathbb{R}^d\). ◻
Lemma 21. \(K_{3,d+1}^d\) is a non-\(\mathbb{R}^d\)-hypergraph.
Proof. The proof of Lemma 21 is similar to that of Lemma 20. (Figure [new8] is an example of \(K_{3,4}^3\) in \(\mathbb{R}^3\). ) ◻
Definition 24 (anti-\(d\)-dimension minor). If a \(d\)-uniform-topological hypergraph \(G\) has a \(K_{d+3}^d\)-minor or \(K_{3,d+1}^d\)-minor, then we call \(G\) an anti-\(d\)-dimension minor.
6.4 Proof of Theorem 1↩︎
In view of Lemma 14 and Lemma 16, it suffices to prove Theorem 1 for triangulated \(d\)-uniform topological hypergraph whose \(1\)-skeleton is \((d+1)\)-connected.
Proof. Let \(G\) be a triangulated \(d\)-uniform topological hypergraph. If its minors include either \(K_{3,d+1}^d\) or \(K_{d+3}^d\), it is obvious that \(G\) is a non-\(\mathbb{R}^d\)-hypergraph by Lemmas 20-21.
Now we assume that \(G\) is a non-\(\mathbb{R}^d\)-hypergraph, the \(1\)-skeleton of \(G\) (denoted by \(G_{sk}^1\)) is \((d+1)\)-connected, and \(G\) is simple. Because all hypergraphs on \((d+2)\) or fewer vertices can be embedded in \(\mathbb{R}^d\), we have \(|V(G)|\geq d+3\). We proceed by induction on \(|V(G)|\). By Lemma 17, \(G_{sk}^1\) contains a \(1\)-dimensional simplexoid \(e = xy\) such that the \(1\)-skeleton of \(H= G/e\) is \((d+1)\)-connected. If \(H\) is a non-\(\mathbb{R}^d\)-hypergraph, it has an anti-\(d\)-dimension minor, by induction. Since every minor of \(H\) is also a minor of \(G\), we deduce that \(G\) too has an anti-\(d\)-dimension minor. So we may assume that \(H\) is an \(\mathbb{R}^d\)-hypergraph.
Consider an \(\mathbb{R}^d\)-embedding \(H'\) of \(H\). Denote by \(z\) the vertex of \(H\) formed by contracting \(e\). Because \(H\) is \((d+1)\)-connected, by Lemma 13 the neighbors of \(z\) lie on a \((d-1)\)-sphere \(S^{d-1}\), the boundary of some polytope \(W\) of \(H'- z\). Denote by \(B_x\) and \(B_y\), respectively, the bridges of \(W\) in \(G \backslash e\) that contain the vertices \(x\) and \(y\).
Note that \(B_x\) and \(B_y\) cannot avoid each other since \(G\) is a triangulated \(d\)-uniform topological hypergraph. It follows that \(B_x\) and \(B_y\) overlap. By Lemma 7, they are therefore either skew or else equivalent \((d+1)\)-bridges. In the latter case, \(G\) has a \(K_{d+3}^d\)-minor; In the former case, \(G\) has a \(K_{3,d+1}^d\)-minor. ◻
Note that in higher dimensions, if \(B_x\) and \(B_y\) in the above proof are skew, the resulting structure becomes less intuitive. We present an example in three-dimensional Euclidean space. It is easy to observe that in this case, \(B_x\) and \(B_y\) together form a \(K_{3,4}^3\), which can be analogized to higher-dimensional cases:
As shown in Figure 7 (1), simplexoids \(x_1y_1y_2,x_1y_2y_3,x_1y_1y_3\), \(x_2y_1y_2,x_2y_2y_3,x_1y_1y_3\) are joined together to form a two-dimensional sphere \(S^2\). Vertices \(x\) and \(y\) are inside \(S^2\). As shown in Figure 7 (2), simplexoids \(xy_1y_2,xy_2y_3\) and \(xy_1y_3\) form a bridge \(B_1\), which effect a partition of \(S^2\) into \(2\) disjoint segments. As shown in Figure 7 (3), there is another bridge \(B_2\) with internal vertex \(y\). Its vertics of attachment includes both \(x_1\) and \(x_2\). By definition, \(B_1\) and \(B_2\) are skew. On the other hand, since there are no pendant simplexoid in the hypergraph, bridge \(B_2\) must include simplexoids \(\{yx_1y_1, yx_1y_2, yx_1y_3, yx_2y_1, yx_2y_2, yx_2y_3, yy_1y_2, yy_2y_3, yy_1y_3\}\). As shown in Figure 7 (4), let \(A=\{x,x_1,x_2\}\) and \(B=\{y,y_1,y_2,y_3\}\), At this point, \(K_{3,4}^3= S^2\cup B_1\cup B_2=(A,B)\) is a complete bipartite \(3\)-uniform-topological hypergraph.
7 Conclusion and outlook↩︎
The Hadwiger conjecture states that every loopless graph \(G\) without a \(K_t\) minor satisfies \(\chi(G) \leq t-1\). This conjecture has been verified for \(1 \leq t \leq 6\). As a generalization of the four color theorem, it remains one of the most significant and challenging open problems in graph theory. Notably, Wagner’s theorem and the four color theorem are equivalent to the case \(t = 5\) of the Hadwiger Conjecture. Given the conjecture’s inherent complexity, we attempt to describe the structure of hypergraphs through high-dimensional embeddings, aiming to establish a connection between the chromatic number of a hypergraph and its embeddability in higher-dimensional spaces. Crucially, we observe that in Theorem 1, the hypergraph \(K_{d+3}^d\) has a \(1\)-skeleton isomorphic to the complete graph \(K_{d+3}\)—precisely the structure central to the Hadwiger Conjecture. To leverage high-dimensional embeddings for studying this conjecture, the following objectives must be addressed:
Develop a method for converting graphs into hypergraphs, thereby establishing an embedding theory for graphs in higher-dimensional Euclidean spaces.
Construct a coloring theory for high-dimensional Euclidean spaces, generalizing the four color theorem. Specifically, we aim to prove that if a graph \(G\) embeds into \(\mathbb{R}^d\), then \(\chi(G) \leq d - 1\).
Our future research will focus primarily on these directions. Resolving these problems will enable the application of Theorem 1 to the Hadwiger Conjecture, offering a fundamentally new framework for its study.
Acknowledgement↩︎
This work was funded by the National Key R & D Program of China (No. 2022YFA1005102) and the National Natural Science Foundation of China (Nos. 12325112, 12288101).
Statements and Declarations↩︎
Competing interests: We hereby declare that there are no conflicts of interest to disclose in relation to this submission. We have no affiliations, relationships, or financial interests that could be perceived as influencing my work.
Data availability: This research does not involve any data generation or analysis. Therefore, no data are available.