Bounding the Chromatic Number via High Dimensional Embedding

Qiming Fang^a, Sihong Shao^b
^aBeijing International Cener for Mathematical Research, Peking University
Beijing 100091, China
^bSchool of Mathematical Sciences, Peking University
Beijing 100091, China Corresponding author: [email protected] (Q.Fang); [email protected](S.Shao)

Abstract: We present a necessary and sufficient condition for determining whether a hypergraph can be embedded in a high-dimensional space, and establish an upper bound for the chromatic number of such hypergraph, which can be viewed as the high-dimensional extension of the Heawood conjecture and Wagner’s Theorem, respectively. Based on them, for a graph of order $n$ , there exists accordingly an algorithm with a complexity of $O(n\log^{2}n)$ that can determine the upper bound for the chromatic number. Specifically, we prove: (i) The graph-closure of a $d$ -uniform-topological hypergraph is a closed- $R^{d}$ -graph if and only if its minors include neither $K_{d+3}^{d}$ nor $K_{3,d+1}^{d}$ ; (ii) Let $G$ be a special triangulated $R^{d}$ -graph, $G^{v}$ be the vertex-hypergraph of $G$ , then $G^{v}$ is $3\cdot 2^{d-1}$ -choosable.

Keywords: embedding; coloring; chromatic number; hypergraph

1 Introduction

This paper aims to bounding the chromatic number via high dimensional embedding in quasilinear time. To achieve this goal, we generalize the concept of planar graph to a higher-dimensional form. A challenge arises: Unlike the plane, higher-dimensional Euclidean spaces are not intuitive. Most definitions and methods related to planar graphs cannot be directly extend to higher dimensions. To address this challenge, it is necessary to introduce concepts and theorems related to simplex, CW complexes, homotopy, and fundamental groups. Please refer to [1, 2, 9] for common used definitions and notations that are not specified in this work.

It is NP-complete to decide if a given graph admits a $k$ -coloring except for the cases $k\in\{0,1,2\}$ . In particular, computing the chromatic number (denoted by $\chi$ ) is NP-hard [7]. There are many algorithms for the problem of calculating the chromatic number, such as greedy algorithms [4, 19], heuristic algorithms [11], parallel and distributed algorithms [16, 17], and graph embeddings [3, 8, 12, 13]. Previous researchers developed the theory of graph embeddings on two-dimensional surfaces and established upper bounds for the chromatic number of graphs on such surfaces, and we follow in this research line by further investigating the embedding problem in high-dimensional spaces.

1.1 Our results

We consider a $d$ -uniform hypergraph as a CW complex. If the fundamental group of a $d$ -uniform hypergraph is trivial, we refer to it as a special $R^{d}$ -graph. All related definitions are given in Section 2.

Wagner’s Theorem states that a finite graph is planar if and only if its minors include neither $K_{5}$ nor $K_{3,3}$ , and we derive its higher-dimensional form.

Theorem 1.1.

The graph-closure of a $d$ -uniform-topological hypergraph is a closed- $R^{d}$ -graph if and only if its minors include neither $K_{d+3}^{d}$ nor $K_{3,d+1}^{d}$ .

The Heawood conjecture (or Ringel-Youngs Theorem) states that $\chi(G)\leq\frac{1}{2}(7+\sqrt{49-24c^{\prime}})$ if $G$ is a graph which can be embedded in a surface $\Sigma$ of Euler characteristic $c^{\prime}$ , and the following theorem presents a kind of its higher-dimensional extension.

Theorem 1.2.

Let $G$ be a special triangulated $R^{d}$ -graph, $G^{v}$ be the vertex-hypergraph of $G$ , then $G^{v}$ is $3\cdot 2^{d-1}$ -choosable.

Theorem 1.1 provides conditions for determining whether a hypergraph can be embedded in $d$ -dimensional Euclidean space (denoted by $R^{d}$ ), and Theorem 1.2 gives an upper bound for the chromatic number of $R^{d}$ . Since a hypergraph can be regarded as a CW complex and a graph can be regarded as the $1$ -skeleton of a CW complex, we can use the aforementioned two theorems to estimate the upper bound for the chromatic number of a graph.

Let $G$ be a graph and $G_{d}$ be a $d$ -uniform-topological hypergraph, if $G$ is the $1$ -skeleton of the graph-closure of $G_{d}$ , then we can conclude from Theorem 1.1 that $G_{d}$ can be embedded in $R^{d}$ . Furthermore, we obtain an upper bound for the chromatic number of $G_{d}$ by Theorem 1.2. Since the chromatic number of $G$ is less than that of $G_{d}$ , we can obtain the following corollary. It should be noted that the method of transforming a graph into a CW complex is not unique, and there should exist an optimal embedding method that yields the better estimate, but we have not yet solved this problem, which remains one of our future work.

Corollary 1.

Let $G$ be a graph, if its minors include neither $K_{d+3}$ nor $K_{3,d+1}$ , then $G$ is $3\cdot 2^{d-1}$ -choosable.

Corollary 1 transforms the problem of determining the upper bound for the chromatic number into the problem of minor testing. Analogous to the embedding problem for two-dimensional closed surfaces [14, 12, 13], if there exists an algorithm that can determine whether a given minor exists in a graph, we can use binary search to obtain an upper bound for the chromatic number. Given a graph of order $n$ , Robertson and Seymour [15] proved that for every graph $M$ there exists a algorithm with a complexity of $O(n^{3})$ that decides whether $G$ contains $M$ as a minor. Later, Kawarabayashi and Reed [10] improved it to $O(n\log n)$ .

Since the complexity of binary search is $O(\log n)$ after noting that the chromatic number of any graph does not exceed its order $n$ and the complexity of minor testing is $O(n\log n)$ [10], by multiplying the two complexities, we can naturally obtain an algorithm with a complexity of $O(n\log^{2}n)$ based on the binary search to compute the upper bound for the chromatic number of any graph.

Remark. Several remarks related to above results follow.

•

We observe that Corollary 1 establish a connection between graph minors and chromatic numbers, which is very similar to Hedwiger’s Conjecture [2]. In [18], Thomason proved that if a graph $G$ does not contain a $K_{t}$ -minor, then the chromatic number of $G$ is at most $2.68t\sqrt{\log_{2}t}\cdot(1+O(1))$ . Substituting $t=7$ , we obtain the following conclusion: If a graph $G$ does not contain a $K_{7}$ -minor, then the chromatic number of $G$ is at most $26$ . Now, substituting $d=4$ into Corollary 1, we know that if $G$ contains neither a $K_{7}$ -minor nor a $K_{3,5}$ -minor, then the chromatic number of $G$ is at most $24$ . Clearly, even without optimize the bound of Corollary 1, our conclusion is partially superior to previous results in low dimensions. Furthermore, if we can introduce the Discharging method into $R^{d}$ -graph to improve the conclusion of Corollary 1, it may help us find another approach to solving Hedwiger’s conjecture. Note that the bound in Theorem 1.2 is estimated only by the relationship between the number of vertices and edges; therefore, there remains a gap between Theorem 1.2 and the sharp upper bound for the chromatic number. By introducing mathematical tools from the field of planar graphs, such as Discharging, we can further refine the bound of Theorem 1.2. However, due to space limitations, we will not discuss this issue in detail here, and relevant conclusions will be presented in our future work. (We conjecture that if $G$ is a special triangulated $R^{d}$ -graph, then there exists a polynomial $f(d)$ such that $G^{v}$ is $f(d)$ -choosable.)
•

Taking planar graph $G$ as an example, from Wagner’s Theorem, we know that if its minors include neither $K_{5}$ nor $K_{3,3}$ , it can be embedded in the plane, thereby implying that the upper bound for the chromatic number of $G$ is $4$ . For any arbitrary two-dimensional closed surface, there is a similar conclusion. In 1979, Filotti et al. [6] presented a polynomial-time algorithm with a complexity of $O(n^{\alpha k+\beta})$ , capable of determining whether a graph $G$ can be embedded in an orientable surface. This algorithm was subsequently optimized, with the most efficient version provided by Mohar [12, 13] in 1996, achieving a complexity of $O(n)$ .
•

Since there exists an algorithm with a complexity of $O(n)$ that can determine whether a graph can be embedded in any given two-dimensional closed surface, and since the chromatic number of a graph does not exceed the number of its vertices $n$ , we can naturally obtain an algorithm with a complexity of $O(n\log n)$ based on binary search to compute an upper bound for the chromatic number of any graph. Unfortunately, for many classes of graphs, the upper bound for the chromatic number obtained by the aforementioned algorithm is not good enough, even for special graph classes such as bipartite graphs. For example, the bipartite graph $K_{3,(5-c^{\prime})}$ cannot be embedded in a two-dimensional closed surface with Euler characteristic $c^{\prime}$ , which suggests that when using this algorithm to estimate the upper bound for the chromatic number for bipartite graphs, the result can be arbitrarily large. However, it is easy to construct a closed- $R^{3}$ -graph $G$ such that $K_{3,(5-c^{\prime})}$ is the $1$ -skeleton of it. Therefore, the upper bound for the chromatic number of $G$ is also an upper bound for the chromatic number of $K_{3,(5-c^{\prime})}$ . According to Theorem 1.2, this bound is $12$ , which reduces the gap between the upper bound of the chromatic number and the actual chromatic number of $K_{3,(5-c^{\prime})}$ from infinite to finite.
•

Over the past few decades, many researchers have attempted to study the embedding of graphs in higher-dimensional spaces. In 1973, Bothe defined the linkless embedding: A linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked (the knotless embedding can also be defined in a similar manner). In 1995, Cohen et al. [5] proved that any finite graph can be embedded into three-dimensional Euclidean space. We focus on hypergraphs and use polytopes in higher-dimensional spaces to represent the hyperedges of hypergraphs, then extend the problem of graph embedding to higher dimensions.

1.2 Overview of the paper

Section 2 mainly talks about the definitions of hypergraphs that can be embedded in $R^{d}$ . In Section 3, we extend the concept of triangulation to higher-dimensional spaces. In Section 4, we prove Theorem 1.2. In Sections 5 and 6, we prepare the groundwork for proving Theorem 1.1, and the proof is laid out in Section 7.

2 $R^{d}$ -graph: Definition and property

By considering $(d-1)$ -dimensional simplices as hyperedges of a $d$ -uniform hypergraph, the concept of planar graphs can be extended to higher-dimensional spaces. We note that the line segments ( $1$ -dimensional simplices) in a planar graph are allowed to undergo topological deformation. Therefore, we allow hyperedges embedded in higher-dimensional space to undergo topological deformation as well. To avoid confusion, we refer to these hyperedges as simplexoid, 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}\}$ , $B$ is a face of $A$ , $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 the image of $B$ under homeomorphism is $B_{0}$ , then we say $B_{0}$ is a $(i-1)$ -sub-simplexoid of $A_{0}$ (or $(i-1)$ -face) if $B_{0}$ contains exactly $i$ vertices.

Definition 2 ( $d$ -Uniform-Topological hypergraph).

Let $H=(X,E)$ be a $d$ -uniform hypergraph. If each hyperedge of $H$ is regarded as a simplexoid of dimension $(d-1)$ , we refer to such a hypergraph as a $d$ -uniform-topological hypergraph.

Definition 3 (General $R^{d}$ -graph).

Let $T_{1},T_{2},...,T_{m}$ be simplexoids of dimension $(d-1)$ which are embedded in $R^{d}$ . We say $\bigcup\limits_{i=1}^{m}T_{i}$ is a general $R^{d}$ -graph if the following conditions hold: If $T_{i}$ and $T_{j}$ are simplexoids in $\{T_{1},T_{2},...,T_{m}\}$ and $T^{\prime}=T_{i}\cap T_{j}\neq\emptyset$ , then $T^{\prime}$ is a sub-simplexoid of both $T_{i}$ and $T_{j}$ . (Each simplexoid $T_{i}$ can be regarded as a hyperedge.)

From Definitions 2 and 3, we know that if a $d$ -uniform-topological hypergraph can be embedded in $R^{d}$ , then it is a general $R^{d}$ -graph.

Definition 4 (Special $R^{d}$ -graph).

If the fundamental group of a general $R^{d}$ -graph is trivial, then this graph is called a special $R^{d}$ -graph.

Note that in the case where the fundamental group is trivial, there will be no knot or other complex structures in the manifold. According to Definition 3 and 4, it is obvious that the special $R^{d}$ -graph is a special kind of the general $R^{d}$ -graph. Since the fundamental group of a special $R^{d}$ -graph is trivial, it can be regarded, up to isomorphism, as a union of internally disjoint $(d-1)$ -dimensional spheres and $(d-1)$ -dimensional balls. (An $i$ -sphere is a topological space that is homeomorphic to a standard $i$ -sphere. The space enclosed by a $i$ -sphere is called an $(i+1)$ -ball. )

Lemma 2.1 (The Construction of Special $R^{d}$ -graph).

Every special $R^{d}$ -graph can be constructed by the following procedure.

Procedure X: $T_{1},T_{2},...,T_{m}$ are simplexoids of dimension $(d-1)$ in $R^{d}$ . Starting from $T_{0}$ , add $T_{1},T_{2},...,T_{m}$ in $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^{\prime}=T_{i}\cap T_{j}\neq\emptyset$ , then $T^{\prime}$ is a sub-simplexoid of both $T_{i}$ and $T_{j}$ .
•

2. Suppose our procedure has reached the $i$ -th step ( $T_{i}$ has been added in $R^{d}$ ). Let $K_{i}=\bigcup\limits_{j=0}^{i}T_{j}$ , $V(T_{i+1})=\{v_{0},v_{1},...,v_{d-1}\}$ , $B_{v_{i}}$ be the sub-simplexoid with vertex set $V(T_{i+1})\backslash\{v_{i}\}$ , $\mathscr{B}=\bigcup\limits_{i=0}^{d-1}\{B_{v_{i}}\}$ be the sub-simplexoid set of $T_{i+1}$ of dimension $(d-2)$ . $T_{i+1}$ satisfies the following condition when adding $T_{i+1}$ to $R^{d}$ : If $\mathscr{A}=T_{i+1}\cap K_{i}$ , then $\exists\mathscr{B}_{0}\subseteq\mathscr{B}$ such that $\mathscr{A}=\bigcup\limits_{B_{v_{i}}\in\mathscr{B}_{0}}B_{v_{i}}$ and $\mathscr{B}_{0}\neq\emptyset$ .

Proof.

Let $K$ be a special $R^{d}$ -graph which is constructed by Procedure X. We prove that the fundamental group of $K$ is trivial. Since $K$ is obtained by adding simplexoid $T_{0},T_{1},T_{2},...,T_{m}$ be one by one, this procedure does not result in any change of the fundamental group, thus the fundamental group of $K$ is the same as that of $T_{0}$ .

Next, let $K$ be a special $R^{d}$ -graph which is constructed by Definition 4, then it is evident that there exists a simplexoid $T_{i}$ in the special $R^{d}$ -graph $K$ such that the fundamental group remains trivial after removing $T_{i}$ from $K$ . By repeatedly removing simplexoids from $K$ , we eventually obtain an empty graph. Note that the fundamental group remains trivial in this process and the process is reversible, which implies that $K$ can be constructed by Procedure X. ∎

Definition 5 (Non-special $R^{d}$ Graph).

If the fundamental group of a $d$ -uniform-topological hypergraph $K=\bigcup\limits_{i=1}^{m}T_{i}$ is trivial and $K$ cannot embedded in $R^{d}$ , then $K$ is called a non-special $R^{d}$ -graph (or non- $R^{d}$ -graph for short).

Note that the generalized Poincaré conjecture ensures that the $R^{d}$ -graph can always be embedded on the $d$ -sphere.

In high-dimensional spaces, some common definitions can be generalized as follows.

Definition 6 (Multiple Simplexoids).

Let $T_{1}$ and $T_{2}$ be $i$ -dimensional simplexoids of an $R^{d}$ -graph $G$ . If $V(T_{1})=V(T_{2})$ , and there exists an open set $W\subseteq R^{d}\backslash G$ such that the boundary of $W$ contains both $T_{1}$ and $T_{2}$ , then $T_{1}$ and $T_{2}$ are called $i$ -dimensional multiple simplexoids.

It should be noted that the above definition requires two simplexoids to lie on the boundary of the same open set; otherwise, we do not consider they are multiple simplexoids.

Definition 7 ( $R^{d}$ -Loops).

Let $T_{1}$ be an $i$ -dimensional simplexoid of an $R^{d}$ -graph. $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 $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 $R^{d}$ -loop.

Definition 8 (Simple $R^{d}$ -Graph).

If $R^{d}$ -graph $G$ does not contain multiple simplexoid and $R^{d}$ -loop, then $G$ is called a simple $R^{d}$ -graph.

Unless otherwise specified, all $R^{d}$ -graphs mentioned hereafter will be simple $R^{d}$ -graphs. Analogous to the definition of incident and adjacent in graph theory, we can define the notions of incident and adjacent in $R^{d}$ -graphs.

Definition 9 (Neighbour).

Let $G$ be an $R^{d}$ -graph, and an $i$ -dimensional simplexoid of $G$ is denoted by $a_{i}$ , and the set of $i$ -dimensional simplexoid of $G$ is denoted as $A_{i}(G)=\{a_{i}|a_{i}\ is\ a\ simplexoid\ of\ G\ of\ dimensional\ i\}$ . For convenience, we use $V(G)$ to denote the vertex set of $G$ , use $V(a_{i})$ to denote the vertex set of $a_{i}$ . Let $u,v\in V(G)$ , we say $u$ is adjacent to $v$ if $\exists~{}a_{i}\in A_{i}(G)$ such that $u,v\in V(a_{i})$ . The set of all vertices that adjacent to point $u$ is denoted by $N_{G}(u)$ , the degree of $u$ is denoted by $d_{G}(u)=|N_{G}(u)|$ .

Definition 10 (Incident and Adjacent).

Let $a_{i}$ be an $i$ -dimensional simplexoid, and $a_{j}$ be a $j$ -dimensional simplexoid ( $i\leq j$ ). We say $a_{i}$ is incident to $a_{j}$ (or $a_{j}$ is incident to $a_{i}$ ) if $a_{i}\cap a_{j}=a_{i},i\neq j$ ; 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 11 (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 12 (Simplexoid Deletion).

Given an $R^{d}$ -graph $G$ , there are two natural ways of deriving smaller graphs from $G$ . If $e$ is a $(d-1)$ -dimensional simplexoid of $G$ , we may obtain a graph with $m-1$ $(d-1)$ -dimensional simplexoids by deleting $e$ from $G$ but leaving the vertices and the remaining simplexoids intact. The resulting graph 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 graph by deleting from $G$ the vertex (or simplexoid) $v$ together with all the $(d-1)$ -dimensional simplexoids incident with $v$ . The resulting graph is denoted by $G-v$ or $G\backslash v$ .

Definition 13 (Simplexoid Contraction).

To contract a simplexoid $e$ of an $R^{d}$ -graph $G$ is to delete the simplexoid and then identify its incident vertices. The resulting graph 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 graph is a simple graph.

Definition 14 ( $R^{d}$ -Embedding).

Let $G$ be a $d$ -uniform-topological hypergraph, an $R^{d}$ -embedding $G^{\prime}$ of $G$ can be regarded as a graph isomorphic to $G$ and is embedded in $R^{d}$ .

Finally, let us provide a brief summary. The $R^{d}$ -graph graph 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 $R^{d}$ -graph, a special $R^{d}$ -graph, or a non- $R^{d}$ -graph, they are essentially special cases of CW complex.

A general $R^{d}$ -graph requires that this CW complex can be embedded in $R^{d}$ . A special $R^{d}$ -graph requires that this CW complex can be embedded in $R^{d}$ and has a trivial fundamental group. A non- $R^{d}$ -graph requires that this CW complex cannot be embedded in $R^{d}$ and has a trivial fundamental group. A thorough understanding of these definitions lays a solid foundation for subsequent proofs.

3 Triangulation of special $R^{d}$ -graph ( $d\geq 3$ )

A simple connected plane graph in which all faces have degree three is called a plane triangulation or, for short, a triangulation. This section extends the concept of triangulation to higher-dimensional spaces. We will divide the triangulation process into two steps: Graph-closure and triangulation. In the following part, the term $R^{d}$ -graph refers to special $R^{d}$ -graph unless otherwise specified.

3.1 Step I: Graph-closure

First, it is necessary to have a clear understanding of the structure of $R^{d}$ -graphs. From Definition 4 and Lemma 3.1, an $R^{d}$ -graph is homeomorphic to the union of a finite collection of $(d-1)$ -dimensional balls and $(d-1)$ -spheres with trivial fundamental group.

Lemma 3.1.

[1] A path connected space whose fundamental group is trivial is simply connected.

The simplexoids in $R^{d}$ -graphs can be divided into two categories which are similar to the hanging edge and non-hanging edge in planar graphs. Next, we will extend the concept of hanging edges to higher-dimensional spaces.

Definition 15 (Hanging Simplexoid).

Let $T$ be a $(d-1)$ -dimensional simplexoid of an $R^{d}$ -graph $K$ , $N_{K(d-2)}(T)$ represent the set of all $(d-2)$ -dimensional simplexoids that is incident to $T$ . If $\forall J\in N_{K(d-2)}(T)$ , there exists a $(d-1)$ -dimensional simplexoid $T^{\prime}\subseteq K$ such that $J=T\cap T^{\prime}$ , then $T$ is called non-hanging simplexoid, if not $T$ is called hanging simplexoid.

Since hanging simplexoids can cause some difficulties in our subsequent research, we need to find a way to eliminate hanging simplexoids in $R^{d}$ -graphs.

Before defining the graph-closure, we first need to introduce the definition of hyper-polytopes. Similar to planar graphs, the following lemma implies that an $R^{d}$ -graph $K$ can be regarded as the boundary of the maximal connected open sets in set $R^{d}\backslash K$ .

Lemma 3.2.

Let $W_{0}$ be a maximal connected open set of $R^{d}\backslash K$ , $W=\overline{W_{0}}$ be the closure of $W_{0}$ , $\partial W=W\backslash W_{0}$ be the boundary of $W$ , then $\partial W\subseteq K$ .

Proof.

Suppose to the contrary that $\partial W\nsubseteq K$ . Let $x\in\partial W\setminus K$ , $d(x,K)=r$ be the minimum distance from $x$ to $K$ .

Let $B(x,\frac{r}{2})$ be a $d$ -dimensional open ball with center $x$ and radius $\frac{r}{2}$ , then $B(x,\frac{r}{2})\cap K=\emptyset$ .

Let $W^{\prime}=W_{0}\cup B(x,\frac{r}{2})$ , then $W^{\prime}$ is a connected open set with $W^{\prime}\cap K=\emptyset$ and $W_{0}\subsetneqq W^{\prime}$ , contradict to the fact that $W_{0}$ is a maximal connected open set of $R^{d}\backslash K$ .

∎

If a planar graph does not contain hanging edges, then each face of the planar graph can be regarded as a polygon. Similarly, if an $R^{d}$ -graph $K$ does not contain hanging simplexoids, then each maximal connected open set in the $R^{d}$ -graph can be regarded as a high-dimensional polytope. Therefore, eliminating all hanging edges in $R^{d}$ -graphs can greatly facilitate subsequent research.

Let $W=\overline{W_{0}}$ be the closure of a maximal connected open set of $R^{d}\backslash K$ , then we say $W$ is a polytope of $K$ . If there is no hanging simplexoids in $K$ and $W$ is a polytope of an $R^{d}$ -graph $K$ , then the boundary of $W$ is a $(d-1)$ -sphere in $K$ by Definition 4 and Lemma 3.2.

The $(d-1)$ -dimensional degree of $W$ is denoted by $d_{G(d-1)}(W)$ by Definition 10. We say $W$ is a unit polytope of dimension $d$ if $d_{G(d-1)}(W)=d+1$ . Note that the definition of unit polytope of dimension $d$ is equivalent to $d$ -dimensional simplexoid. We will prove that each polytope of $R^{d}$ -graph $K$ can be triangulated into a finite collection of unit polytope of dimension $d$ in Section 3.2.

Definition 16 (Graph-Closure).

Let $K$ be an $R^{d}$ -graph and $\mathscr{K}$ be a set of simplexoids such that

\mathscr{K}=\{K_{i}:\ V(K_{i})=V(K),\ A_{d-1}(K)\subseteq A_{d-1}(K_{i}),\ and\ there\ is\ no\ hanging\ simplexoid\ in\ K_{i}\}.

The minimal $R^{d}$ -graph $K^{\prime}$ in set $\mathscr{K}$ is called the graph-closure of $K$ , denoted as $K^{\prime}=\overline{K}$ . A minimal $R^{d}$ -graph means that for any $(d-1)$ -dimensional simplexoid $s$ in $K^{\prime}$ , $K^{\prime}\backslash s\notin\mathscr{K}$ .

Definition 17 (Closed- $R^{d}$ -Graph).

Let $\overline{K}$ be the graph-closure of a special $R^{d}$ -graph $K$ , then $K$ is called the closed- $R^{d}$ -graph if $K=\overline{K}$ .

Next, we prove that for any $R^{d}$ -graph $K$ , simplexoids can be added sequentially to obtain the graph-closure of $K$ .

Theorem 3.1.

Let $K$ be an $R^{d}$ -graph, we add simplexoids $T_{0},T_{1},T_{2},T_{3},...$ into $K$ one by one according to the following procedure. We prove that this procedure will inevitably terminate in a finite number of steps, and the resulting graph will be a graph-closure of $K$ .

Procedure: Let $K=K_{0}$ , we assume that $K$ has became into $K_{i}$ when adding the $i$ -th simplexoid $T_{i}$ .

•

(1). Suppose that our procedure has reached the $i$ -th step, now we need to add $T_{i+1}$ into $K_{i}$ .

Figure 1: graph-closure
- –
  
  (1.1). If $K_{i}$ has no hanging-simplexoid, then we terminate the procedure, it is easy to verify that $K_{i}$ is a graph-closure of $K$ .
- –
  
  (1.2). Otherwise, execute (2).
•

(2). Let $W_{i}$ be a polytope of a $R^{d}$ -graph $K_{i}$ .
- –
  
  (2.1). If there exists two $(d-1)$ -dimensional hanging-simplexoids $T\subseteq\partial W_{i}$ and $T^{\prime}\subseteq\partial W_{i}$ such that each of them contains a $(d-2)$ -sub-simplexoid (denoted by $T_{h}$ and $T_{h}^{\prime}$ ) which is incident with no $(d-1)$ -dimensional simplexoid in $K_{i}$ and $|V(T_{h})\cap V(T_{h}^{\prime})|=d-2$ . Assume that $V(T_{h})=\{v_{1},v_{2},...,v_{d-2},v^{*}\}$ ; $V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{\prime}\}$ . Let $T_{i+1}$ be a $(d-1)$ -dimensional simplexoid with $V(T_{i+1})=V(T_{h})\cup V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{*},v^{\prime}\}$ , we add $T_{i+1}$ into $K_{i}$ and get $K_{i+1}$ , return to (1).
  
  (We provide a figure of the graph-closure of an $R^{3}$ -graph to explain Srep(2.1). As shown in Figure 1, $K_{i}$ is an $R^{3}$ -graph, both $T$ and $T^{\prime}$ are $2$ -dimensional simplexoids, $V(T_{i+1})=\{v_{1},v^{*},v^{\prime}\}$ . Note that after adding the simplexoids $T_{i+1}$ , the number of hanging-simplexoids in $K_{i}$ decreases by one. )
- –
  
  (2.2). Otherwise, choose a $(d-1)$ -dimensional hanging-simplexoid $T\subseteq\partial W_{i}$ and a $(d-1)$ -dimensional simplexoid $T^{\prime}\subseteq\partial W_{i}$ such that $|V(T)\cap V(T^{\prime})|\geq d-2$ . Let $T_{h}$ be the $(d-2)$ -sub-simplexoid of $T$ that is incident with no $(d-1)$ -dimensional simplexoid in $K_{i}$ ; $T_{h}^{\prime}$ be the $(d-2)$ -sub-simplexoid of $T^{\prime}$ such that $|V(T_{h})\cup V(T_{h}^{\prime})|=d-2$ . Assume that $V(T_{h})=\{v_{1},v_{2},...,v_{d-2},v^{*}\}$ ; $V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{\prime}\}$ . let $T_{i+1}$ be a $(d-1)$ -dimensional simplexoid with $V(T_{i+1})=V(T_{h})\cup V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{*},v^{\prime}\}$ , we add $T_{i+1}$ into $K_{i}$ and get $K_{i+1}$ , return to (1).
  
  (We provide a figure of the graph-closure of an $R^{3}$ -graph to explain Srep(2.2). As shown in Figure 2, $K_{i}$ is an $R^{3}$ -graph and $e$ is a hanging-simplexoid. Note that after adding the simplexoids $T_{i+1}$ and $T_{i+2}$ , there is no hanging-simplexoid in $K_{i}$ . )

Refer to caption — Figure 2: hanging simplexoids

Proof.

First, we prove that the above process will certainly terminate in a finite number of steps. It is evident that through step (2), the number of hanging-simplexoids in $K$ will decrease. Since $K$ is a finite $R^{d}$ -graph with no multiple simplexoids, the process will inevitably terminate in a finite number of steps.

Since the number of hanging-simplexoids in $K$ decreases with each iteration of step (2), let $K_{x-1}$ denote the $R^{d}$ -graph after $(x-1)$ steps, which still contains hanging-simplexoids; let $K_{x}$ be the $R^{d}$ -graph which no longer contains any hanging-simplexoids after $x$ steps. By Definition 16, it is evident that $K_{x}$ is the closure of $K$ .

∎

Corollary 2.

Let $K$ be an $R^{d}$ -graph and $\overline{K}$ be the graph-colsure of $K$ , then $\overline{K}$ is homeomorphic to the union of a finite collection of $(d-1)$ -spheres.

3.2 Step II: Triangulation

In this section, we will further triangulate $R^{d}$ -graphs based on their closures, ensuring that each polytope in the $R^{d}$ -graph is a unit polytope.

Definition 18.

An $R^{d}$ -graph in which all polytopes are unit polytopes of dimension $d$ is called a triangulated $R^{d}$ -graph.

Definition 19.

Let $K$ and $K^{T}$ be $R^{d}$ -graphs. If $V(K)=V(K^{T})$ , $A_{d-1}(K)\subseteq A_{d-1}(K^{T})$ , and $K^{T}$ is a triangulated $R^{d}$ -graph, then $K^{T}$ is a called a triangulated $R^{d}$ -graph of $K$ .

Definition 20.

An $R^{d}$ -graph $G$ is called a special triangulated $R^{d}$ -graph if $G$ is a special $R^{d}$ -graph and all polytopes of $G$ are unit polytopes of dimension $d$ .

Next, we prove that for any $R^{d}$ -graph, simplexoids can be added sequentially to obtain a triangulated $R^{d}$ -graph.

Theorem 3.2.

Let $K$ be a closed- $R^{d}$ -graph, we add simplexoids $T_{1},T_{2},T_{3},...$ into $\overline{K}$ one by one according to the following procedure. We prove that this procedure will inevitably terminate in a finite number of steps, and the resulting graph will be a triangulated $R^{d}$ -graph of $K$ .

Procedure: Let $K=K_{0}$ ; we assume that $K$ has become into $K_{i}$ when adding the $i$ -th simplexoid $T_{i}$ .

•

(1). Suppose that our procedure has reached the $i$ -th step, now we need to add $T_{i+1}$ into $K_{i}$ .
- –
  
  (1.1). If all polytopes of $K_{i}$ are unit polytopes of dimension $d$ , it is easy to verify that $K_{i}$ is a graph-closure of $K$ .
- –
  
  (1.2). Otherwise, execute (2).
•

(2). Let $W_{i}$ be a polytope of a special $R^{d}$ -graph $K_{i}$ . Choose two $(d-2)$ -dimensional simplexoids $T_{h}\subseteq\partial W_{i}$ and $T^{\prime}_{h}\subseteq\partial W_{i}$ such that $|V(T_{h})\cap V(T^{\prime}_{h})|=d-2$ . Assume that $V(T_{h})=\{v_{1},v_{2},...,v_{d-2},v^{*}\}$ ; $V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{\prime}\}$ .
- –
  
  (2.1). If $V(T^{\prime\prime})\neq V(T_{h})\cup V(T_{h}^{\prime})$ for any $(d-1)$ -dimensional simplexoid $T^{\prime\prime}\in A_{d-1}(K_{i})$ , then let $T_{i+1}$ be a $(d-1)$ -dimensional simplexoid with $V(T_{i+1})=V(T_{h})\cup V(T_{h}^{\prime})$ . Now we add $T_{i+1}$ into $K_{i}$ and get $K_{i+1}$ , return to (1). (Figure 4 is the procedure of (2.1) when $K$ is a special $R^{2}$ -graph (planar graph).)
- –
  
  (2.2). If there exists a $(d-1)$ -dimensional simplexoid $T^{\prime\prime}\in A_{d-1}(K_{i})$ such that $V(T^{\prime\prime})=V(T_{h})\cup V(T_{h}^{\prime})=\{v_{1},v_{2},...,v_{d-2},v^{*},v^{\prime}\}$ , then we return to (2), reselect two different $(d-2)$ -dimensional simplexoids $T_{h}\subseteq\partial W_{i}$ and $T^{\prime}_{h}\subseteq\partial W_{i}$ , and then re-execute (2.1) and (2.2).

Proof.

Since $K$ contains no multiple simplexoid, the above process always terminates in a finite number of steps. Clearly, the necessary and sufficient condition for the above process to terminate at step $i$ is that all polytopes of $K_{i}$ are unit polytopes of dimension $d$ , which implies that $K_{i}$ is called a triangulated $R^{d}$ -graph of $K$ . ∎

In practical applications, it is necessary not only to perform a triangulation of the $R^{d}$ -graph but also to determine the number of unit polytopes in the triangulated $R^{d}$ graph. Therefore, it is required to prove the following theorem.

Theorem 3.3.

Let $W$ be a polytope of a special $R^{d}$ -graph $K$ . Each simplexoid in $W$ is the non-hang simplexoid. We use $d_{\partial W(d-1)}(v)$ to denote the number of $(d-1)$ -dimensional simplexoids which are incident to $v$ in $\partial W$ . We use $d_{G(d-1)}(W)$ to denote the number of $(d-1)$ -dimensional simplexoids that are in $\partial W$ . Then $W$ can be triangulated into $d_{G(d-1)}(W)-k$ $d$ -dimensional simplexoids if there exists $v\in\partial W$ with $d_{\partial W(d-1)}(v)=k$ . Such triangulation is called the $v$ -triangulation.

Proof.

Let $B_{d}$ be a $d$ -dimensional closed ball, $\partial B_{d}=S_{d-1}$ , then $W$ is homeomorphic to the $B_{d}$ with homeomorphism $\phi:W\rightarrow B_{d}$ . Furthermore, $\phi$ takes the interior of $W$ to the interior of $B_{d}$ , and the $\partial W$ to the boundary of $S_{d}$ by Lemma 3.3.

Let $T\subseteq\partial W$ be a $(d-1)$ -dimensional simplexoid which satisfy $v\notin V(T)$ , then $\phi(T)\subseteq S_{d}$ is also a $(d-1)$ -dimensional simplexoid. The number of such $T$ is $d_{G(d-1)}(W)-k$ .

$\forall x_{i}\in\phi(T)$ , join $\phi(v)$ and $x_{i}$ . All such line segments form a $d$ -dimensional manifold $A$ , and it is obvious that $\phi^{-1}(A)$ is a $d$ -dimensional simplexoid in $W$ (Figure 4 is an example of $A$ when $d=3$ ). For every such $T$ that satisfies the above conditions, we repeat this process and get a triangulation of $B_{d}$ , such triangulation is also a triangulation of $W$ since $W$ is homeomorphic to the $B_{d}$ .

Note that the number of such $d$ -dimensional simplexoids in $W$ is equal to the number of $(d-1)$ -dimensional simplexoids (denoted by $T$ ) which satisfy $T\subseteq\partial W$ and $v\notin T$ , thus we can triangulate $W$ into $d_{G(d-1)}(W)-k$ $d$ -dimensional simplexoids.

∎

Lemma 3.3.

[9] Let $h:S_{1}\rightarrow S_{2}$ be a homeomorphism between two manifolds, then $h$ takes the interior of $S_{1}$ to the interior of $S_{2}$ , and the boundary of $S_{1}$ to the boundary of $S_{2}$ .

4 Coloring of special $R^{d}$ -graph

In order to estimate the chromatic number of special $R^{d}$ -graph, we need a new definition that connects the special $R^{d}$ -graph with coloring. In fact, the vertex-hypergraph can be considered as the skeleton of the special $R^{d}$ -graph.

4.1 Relationship between the number of vertices and edges

Definition 21 (Vertex-Hypergraph).

Let $G$ be an $R^{d}$ -graph. If we regard each $T$ as a hyperedge with vertex set $V(T)$ , then we get a $d$ -uniform hypergraph $G^{v}$ which is called the vertex-hypergraph of $G$ . A proper coloring of the hypergraph $G^{v}$ is a coloring such that $c(u)\neq c(v)$ for any adjacent vertices $u$ and $v$ (id est, there exists a hyperedge $T$ such that $\{u,v\}\subseteq V(T)$ ), the chromatic number $\chi(G^{v})$ of $G^{v}$ is the smallest integer $k$ such that $G^{v}$ is $k$ -colorable. Let $L$ be a list assignment of $G^{v}$ with $L(v)=k$ for any $v\in V(G^{v})$ , an $L$ -coloring $c$ of $G^{v}$ is a coloring such that $c(v)\in L(v)$ for any $v\in V(G^{v})$ . $G^{v}$ is $k$ -choosable if $G^{v}$ has an $L$ -coloring for any list $L$ with $|L(v)|=k$ . The choice number of $G^{v}$ , denoted by $\chi^{l}(G^{v})$ , is the least integer $k$ such that $G^{v}$ is $k$ -choosable.

We observe that performing graph-closure or triangulation on an $R^{d}$ -graph $K$ does not decrease the chromatic number of the vertex-hypergraph.

Theorem 4.1.

Let $G$ be a special triangulated $R^{d}$ -graph, $E(G)$ be the set of $1$ -dimensional simplexoids of $G$ , then $|E(G)|\leq(3\cdot 2^{d-2})|V(G)|-3\cdot 2^{d-2}\cdot(d+1)+\frac{d(d+1)}{2}$ if $|V(G)|\geq d+1$ .

Proof.

By induction on $d$ (denoted by Induction $\alpha$ ). The theorem holds trivially for $d=2$ . Assume that it holds for all integers less tha $d$ , and let $G$ be a triangulated special $R^{d-1}$ -graph with

|E(G)|\leq(3\cdot 2^{d-3})|V(G)|-3\cdot 2^{d-3}\cdot d+\frac{d(d-1)}{2},

then

\frac{2|E(G)|}{|V(G)|}\leq 3\cdot 2^{d-2}-\frac{3\cdot 2^{d-3}\cdot d-\frac{d(d-1)}{2}}{|V(G)|}<3\cdot 2^{d-2},

which implies that there exists a vertex $v\in V(G)$ such that $d_{G}(v)\leq 3\cdot 2^{d-2}-1$ .

Now we prove that the theorem holds for $d$ .

Claim 4.1.

Theorem 4.1 holds for $d$ .

Proof.

By induction on $|V(G)|$ (denoted by Induction $\beta$ ). The theorem holds trivially for $|V(G)|=d+1$ . Let $m$ be an integer with $m>d+1$ . Assume that the theorem holds for $|V(G)|<m$ .

Now we prove the theorem holds for $|V(G)|=m$ .

$\forall~{}u\in V(G)$ , let $d_{G0}(u)$ be the number of vertices which are adjacent to $u$ , $G_{1}=G-u$ be a special $R^{d}$ -graph with $V(G_{1})=V(G)\backslash\{u\}$ and $A_{d-1}(G_{1})=\{T|\ T\in A_{d-1}(G),\ u\notin V(T)\}$ . It is obvious that there is only one polytope $W$ which is not the unit polytope of $G_{1}$ , and $\partial W$ is a special $R^{d-1}$ -graph (denoted by $G_{0}$ ).

Observe that $G_{0}$ is homeomorphic to $S_{d-1}$ , and $|V(G_{1})|\geq d+1$ since $|V(G)|=m>d+1$ , then there exists a vertex $v\in V(G_{0})$ such that $d_{G_{0}}(v)\leq 3\cdot 2^{d-2}-1$ by the induction hypothesis (Induction $\alpha$ ).

We triangulate $G_{1}$ into a triangulated $R^{d}$ -graph $G_{1}^{\prime}$ , and such a triangulation is a $v$ -triangulation in Theorem 4.2. Observe that $G_{1}^{\prime}$ is also a special $R^{d}$ -graph, then $|E(G_{1}^{\prime})|\leq 3\cdot 2^{d-2}|V(G_{1}^{\prime})|-3\cdot 2^{d-2}\cdot(d+1)+\frac{d(d+1)}{2}$ by the induction hypothesis (Induction $\beta$ ).

Note that the triangulation is a $v$ -triangulation, then

|E(G)|-d_{G0}(u)=|E(G_{1})|=|E(G_{1}^{\prime})|-(d_{G}(u)-d_{G_{0}}(v)-1),

|E(G_{1}^{\prime})|=|E(G)|-d_{G_{0}}(v)-1.

On the other hand, $|E(G_{1}^{\prime})|=|E(G)|-d_{G_{0}}(v)-1\geq|E(G)|-3\cdot 2^{d-2}$ since $d_{G_{0}}(v)\leq 3\cdot 2^{d-2}-1$ , and we also know that $|V(G_{1})|=|V(G)|-1$ . Therefore,

|E(G)|-3\cdot 2^{d-2}\leq|E(G_{1}^{\prime})|\leq 3\cdot 2^{d-2}(|V(G)|-1)-3\cdot 2^{d-2}\cdot(d+1)+\frac{d(d+1)}{2},

|E(G)|\leq 3\cdot 2^{d-2}|V(G)|-3\cdot 2^{d-2}\cdot(d+1)+\frac{d(d+1)}{2},

and the claim follows by induction.

∎

We infer that Theorem 4.1 holds for $d$ , and the theorem follows by induction.

∎

Corollary 3.

Let $G$ be a special triangulated $R^{d}$ -graph, $G^{v}$ be the vertex-hypergraph of $G$ , then there exists a $(3\cdot 2^{d-1}-1)^{-}$ -vertex in $G^{v}$ . (An $i^{-}$ -vertex $v$ represent that $d(v)\leq i$ . )

Proof.

By Lemma 4.1,

\frac{2|E(G)|}{|V(G)|}\leq 3\cdot 2^{d-1}-\frac{3\cdot 2^{d-2}\cdot(d+1)-\frac{d(d+1)}{2}}{|V(G)|}<3\cdot 2^{d-1},

which implies that there exists a $(3\cdot 2^{d-1}-1)^{-}$ -vertex in $G^{v}$ .

∎

4.2 Proof of Theorem 1.2

Proof.

Suppose to the contrary that there exists a minimum counterexample $G$ of Theorem 1.2 with fewest vertices. Note that there exists a $(3\cdot 2^{d-1}-1)^{-}$ -vertex $v$ in $G^{v}$ by Corollary 3.

By the minimality of $G^{v}$ , $G^{\prime}=G^{v}-v$ is $3\cdot 2^{d-1}$ -choosable. Let $N_{G}(v)=\{v_{i}|\ \exists e\in E\ such\ that\ v_{i}\in e\ and\ v\in e\}$ , $L$ be a list assignment of $G$ with $L(v)=3\cdot 2^{d-1}$ . It is obvious that $G^{\prime}$ has an $L$ -coloring $c$ . Observe that $d_{G}(v)\leq 3\cdot 2^{d-1}-1$ , we color $v$ by $c(v)\in L(v)\backslash\{c(v_{i})|v_{i}\in N_{G}(v)\}$ and get a $L$ -coloring of $G$ , a contradiction.

∎

Since an $R^{d}$ -graph is a special type of $(d-1)$ -dimensional CW complex, and a graph can be regarded as the $1$ -skeleton of an $R^{d}$ -graph, the upper bound for the chromatic number of $R^{d}$ -graphs can be easily extended to graphs.

5 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 $R^{d}$ -graph 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-1$ , 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 elements of $V(B)\cap V(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 (that is, if it is of the second type). A bridge with $k$ vertices of attachment is called a $k$ -bridge. Two bridges with the same vertices of attachment 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 5.1.

Let $G$ be a special $R^{d}$ -graph, $B$ be a bridge of $(d-1)$ -sphere $S_{d-1}$ , the projection of $B$ which is denoted by $p(B)=B\cap S_{d-1}$ is a connected special $R^{d-1}$ -graph.

Proof.

Let $p_{1}$ and $p_{2}$ be two distinct connected components of $p(B)$ , $v_{1}\in p_{1}$ and $v_{2}\in p_{2}$ , $P_{B}(v_{1},v_{2})\subseteq B$ denotes a path between vertices $v_{1}$ and $v_{2}$ , $P_{S}(v_{1},v_{2})\subseteq S_{d-1}$ denotes another path between vertices $v_{1}$ and $v_{2}$ , then $C=P_{B}(v_{1},v_{2})\cup P_{S}(v_{1},v_{2})$ is evidently a cycle, and in graph $G$ , cycle $C$ cannot be continuously contracted to a point. Thus, it follows that the fundamental group of graph $G$ is nontrivial, leading to a contradiction. ∎

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^{\prime}$ 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 of attachment $u,v$ of $B^{\prime}$ 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 5.1 and Lemma 7.6.

We give an example of skew for $S_{2}$ . As shown in Figure 5, 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 5.2.

Overlapping $d$ -hyper-bridges of a closed- $R^{d}$ -graph are either skew or else equivalent $(d+1)$ -bridges.

Proof.

Suppose that bridges $B$ and $B^{\prime}$ overlap. Clearly, each of them must have at least $d$ vertices of attachment. If either $B$ or $B^{\prime}$ is a $d$ -bridge, it is easily verified that they must be skew. We may therefore assume that both $B$ and $B^{\prime}$ have at least $(d+1)$ vertices of attachment.

If $B$ or $B^{\prime}$ 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 of attachment $u^{\prime},v^{\prime}$ of $B^{\prime}$ such that $u^{\prime}$ and $v^{\prime}$ are in different segment of $\{R_{1},R_{2}\}$ . It follows that $B$ and $B^{\prime}$ are skew.

If $B$ and $B^{\prime}$ are equivalent k-bridges, then $k\geq d+1$ . If $k\geq d+2$ , $B$ and $B^{\prime}$ are skew by Lemma 5.3; if $k=d+1$ , they are equivalent $(d+1)$ -bridges.

∎

Lemma 5.3.

Let $G$ be an special $R^{d}$ -graph which is isomorphic to $S_{d-1}$ with $|V(G)|\geq d+2$ , then there is a subgraph $C$ of $G$ which is isomorphic 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 of attachment $u^{\prime},v^{\prime}$ of $G$ such that $u^{\prime}$ and $v^{\prime}$ are in different segment of $\{R_{1},R_{2}\}$ .

Proof.

Firstly, we prove that there exists a vertex $v^{\prime}\in V(G)$ such that $d(v^{\prime})\leq|V(G)|-2$ , if not, we konw that $d(v)=|V(G)|-1$ for every vertex $v\in V(G)$ , which implies that $G$ is a complete graph. It is impossible since $G$ is isomorphic to $S_{d-1}$ .

Let $N_{G}(v^{\prime})$ be the neighbor of $v^{\prime}$ , then $G[N_{G}(v^{\prime})]$ is isomorphic to a $(d-2)$ -sphere, note that $G[N_{G}(v^{\prime})]$ effects a partition of $S_{d-1}$ into $2$ disjoint segments $\{R_{1},R_{2}\}$ , without loss of generality, let $v^{\prime}\in R_{1}$ .

It is easy to verify that $V(G)\backslash[N_{G}(v^{\prime})\cup\{v^{\prime}\}]\neq\phi$ since $|V(G)|\geq d+2$ , let $u^{\prime}\in V(G)\backslash[N_{G}(v^{\prime})\cup\{v^{\prime}\}]$ , it follows that $u^{\prime}\in R_{2}$ .

∎

6 Hyper ear decomposition

In this section, we aim to establish some lemmas of ear decomposition in higher-dimensional spaces. Let $K$ be a $d$ -connected $R^{d}$ -graph. Apart from complete graph $K_{i}$ ( $i\leq d+1$ ), the $d$ -connected closed- $R^{d}$ -graph contains a subgraph $G_{0}$ which is isomorphic to $S_{d-1}$ . We describe here a simple recursive procedure for generating any such graph starting with an arbitrary $(d-1)$ -sphere of the $R^{d}$ -graph.

Definition 22 (Hyper Ear).

Let $F$ be a subgraph of an $R^{d}$ -graph $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 23 (Hyper Ear Decomposition).

A nested sequence of a closed- $R^{d}$ -graph is a sequence $(G_{0},G_{1},...,G_{k})$ of $R^{d}$ -graphs such that $G_{i}\subseteq G_{i+1}$ , $0\leq i\leq k$ . A hyper ear decomposition of a $d$ -connected closed- $R^{d}$ -graph $G$ is a nested sequence $(G_{0},G_{1},...,G_{k})$ of $d$ -connected subgraphs of $G$ such that:

•

$G_{0}$ is isomorphic to $S_{d-1}$ .
•

$G_{i+1}=G_{i}\cup P_{i}$ where $P_{i}$ is a hyper ear of $G_{i}$ in $G$ , $0\leq i\leq k$ .
•

$G_{k}=G$ .

Lemma 6.1.

The $d$ -connected closed- $R^{d}$ -graph $G$ with $|V(G)|>d+1$ has a hyper ear decomposition.

Proof.

Note that $G$ is homeomorphic to the union of a finite collection of $(d-1)$ -spheres by Corollary 2. It is obvious that $G$ has a hyper ear decomposition by Definition 23. ∎

Lemma 6.2.

In a $d$ -connected closed- $R^{d}$ -graph $G$ with $|V(G)|>d+1$ , each maximal connected region or $R_{d}\backslash G$ is bounded by a $(d-1)$ -sphere.

Proof.

Note that $G$ has a hyper ear decomposition by Lemma 6.1. Consider an ear decomposition $(G_{0},G_{1},...,G_{k})$ of $G$ , where $G_{0}$ is isomorphic 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 isomorphic 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 $R^{d}$ -graph, 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 6.3.

In a loopless $(d+1)$ -connected closed- $R^{d}$ -graph $G$ , the neighbours of any vertex lie on a common $(d-1)$ -sphere.

Proof.

Let $G$ be a loopless $(d+1)$ -connected $R^{d}$ -graph and $v$ be a vertex of $G$ , then $G-v$ is $d$ -connected, so each maximal connected region of $G-v$ is bounded by a sphere by Lemma 6.2. If $f$ is the region of $G-v$ in which the vertex $v$ was situated, the neighbours of $v$ lie on its bounding sphere $\partial(f)$ .

∎

7 Recognizing $R^{d}$ -Graph

We extend the definition of $S$ -component for graphs to higher-dimensional spaces before proving our main result.

7.1 $S$ -component

Definition 24 ( $S$ -component).

Let $G$ be a connected graph 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 $d$ -connected $R^{d}$ -graph 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$ . The graph $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 6, $S:=\{x_{1},x_{2},x_{3}\}$ be a 3-cut of an $R^{3}$ -graph $G$ , we provide an example of the $S$ -decomposition and marked $S$ -decomposition of an $R^{3}$ -graph. 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 graph, it needs to be added during the construction.

We need to establish some lemmas before proving our main results.

Lemma 7.1.

Let $G$ be a closed- $R^{d}$ -graph 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^{\prime}$ 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^{\prime}$ and $B\cup e$ is a $(d-1)$ -sphere by Lemma 6.1. It is easy to verify that $H$ is isomorphic to a minor of $G$ by contract $H^{\prime}$ into a single simplexoid $e$ .

∎

Lemma 7.2.

Let $G_{1}$ and $G_{2}$ be closed $R^{d}$ -graphs whose intersection is isomorphic to $K_{d}$ with $V(K_{d})=\{x_{1},x_{2},...,x_{d}\}$ , then $G_{1}\cup G_{2}$ is a closed $R^{d}$ -graph.

Proof.

Let $H$ be a hyperplane, $V(K_{d})\subseteq H$ . At this point, the hyperplane $H$ divides $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 fundamental group of $G_{1}\cup G_{2}$ is nontrivial, then there must exist a curve $L$ that cannot be continuously contracted to the base point. If curve $L$ belongs to either $G_{1}$ or $G_{2}$ , then it can be contracted continuously to base point, which leads to a contradiction. Therefore, $L$ must intersect both $G_{1}$ and $G_{2}$ . Let $L\cap G_{1}=L_{1}$ and $L\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 $L$ can be continuously contracted to the base point, a contradiction. In conclusion, the assumption is invalid, and the theorem is proven.

∎

Lemma 7.3.

Let $G$ be a closed- $R^{d}$ -graph with a $d$ -vertex cut $\{x_{1},x_{2},...,x_{d}\}$ , then $G$ is a closed- $R^{d}$ -graph if and only if each of its marked $\{x_{1},x_{2},...,x_{d}\}$ -components is a closed- $R^{d}$ -graph.

Proof.

Suppose, first, that $G$ is a closed $R^{d}$ -graph. By Lemma 7.1, each marked $\{x_{1},x_{2},...,x_{d}\}$ -component of $G$ is isomorphic to a minor of $G$ , hence is closed- $R^{d}$ -graph.

Conversely, suppose that $G$ has $k$ marked $\{x_{1},x_{2},...,x_{d}\}$ -components each of which is a closed- $R^{d}$ -graph. Let $e$ denote their common marker simplexoid. Applying Lemma 7.2 and induction on $k$ , it follows that $G+e$ is a closed $R^{d}$ -graph, hence so is $G$ . ∎

By Lemma 7.3, we know that to prove a closed $R^{d}$ -graph can be embedded in $R^{d}$ , it is sufficient to show that all of its marked $\{x_{1},x_{2},...,x_{d}\}$ -components can be embedded in $R^{d}$ .

7.2 Connectivity

Before proving Theorem 1.1, we need a lemma regarding connectivity.

Lemma 7.4.

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 7.5, 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 7.4, 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 $\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 7.5.

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$ . ∎

7.3 Anti- $d$ -dimension minor

The following proof demonstrates that there is a conclusion that holds in $R^{d}$ that similar to Wagner’s Theorem. It is necessary to generalize the concepts of complete graphs and bipartite graphs to higher-dimensional spaces.

Definition 25 (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 8 is an example of $K_{4}^{3}$ . )

Definition 26 (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}$ . (Figure 8 is an example of $K_{2,4}^{3}$ . )

•

$G[B]$ is a complete $(i-1)$ -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}\}$ and $|A_{i-1}(G)|$ is minimal.

Next, we use the Jordan-Brouwer Separation Theorem to prove Lemma 7.7 and 7.8.

Lemma 7.6.

(Jordan-Brouwer Separation Theorem) Let $X$ be a $d$ -dimensional topological sphere in the $(d+1)$ -dimensional Euclidean space $R_{d+1}$ ( $d>0$ ), i.e. the image of an injective continuous mapping of the $d$ -sphere $S_{d}$ into $R_{d+1}$ , then the complement $Y$ of $X$ in $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 7.7.

$K_{d+3}^{d}$ is a non- $R^{d}$ -graph.

Proof.

Suppose to the contrary that $K_{d+3}^{d}$ is an $R^{d}$ -graph.

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 isomorphic 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 $R^{d}$ . By Lemma 7.6, each $K_{d+3}^{d}[V_{i}]$ will divide $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 the Figure 10, when embedded $K_{d+3}^{d}$ in $R^{d}$ , it is obvious that line $v_{1}v_{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 7.6, this simplexoid must intersect with $K_{d+3}^{d}[V_{1}]$ . Therefore $K_{d+3}^{d}$ cannot be embedded in $R^{d}$ .

∎

Lemma 7.8.

$K_{3,d+1}^{d}$ is a non- $R^{d}$ -graph.

Proof.

The proof of Lemma 7.8 is similar to that of Lemma 7.7. (Figure 10 is an example of $K_{3,4}^{3}$ in $R^{3}$ . )

∎

Definition 27 (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.

7.4 Proof of Theorem 1.1

Proof.

Let $G$ be the graph-closure of a $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- $R^{d}$ -graph by Lemma 7.7-7.8.

Now we assume that $G$ is a $(d+1)$ -connected non- $R^{d}$ -graph and $G$ is simple. Because all graphs on $d+2$ or fewer vertices can be embedded in $R^{d}$ , we have $|V(G)|\geq d+3$ . We proceed by induction on $|V(G)|$ . By Lemma 7.4, $G$ contains an edge $e=xy$ such that $H=G/e$ is $(d+1)$ -connected. If $H$ is non- $R^{d}$ , 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 $R^{d}$ -graph.

Consider an $R^{d}$ -embedding $H^{\prime}$ of $H$ . Denote by $z$ the vertex of $H$ formed by contracting $e$ . Because $H$ is $(d+1)$ -connected, by Lemma 6.3 the neighbours of $z$ lie on a $(d-1)$ -sphere $S_{d-1}$ , the boundary of some polytope $W$ of $H^{\prime}-z$ . Denote by $B_{x}$ and $B_{y}$ , respectively, the hyper-bridges of $W$ in $G\backslash e$ that contain the vertices $x$ and $y$ .

Suppose, first, that $B_{x}$ and $B_{y}$ avoid each other. In this case, $B_{x}$ and $B_{y}$ can be embedded in the polytope $W$ of $H^{\prime}-z$ in such a way that the vertices $x$ and $y$ belong to the same polytope of the resulting $R^{d}$ -graph $(H^{\prime}-z)\cup B_{x}\cup B_{y}$ . The edge $xy$ and the simplexoids that incident with $xy$ can now be drawn in that polytope so as to obtain an $R^{d}$ -embedding of $G$ itself, contradicting the hypothesis that $G$ is non- $R^{d}$ .

It follows that $B_{x}$ and $B_{y}$ do not avoid each other, that is, they overlap. By Lemma 5.2, 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.

•

In higher dimensions, the former case is not intuitive. Here, we provide an example of minimum skew is equivalent to $K_{3,4}^{3}$ in $R^{3}$ , which can be analogized to higher-dimensional cases.
•

As shown in Figure 11(1), simplexoids $x_{1}y_{1}y_{2},x_{1}y_{2}y_{3},x_{1}y_{1}y_{3}$ , $x_{2}y_{1}y_{2},x_{2}y_{2}y_{3},x_{1}y_{1}y_{3}$ are joined together to form a two-dimensional sphere $S_{2}$ . Vertices $x$ and $y$ are inside $S_{2}$ .
•

As shown in Figure 11(2), simplexoids $xy_{1}y_{2},xy_{2}y_{3}$ and $xy_{1}y_{3}$ form a bridge $B_{1}$ , which effect a partition of $S_{2}$ into $2$ disjoint segments.
•

As shown in Figure 11(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 hanging simplexoid in the graph, bridge $B_{2}$ must include simplexoids $\{yx_{1}y_{1},yx_{1}y_{2},yx_{1}y_{3},yx_{2}y_{1},yx_{2}y_{2},yx_{2}y_{3},yy_{1}y_{2},yy_{2}y_{3},yy_{1}y_{3}\}$ .
•

As shown in Figure 11(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.

∎

References

[1] Mark Anthony Armstrong. Basic topology. Springer Science & Business Media, 2013.
[2] John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory. Springer Publishing Company, Incorporated, 2008.
[3] John M Boyer and Wendy J Myrvold. Simplified o (n) planarity by edge addition. Graph Algorithms Appl, 5:241, 2006.
[4] Daniel Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979.
[5] Robert F. Cohen, Peter Eades, Tao Lin, and Frank Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199–208, 1997.
[6] IS Filotti, Gary L Miller, and John Reif. On determining the genus of a graph in o (v o (g)) steps (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 27–37, 1979.
[7] Michael R Garey, David S Johnson, and Larry Stockmeyer. Some simplified np-complete problems. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 47–63, 1974.
[8] John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM (JACM), 21(4):549–568, 1974.
[9] R Munkres James. Topology. Prentic Hall of India Private Limited, New delhi, 7, 2000.
[10] Ken-ichi Kawarabayashi and Paul Wollan. A simpler algorithm and shorter proof for the graph minor decomposition. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 451–458, 2011.
[11] Rhyd Lewis. Guide to graph colouring. Springer, 2021.
[12] Bojan Mohar. Embedding graphs in an arbitrary surface in linear time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 392–397, 1996.
[13] Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics, 12(1):6–26, 1999.
[14] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Press, 2001.
[15] Neil Robertson and Paul D Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110, 1995.
[16] Johannes Schneider and Roger Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pages 35–44, 2008.
[17] Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 257–266, 2010.
[18] Andrew Thomason. An extremal function for contractions of graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 95, pages 261–265. Cambridge University Press, 1984.
[19] Dominic JA Welsh and Martin B Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.

Bounding the Chromatic Number via High Dimensional Embedding

1 Introduction

1.1 Our results

Theorem 1.1.

Theorem 1.2.

Corollary 1.

1.2 Overview of the paper

2 RdR^{d}-graph: Definition and property

Definition 1 (Simplexoid).

Definition 2 (dd-Uniform-Topological hypergraph).

Definition 3 (General RdR^{d}-graph).

Definition 4 (Special RdR^{d}-graph).

Lemma 2.1 (The Construction of Special RdR^{d}-graph).

Proof.

Definition 5 (Non-special RdR^{d} Graph).

Definition 6 (Multiple Simplexoids).

Definition 7 (RdR^{d}-Loops).

Definition 8 (Simple RdR^{d}-Graph).

Definition 9 (Neighbour).

Definition 10 (Incident and Adjacent).

Definition 11 (Merging of Multiple Simplexoids).

Definition 12 (Simplexoid Deletion).

Definition 13 (Simplexoid Contraction).

Definition 14 (RdR^{d}-Embedding).

3 Triangulation of special RdR^{d}-graph (d≥3d\geq 3)

3.1 Step I: Graph-closure

Lemma 3.1.

Definition 15 (Hanging Simplexoid).

Lemma 3.2.

Proof.

Definition 16 (Graph-Closure).

Definition 17 (Closed-RdR^{d}-Graph).

Theorem 3.1.

Proof.

Corollary 2.

3.2 Step II: Triangulation

Definition 18.

Definition 19.

Definition 20.

Theorem 3.2.

Proof.

Theorem 3.3.

Proof.

Lemma 3.3.

4 Coloring of special RdR^{d}-graph

4.1 Relationship between the number of vertices and edges

Definition 21 (Vertex-Hypergraph).

Theorem 4.1.

Proof.

Claim 4.1.

Proof.

Corollary 3.

Proof.

4.2 Proof of Theorem 1.2

Proof.

5 Bridges

Lemma 5.1.

Proof.

Lemma 5.2.

Proof.

Lemma 5.3.

Proof.

6 Hyper ear decomposition

Definition 22 (Hyper Ear).

Definition 23 (Hyper Ear Decomposition).

Lemma 6.1.

Proof.

Lemma 6.2.

Proof.

Lemma 6.3.

Proof.

7 Recognizing RdR^{d}-Graph

7.1 SS-component

Definition 24 (SS-component).

Lemma 7.1.

Proof.

Lemma 7.2.

Proof.

Lemma 7.3.

Proof.

2 $R^{d}$ -graph: Definition and property

Definition 2 ( $d$ -Uniform-Topological hypergraph).

Definition 3 (General $R^{d}$ -graph).

Definition 4 (Special $R^{d}$ -graph).

Lemma 2.1 (The Construction of Special $R^{d}$ -graph).

Definition 5 (Non-special $R^{d}$ Graph).

Definition 7 ( $R^{d}$ -Loops).

Definition 8 (Simple $R^{d}$ -Graph).

Definition 14 ( $R^{d}$ -Embedding).

3 Triangulation of special $R^{d}$ -graph ( $d\geq 3$ )

Definition 17 (Closed- $R^{d}$ -Graph).

4 Coloring of special $R^{d}$ -graph

7 Recognizing $R^{d}$ -Graph

7.1 $S$ -component

Definition 24 ( $S$ -component).

7.3 Anti- $d$ -dimension minor

Definition 25 (Complete $i$ -Uniform-Topological Hypergraph $K_{n}^{i}$ ).

Definition 26 (Complete Bipartite $i$ -Uniform-Topological Hypergraph $K_{p,q}^{i}$ ).

Definition 27 (Anti- $d$ -dimension Minor).