Generalized Borsuk Graphs

Francisco Martinez-Figueroa

Abstract

Given a finite group $G$ acting freely on a compact metric space $M$ , and $\varepsilon>0$ , we define the $G$ -Borsuk graph on $M$ by drawing edges $x\sim y$ whenever there is a non-identity $g\in G$ such that $\mathbbm{d}\left(x,gy\right)\leq\varepsilon$ . We show that when $\varepsilon$ is small, its chromatic number is determined by the topology of $M$ via its $G$ -covering number, which is the minimum $k$ such that there is a closed cover $M=F_{1}\cup\dots\cup F_{k}$ with $F_{i}\cap g(F_{i})=\emptyset$ for all $g\in G\setminus\{\mathbbm{1}\}$ . We are interested in bounding this number. We give lower bounds using $G$ -actions on Hom-complexes, and upper bounds using a recursive formula on the dimension of $M$ . We conjecture that the true chromatic number coincides with the lower bound, and give computational evidence. We also study random $G$ -Borsuk graphs, which are random induced subgraphs. For these, we compute thresholds for $\varepsilon$ that guarantee that the chromatic number is still that of the whole $G$ -Borsuk graph. Our results are tight (up to a constant) when the $G$ -index and dimension of $M$ coincide.

1 Introduction

Given $\varepsilon>0$ and $d\geq 1$ , the Borsuk graph $\text{Bor}^{d}(\varepsilon)$ is the infinite graph with vertex set the unit $d$ -sphere $\mathbb{S}^{d}$ and edges $x\sim y$ whenever $\mathbbm{d}_{\mathbb{S}^{d}}\left(x,y\right)\geq\pi-\varepsilon$ , that is, if the two points are $\varepsilon$ -almost antipodal. It is well known that when $\varepsilon$ is sufficiently small, its chromatic number is $d+2$ , which follows from the topology of $\mathbb{S}^{d}$ via Borsuk-Ulam’s Theorem, and an explicit $(d+2)$ coloring given by projecting the facets of an inscribed regular $(d+1)$ -simplex (see e.g. [Mat08, KMF20]).

The Borsuk graph has been studied in relation to Borsuk’s conjecture and distance graphs (see e.g. [Rai12, PRS17, Sag18, BM14]). It is also mentioned in Lovász’s proof of Kneser’s conjecture [Lov78] where he initiated the study of topological obstructions to the chromatic number of graphs. This study has been continued, among others, by Babson’s and Kozlov’s work on the topology of Hom-complexes of graphs [BK03, BK06, Koz08]. In [Kah07], Kahle computed that these topological lower bounds are not efficient for the chromatic number of Erdős–Rényi random graphs. In contrast, in [KMF20] we showed that the topology of the underlying $d$ -sphere still dictates the chromatic number of random Borsuk graphs, and we described the threshold of $\varepsilon$ for this to happen.

Regarding the antipodal map on a sphere as an action of the cyclic group of order two $\mathbb{Z}_{2}=\{\mathbbm{1},\nu\}$ , we can equivalently define the Borsuk graph $\text{Bor}^{d}(\varepsilon)$ as the graph with vertices $\mathbb{S}^{d}$ , and edges $x\sim y$ whenever $\mathbbm{d}_{\mathbb{S}^{d}}\left(x,\nu(y)\right)\leq\varepsilon$ . This formulation naturally generalizes the Borsuk graphs to any metric space where a group $G$ acts. Thus, if $G$ is a group acting on a metric space $M$ , and $\varepsilon>0$ is given, the $G$ -Borsuk graph on $M$ , denoted $\mathcal{G}_{G}\left(M,\varepsilon\right)$ , is the graph with vertex set $M$ , and edges $x\sim y$ whenever there exist $g\in G,g\neq\mathbbm{1}$ s.t. $\mathbbm{d}_{M}\left(x,gy\right)\leq\varepsilon$ . In this paper, we study the chromatic number of such $G$ -Borsuk graphs, when $G$ is a finite group and the underlying space $M$ is finitely triangulable.

Just as with regular Borsuk graphs, the chromatic number of $G$ -Borsuk graphs is determined by the topology of the underlying space, however accurately bounding these requires more work. To get lower bounds, we study the corresponding hom-complexes as $G$ -spaces, applying standard tools for $G$ -spaces as described in [Mat08, Ch. 6]. We also establish some upper bounds, however this are far away from the lower bounds. Computer-aided examples suggest that the topological lower bounds might actually tight.

We also generalize the random Borsuk graphs studied in [KMF20]: a random $G$ -Borsuk graph on $M$ , is the induced subgraph by taking $n$ uniform i.i.d. random points on $M$ . For these, we exhibit threshold for $\varepsilon$ such that asymptotically almost surely the chromatic number of the random subgraph coincides with that of the whole $G$ -Borsuk graph.

This paper is organized as follows. In section 2, we summarize the necessary background on $G$ -spaces and $G$ -simplicial complexes needed for the following sections. We also recall the definition of graph homomorphisms, and describe some conventions that we use throughout this paper. In section 3, we summarize our definitions and theorems about $G$ -Borsuk graphs. In section 4, we prove the topological lower bound for the chromatic number. In section 5, we prove our upper bound. In section 6, we study the random $G$ -Borsuk graphs. Finally, we include an appendix where we describe our approach to produce computer-aided examples.

2 Background

In this section we recall the standard definitions and properties of $G$ -spaces and $G$ -simplicial complexes, including $E_{d}G$ spaces and the $G$ -index. Our exposition follows very closely that of Matoušek in [Mat08, Ch. 6]. We also include the definition of graph homomorphisms and their relation to graph colorings (see more at [HN04, Ch. 1]). In addition, we make some useful conventions for the remainder of this paper.

Definition 2.1 ( $G$ -spaces).

Given a finite group $G$ , a topological space $M$ , is a $\bm{G}$ -space if $G$ acts on $M$ via continuous maps. We say it is a free $\bm{G}$ -space if the $G$ -action is free, that is, if for all $g\in G$ , $g\neq\mathbbm{1}$ the map $g:M\to M$ has no fixed points.

Definition 2.2 (Simplicial $G$ -spaces).

Let $G$ be a finite group.

•

A simplicial complex $K$ is a $\bm{G}$ -simplicial complex if $G$ acts on $K$ via simplicial maps. We say the action is free, if for every face $\sigma\in K$ and every $g\in G$ with $g\neq\mathbbm{1}$ , we have $\sigma\cap g\sigma=\emptyset$ .
•

Moreover, a geometric realization of $K$ , is a geometric $\bm{G}$ -simplicial complex, if $G$ acts on it via linear extensions of simplicial maps. In this case, we consider $\|K\|$ as a metric space with the shortest path distance. Note that the $G$ -action is indeed continuous with this metric. (Here, and throughout this paper, $\|\cdot\|$ denotes a fixed geometric realization).

In this paper: we will only consider free $\bm{G}$ -spaces and free $\bm{G}$ -simplicial complexes, even if we don’t say this explicitly.

Note that $K$ being a free $G$ -simplicial complex is a stronger condition than just asking it to be free on the geometric realization. However, if $K$ is a compact triangulable space and $G$ acts on it freely, we can always find a small enough triangulation such that the simplicial approximation theorem produces a free $G$ -simplicial complex.

We will mostly focus on compact metric $G$ -spaces where the actions are via Lipschitz maps or isometries. Note that when $K$ is a geometric $G$ -simplicial complex, $G$ acts on it via piece-wise linear maps. Thus, if $K$ has a finite number of faces, the $G$ -action is automatically Lipschitz.

Definition 2.3 ( $G$ -maps).

Let $G$ be a finite group.

1.

Let $X$ and $Y$ be $G$ -spaces. A map $\varphi:X\to Y$ is a $\bm{G}$ -map if $\varphi(g(x))=g(\varphi(x))$ for all $x\in X$ , and all $g\in G$ .
2.

Let $K$ and $M$ be $G$ -simplicial complexes. A simplicial map $\varphi:K\to M$ is a $G$ -map if $\varphi(gv)=g\varphi(v)$ for all $v\in V(K)$ and all $g\in G$ .

Notation: In both cases we denote that $\varphi$ is a $G$ -map by writing $\varphi:X\xrightarrow{G}Y$ . We will also write just $X\xrightarrow{G}Y$ , to mean that there exists some $G$ -map from $X$ to $Y$ . It is straightforward to check that composition of $G$ -maps produces a $G$ -map and that the identity is trivially a $G$ -map. More generally, $G$ -spaces with $G$ -maps form a category, and (geometric) $G$ -simplicial complexes with $G$ -maps form a category as well.

When $G=\mathbb{Z}_{2}$ , the canonical example of a $\mathbb{Z}_{2}$ -space is the $d$ -sphere $\mathbb{S}^{d}$ with the antipodal map. For examples of $\mathbb{Z}_{2}$ -simplicial complexes, we can take any triangulation of $\mathbb{S}^{d}$ that is symmetrical with respect to the origin. In particular, the cross-polytopes $\diamond^{d}$ provide a family of such examples. Having one canonical $\mathbb{Z}_{2}$ -space for each dimension, makes the spheres the perfect benchmark for comparing with other $\mathbb{Z}_{2}$ -spaces. The idea of benchmark spaces can be extended to other groups via the finite classifying spaces $E_{d}G$ , here again we follow the notation of [Mat08].

Definition 2.4 (Finite Classifying Spaces).

Let $G$ be a finite group, and $d\geq 0$ . A finite classifying space of dimension $\bm{d}$ , denoted $E_{d}G$ , is

1.

a finite free $G$ -simplicial complex,
2.

$d$ -dimensional, and
3.

$(d-1)$ -connected

This definition doesn’t rule out the existence of different $E_{d}G$ classifying spaces for the same group $G$ and dimension $d$ . However, they are always $G$ -equivalent in the sense that if both $X$ and $Y$ are $E_{d}G$ spaces, then we always have $\|X\|\xrightarrow{G}Y$ and $\|Y\|\xrightarrow{G}X$ [Mat08, Lemma 6.2.2 ]. Let us give some useful examples of $E_{d}G$ spaces.

Examples 2.5.

1.

For $G=\mathbb{Z}_{2}$ , any symmetrical triangulation of $\mathbb{S}^{d}$ is a $E_{d}\mathbb{Z}_{2}$ space. In particular, the $d$ -dimensional cross-polytope $\diamond^{d}$ , which can be described via simplicial joins as

$\diamond^{d}=(\mathbb{S}^{0})^{*(d+1)}=\underbrace{\mathbb{S}^{0}*\cdots*\mathbb{S}^{0}}_{d+1\text{ times}}.$
2.

By some abuse of notation, we can regard a finite group $G$ as a $0$ -dimensional simplicial complex with its vertices labeled by the elements of the group. Then, for any $d\geq 0$ , $G$ acts freely on the space $G^{*(d+1)}$ via left-multiplication on each coordinate of the simplicial join. By elementary properties of the simplicial join operation, $G^{*(d+1)}$ is $(d-1)$ -connected and $d$ -dimensional, so it is an $E_{d}G$ classifying space. Also, by the symmetries of this construction, it can be seen that it can be realized by a geometric simplicial complex where $G$ acts via isometries.
3.

Every cyclic group $\mathbb{Z}_{m}$ acts freely on $\mathbb{S}^{1}$ via $(2\pi)/m$ rotations. Since $\mathbb{S}^{1}$ is 1-dimensional and connected, it gives a $E_{1}\mathbb{Z}_{m}$ space.
4.

Following the previous item, each cyclic group $\mathbb{Z}_{m}$ acts freely on the space $\mathbb{Z}_{m}*\mathbb{S}^{1}$ , which is simply-connected and 2-dimensional, so it is a $E_{d}\mathbb{Z}_{m}$ space. We can understand this space as a collection of $m$ cones over the same $\mathbb{S}^{1}$ . Pictorially, we represent these spaces by showing each $v*\mathbb{S}^{1}$ as an independent disk, where the boundaries must be identified. We use this depiction in Figure 1(d), where we draw the disks at the vertices of a regular $m$ -gon, so that the $\mathbb{Z}_{m}$ action can be observed by rotating the picture by multiples of $2\pi/m$ .

Comparing any $G$ -space with the finite classifying spaces, the $G$ -index is defined as follows.

Definition 2.6 ( $G$ -index).

For a $G$ -space $M$ , its $\bm{G}$ -index is defined as

\text{ind}_{G}\left(M\right):=\min\{d:M\xrightarrow[]{G}E_{d}G\}

We summarize some properties of the $G$ -index.

Theorem 2.7 ([Mat08, Prop. 6.2.4]).

1.

If $X\xrightarrow{G}Y$ then $\text{ind}_{G}\left(X\right)\leq\text{ind}_{G}\left(Y\right)$ .
2.

$\text{ind}_{G}\left(E_{d}G\right)=d$ for all $d\geq 0$ .
3.

$\text{ind}_{G}\left(X*Y\right)\leq\text{ind}_{G}\left(X\right)+\text{ind}_{G}\left(Y\right)+1$ .
4.

If $X$ is $k$ -connected, then $\text{ind}_{G}\left(X\right)\geq k+1$ .
5.

If $K$ is a free simplicial $G$ -complex of dimension $d$ , then $\text{ind}_{G}\left(X\right)\leq d$ .

Note item 2 is a generalization of Borsuk–Ulam’s Theorem, and guarantees the $G$ -index is well defined.

Throughout this paper whenever we say $H$ is a graph, we mean it is a finite, simple, loop-less graph. That is, its vertex set $V(H)$ is a finite set, and its edges $E(H)$ are unordered pairs of vertices. We will also use the notation $u\sim v$ between vertices of $H$ , to represent the edge $\{u,v\}\in E(H)$ . We will denote the complete graph on $m$ vertices by $K_{m}$ . The next couple of definitions are meant as a quick review of graph homomorphisms and colorings, for a more detailed exposition see [HN04, Ch. 1].

Definition 2.8.

Given two graphs $H_{1}$ and $H_{2}$ , a graph homomorphism from $H_{1}$ to $H_{2}$ is a function $f:V(H_{1})\to V(H_{2})$ defined on their vertices such that whenever $u\sim v$ in $H_{1}$ then also $f(u)\sim f(v)$ in $H_{2}$ .

We can thus understand graph homomorphisms as functions that send vertices to vertices and edges to edges. We will denote them as $f:H_{1}\to H_{2}$ . Again, we may just write $H_{1}\to H_{2}$ to mean that there exists some graph homomorphism from $H_{1}$ to $H_{2}$ . It is known that the collection of graphs with graph homomorphisms form a category (see [Koz08, HN04]).

Given two graphs $H_{1}$ and $H_{2}$ , we will denote the set of graph homomorphisms from $H_{1}$ to $H_{2}$ as $\text{Hom}(H_{1},H_{2})$ . Babson and Kozlov [BK03, BK06] introduced a canonical way of endowing $\text{Hom}(H_{1},H_{2})$ with a topological structure. We will discuss more about it in section 5.

Graph colorings and chromatic number can also be described via graph homomorphisms.

Definition 2.9.

Given a graph $H$ , an m-coloring is a graph homomorphism $\varphi:H\to K_{m}$ . The chromatic number of $H$ , is the least $m$ such that an $m$ -coloring exits, i.e.

\chi(H):=\min\{m:\text{Hom}(H,K_{m})\neq\emptyset\}.

3 Definitions and Results

We start by giving a definition that generalizes Borsuk graphs on spheres to any metric $G$ -space.

Definition 3.1 ( $G$ -Borsuk Graphs).

Let $G$ be a finite group. For a metric $G$ -space $M$ , $X\subset M$ , and $\varepsilon>0$ we define the $\bm{G}$ -Borsuk Graph $\mathcal{G}_{G}\left(X,\varepsilon\right)$ as the graph with vertices $V(\mathcal{G}_{G}\left(X,\varepsilon\right))=X$ and edges $x\sim y$ whenever there is a non-identity element $g\in G$ such that $\mathbbm{d}_{M}\left(x,gy\right)\leq\varepsilon$ .

Thus the $\mathbb{Z}_{2}$ -Borsuk Graph $\mathcal{G}_{\mathbb{Z}_{2}}\left(\mathbb{S}^{d},\varepsilon\right)$ , where $\mathbb{Z}_{2}$ acts on $\mathbb{S}^{d}$ via the antipodal map, is the Borsuk Graph on $\mathbb{S}^{d}$ . It is well known that the chromatic number of the $\mathbb{Z}_{2}$ -Borsuk Graph on the $d$ -Sphere is $d+2$ , which follows from Borsuk–Ulam’s Theorem (see e.g. [Mat08]). More specifically, it depends on Lyusternik–Schnirerlman’s Theorem, which is equivalent to Borsuk–Ulam’s, concerning the minimum number of open sets covering $\mathbb{S}^{d}$ s.t. they don’t contain pairs of antipodal points. In this spirit, we define the $G$ -covering number of a $G$ -metric space, and study its relation with $G$ -Borsuk graphs.

Definition 3.2 ( $G$ -covering number).

Let $G$ be a finite group. Let $M$ be a free $G$ -space. Then a (open) $\bm{G}$ -cover of $M$ is an open cover $M=U_{1}\cup\dots\cup U_{k}$ , such that $U_{i}\cap gU_{i}=\emptyset$ for all $i=1,\dots,k$ and all $g\in G,g\neq\mathbbm{1}$ . Then the (open) $\bm{G}$ -covering number of $M$ is:

\text{cov}_{G}\left(M\right)=\min\{k:\text{ there exists a }G\text{-cover }M=U_{1}\cup\dots\cup U_{k}\}

Similarly, we define closed $G$ -covers and the closed $\bm{G}$ -covering number of $M$ , $\overline{\text{cov}_{G}\left(M\right)}$ , using closed covers instead.

Notation:

Theorem 4.1 will show that the open and closed covering numbers coincide for compact spaces, and that they are invariant under $G$ -equivalence. Since all $E_{d}G$ spaces are $G$ -equivalent, the $G$ -covering number $\text{cov}_{G}\left(E_{d}G\right)$ is independent of the specific classifying space, so we will denote it simply as $\text{cov}_{G}\left(d\right)$ .

The $G$ -covering number the chromatic number of $G$ -Borsuk graphs on the same space are related via the next result.

Theorem 3.3.

If $M$ is a compact metric space and $G$ acts via Lipschitz maps. Then there exist constants $D$ and $\varepsilon_{0}$ such that for any $0<\varepsilon<\varepsilon_{0}$ and any $X\subset M$ a $(\varepsilon/D)$ -net of $M$ , we have

\chi\left(\mathcal{G}_{G}\left(X,\varepsilon\right)\right)=\text{cov}_{G}\left(M\right).

This relationship is what motivates us to find bounds for the $G$ -covering number, and, at the same time this duality is one of our main tools finding these bounds.

Theorem 3.4.

Let $G$ be a finite group and $K$ a geometric $G$ -simplicial complex. Let $k=\text{ind}_{G}\left(K\right)$ . Then

k+|G|\leq\text{cov}_{G}\left(K\right)\leq k(|G|-1)+2.

Thus we get linear upper and lower bounds for $\text{cov}_{G}\left(K\right)$ , depending only on the size of $G$ and the $G$ -index of $K$ . In the case $G=\mathbb{Z}_{2}$ we get the tight result $\text{cov}_{G}\left(K\right)=\text{ind}_{\mathbb{Z}_{2}}\left(K\right)+2$ , where the lower bound is a generalization of Lyusternik–Schnirelmann–Borsuk Theorem, and the upper bound is obtained by “coloring” the facets of a regular $(k+1)$ -dimensional simplex inscribed in $\mathbb{S}^{k}$ (see e.g.[KMF20, Mat02]).

In general, we conjecture that the lower bound gives the true chromatic number. If $K$ has $G$ -index $k$ , then $K\xrightarrow{G}E_{k}G$ , and so by Theorem 4.1, $\text{cov}_{G}\left(K\right)\leq\text{cov}_{G}\left(E_{k}G\right)=\text{cov}_{G}\left(k\right)$ , so we only need to upper bound the $G$ -covering number for $E_{d}G$ spaces. Thus, we state our conjecture as follows.

Conjecture 3.5.

Let $G$ be a finite group. Then $\text{cov}_{G}\left(d\right)=|G|+d$ .

We also state the following less general conjectures, which may hold even if Conjecture 3.5 results to be false.

Conjecture 3.6.

1.

For $m\geq 2$ and $d\geq 0$ ,

$\text{cov}_{\mathbb{Z}_{m}}\left(d\right)=m+d.$
2.

Let $G$ be a finite group. Then $\text{cov}_{G}\left(d\right)<\text{cov}_{G}\left(d+1\right)$ for all $d\geq 0$ .

Notice that item 2 in the conjecture asks if $\text{cov}_{G}\left(\cdot\right)$ is strictly increasing, since the fact that it is weakly monotone follows trivially from the $G$ -map $E_{d}G=G^{*(d+1)}\xhookrightarrow{G}G^{*(d+2)}=E_{d+1}G$ , and Theorem 4.1.

Table 1 summarizes the cases for which we have been able to compute $\text{cov}_{G}\left(d\right)$ exactly. Notice that for all of these, Conjecture 3.5 holds. Specific $\mathbb{Z}_{m}$ -coverings for $E_{2}\mathbb{Z}_{m}$ when $m=3,4,5$ and 6 are shown in Figure 1(d). Here we use $\mathbb{Z}_{m}*\mathbb{S}^{1}$ as $E_{2}\mathbb{Z}_{m}$ space, and is depicted as described in Examples 2.5. These $G$ -covers were found solving integer linear programming problems with the free software [SageMath] and a student license of [Gurobi]. We further explain our approach in the appendix.

$\bm{G}$ -Index	Group	Covering Number
$\bm{d}$	$\bm{G}$	cov $\bm{{}_{G}(d)}$
any $d\geq 0$	$\mathbb{Z}_{2}$	$d+2$
0	any $G$	$\|G\|$
1	any $G$	$\|G\|+1$
2	$\mathbb{Z}_{3}$	5
	$\mathbb{Z}_{4}$	6
	$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$	6
	$\mathbb{Z}_{5}$	7
	$\mathbb{Z}_{6}$	8
3	$\mathbb{Z}_{3}$	6

Table 1: Known Covering Numbers

Refer to caption — (a) A cover of $E_{2}\mathbb{Z}_{3}$ with 5 colors.

The lower bound in Theorem 3.4, provides a generalization of the Lyusternik–Schnirelmann–Borsuk Theorem to $G$ -spaces.

Corollary 3.7 (Generalization of LSB-Theorem).

Let $G$ be a finite group and $K$ a finite $G$ -simplicial complex. Suppose $M$ is $d$ -connected and $|G|=m$ . If $M=U_{1}\cup\dots\cup U_{d+m}$ is an open (or closed) cover of $K$ , then there exist $x\in K$ , an index $1\leq i\leq d+m$ and an element $g\in G\setminus\{\mathbbm{1}\}$ such that $x,g(x)\in U_{i}$ .

Proof.

By Theorem 2.7, $\text{ind}_{G}\left(K\right)\geq d+1$ , and by Theorem 3.4, $\text{cov}_{G}\left(K\right)\geq\text{ind}_{G}\left(K\right)+|G|\geq m+d+1$ . Thus there are not open (nor closed, by Theorem 4.1) $G$ -covers of $K$ . ∎

We also generalize the random Borsuk graphs studied in [KMF20] to random induced subgraphs of $G$ -Borsuk graphs.

Definition 3.8 (Random $G$ -Borsuk graphs).

Let $G$ be a finite group, and $M$ a compact metric $G$ -space. We define the random $G$ -Graph on $M$ , denoted by $\mathcal{G}_{G}\left(n,\varepsilon\right)$ , as the $G$ -Borsuk graph $\mathcal{G}_{G}\left(X(n),\varepsilon\right)$ , where $X(n)=\{x_{1},\dots,x_{n}\}$ is a set of $n$ i.i.d. uniform random points on $M$ .

In the same spirit as Theorems 1.2 and 1.3 of [KMF20], the next result provides a tight threshold (up to a constant) for $\varepsilon$ , such that the random $G$ -Borsuk graphs have the chromatic number equal to the $G$ -covering number of its dimension. In this theorem, and throughout this paper, we will say that a random event $A_{n}$ happens asymptotically almost surely (a.a.s.) if $\mathbb{P}\left[A_{n}\right]\to 1$ as $n\to\infty$ .

Theorem 3.9.

Let $G$ be a finite group and $K$ a geometric $E_{d}G$ space. Then, there exist constants $C_{1}$ and $C_{2}$ (independent from $n$ ), such that:

1.

If $\varepsilon\geq C_{1}\left(\frac{\log n}{n}\right)^{1/d}$ , then a.a.s. $\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))=\text{cov}_{G}\left(d\right).$
2.

If $\varepsilon\leq C_{2}\left(\frac{\log n}{n}\right)^{1/d}$ , then a.a.s. $\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))\leq\text{cov}_{G}\left(d-1\right).$

Instead of proving Theorem 3.9, we will prove the more general Theorem 7.2, which can be applied to any geometric $G$ -simplicial complex, even when the $G$ -index and dimension don’t coincide. However, in such general cases, the thresholds found don’t coincide.

A nice application of $G$ -Borsuk graphs, is that they can produce graphs with large chromatic number and prescribed clique number. A similar construction using $G$ -actions can also be found in [Dan18].

Corollary 3.10.

Given $m\leq t$ integers, there is a graph $H$ such that $\omega(H)=m$ and $\chi(H)\geq t$ .

Proof.

Let $G$ be any group of order $m$ , and let $d=t-m$ . Consider $K$ a geometric $E_{d}G$ space. Let $\varepsilon_{1}$ and $D_{1}$ be the corresponding constants given by Theorem 4.2, and $\varepsilon_{2}$ , $D_{2}$ , the ones given by Lemma 4.3. Let $\varepsilon_{0}=\min\{\varepsilon_{1},\varepsilon_{2}\}$ and $D=\max\{D_{1},D_{2}\}$ . Take any $X\subset E_{d}G$ , an $(\varepsilon/D)$ -net, for some $\varepsilon<\varepsilon_{0}$ . Take $H=\mathcal{G}_{G}\left(X,\varepsilon\right)$ . Then, by Lemma 4.3, $\omega(H)=m$ . And by Theorems 4.2 and 3.4,

\chi(H)=\text{cov}_{G}\left(d\right)\geq|G|+d=t.

∎

4 Properties of $\bm{\text{cov}_{G}}$

In this section we state and prove the main properties of $\text{cov}_{G}\left(\cdot\right)$ and its relationship with the chromatic number of $G$ -Borsuk graphs. The following Theorem summarizes a few of these properties.

Theorem 4.1.

Let $G$ be a finite group, and $M$ and $K$ be $G$ -spaces. Then:

1.

If $M\xrightarrow[]{G}K$ , then $\text{cov}_{G}\left(M\right)\leq\text{cov}_{G}\left(K\right)$ . In particular, if $M$ and $K$ are $G$ -equivalent, $\text{cov}_{G}\left(M\right)=\text{cov}_{G}\left(K\right)$ .
2.

If $\varphi:M\xrightarrow{G}K$ is a Lipschitz map with constant $\lambda$ , then for any $X\subset M$ , and any $\varepsilon>0$ , it induces a graph homomorphism

$\varphi:\mathcal{G}_{G}\left(X,\varepsilon\right)\to\mathcal{G}_{G}\left(\varphi(X),\lambda\varepsilon\right).$
3.

If $M$ is a compact metric space and $G$ -acts via Lipschitz maps, then $\text{cov}_{G}\left(M\right)=\overline{\text{cov}_{G}\left(M\right)}.$ So the covering number can be computed using either open or closed covers.
4.

If $G^{\prime}\leq G$ is a subgroup, then $\text{cov}_{G^{\prime}}\left(M\right)\leq\text{cov}_{G}\left(M\right)$

Proof.

1.

Let $k=\text{cov}_{G}\left(K\right)$ , we may assume $k<\infty$ otherwise there’s nothing to prove. Thus there is an open $G$ -cover $K=U_{1}\cup\dots\cup U_{k}$ such that $U_{i}\cap g(U_{j})=\emptyset$ for all $i$ and all $g\in G\setminus\{\mathbbm{1}\}$ . Let $f:M\xrightarrow[]{G}K$ , then $M=f^{-1}(U_{1})\cup\dots\cup f^{-1}(U_{k})$ gives an open cover for $M$ . Moreover, for each $i$ , and $g\in G\setminus\{\mathbbm{1}\}$ , we have

$f(\left(f^{-1}(U_{i})\cap g(f^{-1}(U_{i}))\right)\subset U_{i}\cap g(U_{i})=\emptyset$

so the sets $f^{-1}(U_{i})$ are an open $G$ -cover for $M$ . Therefore, $\text{cov}_{G}\left(M\right)\leq k=\text{cov}_{G}\left(K\right)$ .

We just need to check that $\varphi$ maps edges to edges. Take $x\sim y$ in $\mathcal{G}_{G}\left(X,\varepsilon\right)$ , so $x,y\in X$ and there is some $g\in G,g\neq\mathbbm{1}$ s.t. $\mathbbm{d}_{M}\left(x,gy\right)\leq\varepsilon$ . Since $\varphi$ is Lipschitz with constant $\lambda$ , then

\mathbbm{d}_{K}\left(\varphi(x),g\varphi(y)\right)=\mathbbm{d}_{K}\left(x,\varphi(gy)\right)\leq\lambda\mathbbm{d}_{M}\left(x,gy\right)\leq\lambda\varepsilon,

and so $\varphi(x)\sim\varphi(y)$ in $\mathcal{G}_{G}\left(\varphi(X),\lambda\varepsilon\right)$ . Thus $\varphi$ induces a graph homomorphism.

We may assume both $\text{cov}_{G}\left(M\right)$ and $\overline{\text{cov}_{G}\left(M\right)}$ are finite. If one of them is finite, the following proof gives that the other must be finite as well. Otherwise, they are both infinite.

•

Let $k=\overline{\text{cov}_{G}\left(M\right)}$ . Write $M=F_{1}\cup\dots\cup F_{k}$ , where the $F_{i}$ ’s are a closed $G$ -cover. Note $F_{i}\times F_{i}$ is compact, and for each $g\neq\mathbbm{1}$ , the map $\mathbbm{d}\left(\cdot,g(\cdot)\right):F_{i}\times F_{i}\to\mathbb{R}^{+}$ is continuous (it is indeed positive, because $F_{i}\cap g(F_{i})=\emptyset$ ). Since $b_{i,g}:=\min\{\mathbbm{d}\left(x,g(y)\right):x,y\in F_{i}\}$ is attained, it must be that $b_{i,g}>0$ . Let $b=\min\{b_{i,g}:1\leq i\leq k,g\in G,g\neq\mathbbm{1}\}$ , note $b>0$ .

Since $G$ acts via Lipschitz maps, let $\lambda_{g}$ be the corresponding Lipschitz constant for the map $g\in G\setminus\{\mathbbm{1}\}$ . Let $D=1+\max\{\lambda_{g}:g\in G,g\neq\mathbbm{1}\}$ . For each $i=1,\dots,k$ define $U_{i}=\bigcup_{x\in F_{i}}\text{int}\left(B(x,b/D)\right)$ . Thus the $U_{i}$ ’s are open, and since $F_{i}\subset U_{i}$ , they also cover $M$ . Now we prove the $U_{i}$ ’s are a $G$ -cover.

Suppose by way of contradiction that $y\in U_{i}\cap g(U_{i})$ . So there is $y^{\prime}\in U_{i}$ with $y=g(y^{\prime})$ . By definition of $U_{i}$ , there are $x,x^{\prime}\in F_{i}$ such that $\mathbbm{d}\left(x,y\right)<b/D$ and $\mathbbm{d}\left(x^{\prime},y^{\prime}\right)<b/D$ . Then

	$\displaystyle b\leq b_{i,g}\leq\mathbbm{d}\left(x,g(x^{\prime})\right)$	$\displaystyle\leq\mathbbm{d}\left(x,y\right)+\mathbbm{d}\left(y,g(x^{\prime})\right)=\mathbbm{d}\left(x,y\right)+\mathbbm{d}\left(g(y^{\prime}),g(x^{\prime})\right)$
		$\displaystyle\leq\mathbbm{d}\left(x,y\right)+\lambda_{g}\mathbbm{d}\left(y^{\prime},x^{\prime}\right)<\frac{b}{D}+\lambda_{g}\frac{b}{D}=\frac{1+\lambda_{g}}{D}b\leq b$

But $b<b$ is a contradiction, so $U_{i}\cap g(U_{i})=\emptyset$ for all $i$ , $g\neq\mathbbm{1}$ . Therefore, $\text{cov}_{G}\left(M\right)\leq\overline{\text{cov}_{G}\left(M\right)}$ .

•

Let $k=\text{cov}_{G}\left(M\right)$ . Write $M=U_{1}\cup\dots\cup U_{k}$ , where the $U_{i}$ ’s are an open $G$ -cover. For each $x\in M$ , choose a superset $x\in U_{i}$ , and let $F_{x}$ be a closed neighborhood of $x$ contained in $U_{i}$ . The collection $\{\text{interior}(F_{x}):x\in M\}$ is an open cover of $M$ , by compactness, there is a finite subcover $\mathcal{C}$ .

For each $i=1,\dots,k$ , let $F_{i}=\bigcup F_{x}$ taking the union over the closed sets such that $\text{interior}(F_{x})\in\mathcal{C}$ and $F_{x}\subset U_{i}$ . Thus $F_{1},\dots,F_{k}$ is a closed cover of $M$ . Since $F_{i}\subset U_{i}$ , trivially $F_{i}\cap g(F_{i})=\emptyset$ for all $i$ , $g\in G$ , $g\neq\mathbbm{1}$ . Therefore $\overline{\text{cov}_{G}\left(M\right)}\leq\text{cov}_{G}\left(M\right)$ .

4.

Note any $G$ -cover of $M$ , will also be a $G^{\prime}$ -cover of $M$ , so trivially $\text{cov}_{G^{\prime}}\left(M\right)\leq\text{cov}_{G}\left(M\right)$ . ∎

In the remainder of this paper we will only work on compact $G$ -spaces. Theorem 4.1 establishes that the open and closed $G$ -covering numbers coincide for compact spaces, so we will always denote it simply by $\text{cov}_{G}\left(M\right)$ , even though most of the times we will produce closed $G$ -covers.

The next Theorem explains the relation between the $G$ -covering of a space and the chromatic number of a $G$ -Borsuk graph on the same space. We choose to state this relation via two separate inequalities, since for some of the later results, we will only require one or the other. Theorem 3.3 will then follow immediately.

Theorem 4.2.

Let $G$ be a finite group, and $M$ a compact metric $G$ -space s.t. $G$ acts on $M$ via Lipschitz maps. Then the following hold.

1.

There exists a constant $D$ s.t. if $X\subset M$ is an $(\varepsilon/D)$ -net, we have

$\text{cov}_{G}\left(M\right)\leq\chi(\mathcal{G}_{G}\left(X,\varepsilon\right)).$
2.

There exists a constant $\varepsilon_{0}>0$ s.t. for any $X\subset M$ , and any $0<\varepsilon<\varepsilon_{0}$ we have

$\chi(\mathcal{G}_{G}\left(X,\varepsilon\right))\leq\text{cov}_{G}\left(M\right).$

Proof.

Let $k=\text{cov}_{G}\left(M\right)$ , so we can write $M=F_{1}\cup\dots\cup F_{k}$ , where the $F_{i}$ ’s are a closed $G$ -cover. Using the same notation as in the proof of Theorem 4.1 item 3, there exists $b,D>0$ such that

b\leq\mathbbm{d}\left(x,g(y)\right)\;\forall x,y\in F_{i},\;i=1,\dots,k,\;g\in G\setminus\{\mathbbm{1}\},\text{ and}

\mathbbm{d}\left(g(x),g(y)\right)\leq(D-1)\mathbbm{d}\left(x,y\right)\;\forall x,y\in M,\;g\in G\setminus\{\mathbbm{1}\}.

Let $X\subset M$ be a $(\varepsilon/D)$ -net of $M$ . Suppose by way of contradiction that there is a proper $(k-1)$ -coloring for $\mathcal{G}_{G}\left(X,\varepsilon\right)$ , and fix such a coloring. For each color $i=1,\dots,k-1$ define

U_{i}=\bigcup_{\begin{subarray}{c}v\in X\\ v\text{ has color }i\end{subarray}}\text{int}\left(B\left(v,\frac{\varepsilon}{D}\right)\right).

Since $X$ is an $(\varepsilon/D)$ -net of $M$ , the $U_{i}$ ’s are an open cover of $M$ . Suppose there is an index $i$ and a non-identity $g\in G$ such that $x\in U_{i}\cap g(U_{i})$ . Thus $x=g(x^{\prime})$ for some $x^{\prime}\in U_{i}$ . By definition, there are vertices $v,v^{\prime}\in X$ of color $i$ such that $\mathbbm{d}\left(x,v\right)\leq\varepsilon/D$ and $\mathbbm{d}\left(x^{\prime},v^{\prime}\right)\leq\varepsilon/D$ . But then

	$\displaystyle\mathbbm{d}\left(v,g(v^{\prime})\right)$	$\displaystyle\leq\mathbbm{d}\left(v,x\right)+\mathbbm{d}\left(x,g(v^{\prime})\right)=\mathbbm{d}\left(v,x\right)+\mathbbm{d}\left(g(x^{\prime}),g(v^{\prime})\right)$
		$\displaystyle\leq\mathbbm{d}\left(v,x\right)+(D-1)\mathbbm{d}\left(x^{\prime},v^{\prime}\right)\leq\frac{\varepsilon}{D}+(D-1)\frac{\varepsilon}{D}=\varepsilon$

So $v\sim v^{\prime}$ are adjacent in $\mathcal{G}_{G}\left(X,\varepsilon\right)$ , and they both have the same color $i$ , which is absurd. Hence $U_{i}\cap g(U_{i})=\emptyset$ for all $i$ and all $g\in G\setminus\{\mathbbm{1}\}$ . But this is a $(k-1)$ open cover of $M$ , which is a contradiction since $\text{cov}_{G}\left(M\right)=k$ . Therefore $k\leq\chi(\mathcal{G}_{G}\left(X,\varepsilon\right))$ .

2.

Define $\varepsilon_{0}=b$ , and let $0<\varepsilon<\varepsilon_{0}$ . Let $X\subset M$ . We can $k$ -color the graph $\mathcal{G}_{G}\left(X,\varepsilon\right)$ via the coloring $c:X\to\{1,\dots,k\}$ given by $c(v)=\min\{i:v\in F_{i}\}$ . Indeed, if $v,w\in X$ have $c(v)=c(w)=i$ , then $v,w\in F_{i}$ , so $\mathbbm{d}\left(v,g(w)\right)\geq b>\varepsilon$ for all $g\in G\setminus\{\mathbbm{1}\}$ . Hence $v\not\sim w$ , and $c$ is a proper $k$ -coloring. Therefore $\chi(\mathcal{G}_{G}\left(X,\varepsilon\right))\leq k$ .∎

We finish this section on general properties, by computing the clique number of $G$ -Borsuk graphs. In a sense, this can be seen as a generalization of Lemma 2.2 in [KMF20], regarding the odd-girth of $\mathbb{Z}_{2}$ -Borsuk graphs.

Lemma 4.3.

Let $M$ be a compact $G$ -space such that $G$ acts via Lipschitz maps. Then, there exist constants $\varepsilon_{0}$ and $D$ such that, whenever $X\subset M$ is a $(\varepsilon/D)$ -net of $X$ and $\varepsilon<\varepsilon_{0}$ , then $\omega\left(\mathcal{G}_{G}\left(X,\varepsilon\right)\right)=|G|$ .

Proof.

Let $b=\min\{\mathbbm{d}\left(x,g(x)\right):x\in M,g\in G,g\neq\mathbbm{1}\}$ . Note $b>0$ since the $G$ -action is free and $M$ is compact. Let $m=|G|$ and enumerate $G=\{g_{1}=\mathbbm{1},g_{2},\dots,g_{m}\}$ . Let $\lambda$ be the largest Lipschitz constant of the maps $g_{i}$ . Then set $D=2\max\{\lambda,\lambda^{2}\}+2$ and $\varepsilon_{0}=b/D$ . Suppose now that $X\subset M$ is an $(\varepsilon/D)$ -net with $0<\varepsilon<\varepsilon_{0}$ . Let $z\in M$ be any point, thus for each $i=1,\dots,m$ , there is a point $x_{i}\in X$ such that $\mathbbm{d}\left(x_{i},g_{i}z\right)\leq\varepsilon/D$ . Then, for any $i\neq j$ we have

	$\displaystyle\mathbbm{d}\left(x_{i},(g_{i}g_{j}^{-1})x_{j}\right)$	$\displaystyle\leq\lambda\mathbbm{d}\left(g_{i}^{-1}x_{i},g_{j}^{-1}x_{j}\right)\leq\lambda\left(\mathbbm{d}\left(g_{i}^{-1}x_{i},z\right)+\mathbbm{d}\left(g_{j}^{-1}x_{j},z\right)\right)$
		$\displaystyle\leq\lambda^{2}\left(\mathbbm{d}\left(x_{i},g_{i}x_{i}\right)+\mathbbm{d}\left(x_{j},g_{j}z\right)\right)\leq\frac{\lambda^{2}\varepsilon}{D}<\varepsilon.$

Since $g_{i}g_{j}^{-1}\neq\mathbbm{1}$ whenever $i\neq j$ , $x_{i}\sim x_{j}$ , and so $\{x_{1},\dots,x_{m}\}$ is a $m$ -clique in $\mathcal{G}_{G}\left(X,\varepsilon\right)$ .

On the other hand, suppose by way of contradiction that $x_{0},\dots,x_{m}\in X$ is a $(m+1)$ -clique. So, in particular, for each $1\leq i\leq m$ , there is an index $k_{i}\neq 1$ s.t. $\mathbbm{d}\left(x_{0},g_{k_{i}}x_{i}\right)\leq\varepsilon$ . Hence there must be two different values $i\neq j$ , such that $g_{k_{i}}=g_{k_{j}}$ ; fix these $i$ and $j$ . Since $x_{i}\sim x_{j}$ , there must also be an element $g\in G,g\neq\mathbbm{1}$ such that $\mathbbm{d}\left(x_{j},gx_{i}\right)\leq\varepsilon$ . Then, setting $y=g_{k_{i}}^{-1}x_{0}=g_{k_{j}}^{-1}x_{0}$ , we get

	$\displaystyle\mathbbm{d}\left(x_{i},gx_{i}\right)$	$\displaystyle\leq\mathbbm{d}\left(x_{i},y\right)+\mathbbm{d}\left(x_{j},y\right)+\mathbbm{d}\left(x_{j},gx_{i}\right)$
		$\displaystyle=\mathbbm{d}\left(x_{i},g_{k_{i}}^{-1}x_{0}\right)+\mathbbm{d}\left(x_{j},g_{k_{j}}^{-1}x_{0}\right)+\mathbbm{d}\left(x_{j}+gx_{i}\right)$
		$\displaystyle\leq\lambda\mathbbm{d}\left(g_{k_{i}}x_{i},x_{0}\right)+\lambda\mathbbm{d}\left(g_{k_{j}}x_{j},x_{0}\right)+\varepsilon\leq(2\lambda+1)\varepsilon\leq(2\lambda+1)\varepsilon_{0}<b$

But this is a contradiction, so there are not $(m+1)$ -cliques, and $\omega(\chi(\mathcal{G}_{G}\left(X,\varepsilon\right)))=m=|G|$ . ∎

5 Lower Bound

In this section we focus on proving the lower bound of Theorem 3.4. This result is topological, by bounding the $G$ -index of the cellular structure of $\text{Hom}(K_{m},H)$ , following ideas of [Lov78], [BK03] and [BK06]. It is worth noting, that similar $G$ -actions on Hom-Posets have been independently studied in [Dan18]. We start by restating the result we will prove.

Theorem 5.1.

Let $G$ be a finite group and $K$ a geometric $G$ -simplicial complex. Let $k=\text{ind}_{G}\left(K\right)$ . Then $k+|G|\leq\text{cov}_{G}\left(K\right)$ .

Given two graphs $H_{1}$ and $H_{2}$ , the set of graph homomorphisms $\text{Hom}(H_{1},H_{2})$ can be endowed with a topology as a prodsimplicial complex, as introduced by Babson and Kozlov in [BK03]. Let us explain this structure.

Definition 5.2.

A cell complex is called prodsimplicial if all its cells are products of simplices. I.e. if all of its cells are of the form $\sigma=\sigma_{1}\times\dots\times\sigma_{k}$ , where $\sigma_{i}$ is a $d_{i}$ -simplex. Notation instead of using the $``\times^{\prime\prime}$ symbol, we will write $\sigma=(\sigma_{1},\dots,\sigma_{k})$ .

Definition 5.3.

Given $H_{1}$ and $H_{2}$ , $\text{Hom}(H_{1},H_{2})$ is a prodsimplicial complex with cells $\sigma$ satisfying:

1.

$\sigma=\prod_{x\in V(H_{1})}\sigma_{x}$ , where $\sigma_{x}\subset V(H_{2})$ . That is, $\sigma$ is the direct product of simplices on the vertices of $H_{2}$ , indexed by the vertices of $H_{1}$ , and
2.

If $\varphi:V(H_{1})\to V(H_{2})$ is such that $\varphi(x)\in\sigma_{x}$ for all $x\in V(H_{2})$ , then it extends to a graph homomorphism $\varphi:H_{1}\to H_{2}$ .

We highlight the following points:

•

The cells of $\text{Hom}(H_{1},H_{2})$ can be though of as indexed by functions $\eta:V(H_{1})\to\left(2^{V(H_{2})}\setminus\emptyset\right)$ , such that if $\{x,y\}\in E(H_{1})$ then $\eta(x)\times\eta(y)\subset E(H_{2})$ .
•

The dimension of the cell $\sigma$ is given by $\sum_{x\in V(G)}\text{dim}(\sigma_{x})$ . Thus the vertices (0-cells) of $\text{Hom}(H_{1},H_{2})$ are precisely the graph homomorphisms $\eta:G\to H$ .
•

The 1-skeleton can be seen as a graph, with vertices the graph homomorphisms and edges $\varphi\sim\psi$ if and only if they differ at exactly one value.

Lemma 5.4.

Let $K_{m}$ denote the complete graph with $m$ vertices. If $m\leq t$ , then

\dim\left(\text{Hom}(K_{m},K_{t})\right)=t-m

Proof.

Let $\sigma$ be a cell of $\text{Hom}(K_{m},K_{t})$ . Thus $\sigma=\prod_{i=1}^{m}\sigma_{i}=(\sigma_{1},\dots,\sigma_{m})$ where each $\sigma_{i}\subset\{1,\dots,t\}$ . By definition, when $i\neq j$ , for all possible choices $v_{i}\in\sigma_{i}$ and $v_{j}\in\sigma_{j}$ , we must have $v_{i}\sim v_{j}$ in $K_{t}$ . This is true iff $v_{i}\neq v_{j}$ . Hence, $\sigma_{i}\cap\sigma_{j}=\emptyset$ for $i\neq j$ . Then

\dim(\sigma)=\sum_{i=1}^{m}\dim(\sigma_{i})=\sum_{i=1}^{m}(|\sigma_{i}|-1)=\left(\sum_{i=1}^{m}|\sigma_{i}|\right)-m=\left|\bigcup_{i=1}^{m}\sigma_{i}\right|-m\leq|\{1,\dots,t\}|-m=t-m.

Moreover, the dimension is exactly $t-m$ , since $\sigma=(1,2,3,\dots,m-1,\{m,m+1,\dots,t\})$ is a $(t-m)$ -dimensional cell. ∎

5.1 $\bm{\text{Hom}(K_{m},\cdot)}$ as $\bm{G}$ -space.

Let $G$ be a finite group with $|G|=m$ . Enumerate $G=\{g_{1}=\mathbbm{1},g_{2},g_{3},\dots,g_{m}\}$ . By identifying the elements of $G$ with the vertices $\{1,\dots,m\}$ of the complete graph $K_{m}$ , $G$ acts on $K_{m}$ via right multiplication. For a finite graph $H$ , $G$ acts on $\text{Hom}(K_{m},H)$ as follows: If $g\in G$ , and $\sigma=(\sigma_{1},\dots,\sigma_{m})$ , then $g\sigma=(\sigma_{\pi(1)},\dots,\sigma_{\pi(m)})$ , where $\pi(i)$ is the unique index such that $g_{i}g=g_{\pi(i)}$ . Note that if $g\neq\mathbbm{1}$ , then $\pi(i)\neq i$ for all $i$ . As we pointed out in the proof of Lemma 5.4, if $\sigma$ is a cell in $\text{Hom}(K_{m},H)$ , it must be that $\sigma_{i}\cap\sigma_{j}=\emptyset$ for all $i\neq j$ , in particular,

\sigma\cap g(\sigma)\subset(\sigma_{1}\cap\sigma_{\pi(1)},\dots,\sigma_{m}\cap\sigma_{\pi(m)})=\emptyset.

So $G$ acts freely on $\text{Hom}(G,H)$ via cellular maps. Moreover, it is clear that this construction is functorial, so if $f:H\to H^{\prime}$ is a graph homomorphism, then it induces a $G$ -map

f:\text{Hom}(K_{m},H)\xrightarrow{G}\text{Hom}(K_{m},H^{\prime}).

5.2 Proof of Theorem 5.1

Let $K$ be a free $G$ -simplicial complex with $k=\text{ind}_{G}\left(K\right)$ and $m=|G|$ . Fix $\varepsilon>0$ . Let $T$ be a finer triangulation of $K$ , such that $T$ is also a $G$ -simplicial complex and $\text{diam}\left(\sigma\right)\leq\varepsilon$ for all faces $\sigma\in T$ . Let $H$ be the graph with vertex set $V(T)$ and edges $x\sim y$ whenever there exists $g\in G\setminus\{\mathbbm{1}\}$ such that $\{x,g(y)\}\in T^{(1)}$ . Note then $H$ is an induced subgraph of the $G$ -Borsuk graph $\mathcal{G}_{G}\left(V(T),\varepsilon\right)$ .

Thus if $\varepsilon<\varepsilon_{0}$ , for $\varepsilon_{0}$ the constant given by Theorem 4.2 item 2, we get

\chi(H)\leq\chi(\mathcal{G}_{G}\left(V(T),\varepsilon\right))\leq\text{cov}_{G}\left(K\right).

We will construct a $G$ -map $\Phi:T\xrightarrow{G}\text{Hom}(K_{m},H)$ . Since $H\to K_{\chi(H)}$ , the functoriality of the $G$ -action on $\text{Hom}(K_{m},\cdot)$ produces

T\xrightarrow{G}\text{Hom}(K_{m},H)\xrightarrow{G}\text{Hom}(K_{m},K_{\chi(H)}).

Finally, applying items 1 and 5 of Theorem 2.7 and the dimension computed in Lemma 5.4, we get

	$\displaystyle k$	$\displaystyle=\text{ind}_{G}\left(K\right)=\text{ind}_{G}\left(T\right)\leq\text{ind}_{G}\left(\text{Hom}(K_{m},H)\right)$
		$\displaystyle\leq\text{ind}_{G}\left(\text{Hom}(K_{m},K_{\chi(H)}\right)\leq\dim(\text{Hom}(K_{m},K_{\chi(H)}))\leq\chi(H)-m,$

so $k+m\leq\chi(H)\leq\text{cov}_{G}\left(K\right)$ as desired. From now on, we focus on defining the map $\Phi$ .

Enumerate $G=\{g_{1}=\mathbbm{1},g_{2},g_{3},\dots,g_{m}\}$ . Let $\sigma$ be a $d$ -dimensional face of $K$ , for any $0\leq d\leq\dim(K)$ . Let $\Psi_{\sigma}=\prod_{g\in G}g(\sigma)=(\sigma,g_{2}(\sigma),g_{3}(\sigma),\dots,g_{m}(\sigma))$ . Note $\Psi_{\sigma}$ is isomorphic to the contractible prodsimplicial complex $(\Delta_{d})^{m}$ , where $\Delta_{d}$ is the $d$ -dimensional simplex, and the power $m$ refers to the Cartesian Product.

We claim $\Psi_{\sigma}$ is a subcomplex of $\text{Hom}(K_{m},H)$ . Indeed $g_{i}(\sigma)\subset V(H)$ , so $\Psi_{\sigma}$ is the product of simplices in $V(H)$ indexed by the vertices of $K_{m}$ . To prove our claim, we need that whenever $i\sim j$ in $K_{m}$ , i.e. $i\neq j$ , any choice $x\in g_{i}(\sigma)$ and $y\in g_{j}(\sigma)$ produces an edge $x\sim y$ in $H$ . Pick any such $x$ and $y$ , so $x=g_{i}(v)$ and $y=g_{j}(w)$ for some vertices $v,w\in\sigma$ . Put $g=g_{i}g_{j}^{-1}$ , then

\{x,g(y)\}=\{g_{i}(v),g_{i}(w)\}=g_{i}(\{v,w\})

Since $\{v,w\}\subset\sigma$ is an edge in $T$ , so is $g_{i}(\{v,w\})$ , and thus $x\sim y$ in $H$ as needed. Moreover, note that for any $g\in G$ ,

	$\displaystyle g(\Psi_{\sigma})$	$\displaystyle=g(g_{1}(\sigma),g_{2}(\sigma),\dots,g_{m}(\sigma))$
		$\displaystyle=(g_{\pi(1)}(\sigma),g_{\pi(2)}(\sigma),\dots,g_{\pi(m)}(\sigma))$
		$\displaystyle=(g_{1}g(\sigma),g_{2}g(\sigma),\dots,g_{m}g(\sigma))=\Psi_{g(\sigma)}.$

Note also, if $\tau$ is a face of $\sigma$ , $\Psi_{\tau}$ is a subcomplex of $\Psi_{\sigma}$ , since for any $g\in G$ , $g(\tau)\subset g(\sigma)$ .

Recall we say that a topological space $X$ is $n$ -connected if for every $\ell=-1,0,\dots,n$ , each continuous map $f:\mathbb{S}^{\ell}\to X$ can be extended to a continuous map $f:B^{\ell+1}\to X$ . It is well known that any contractible space is $n$ -connected for all $n\geq 0$ . Recall the $d$ -simplex $\Delta_{d}$ is homeomorphic to the closed ball $B^{d+1}$ and its boundary $\partial\Delta_{d}$ is homeomorphic to the $(d-1)$ -sphere $\mathbb{S}^{d-1}$ . Putting these together with the fact $\Psi_{\sigma}$ is contractible, we get the following tool:

If $f:\partial\sigma\to\|\Psi_{\sigma}\|$ is a continuous map, then it can be extended into a map $f:\sigma\to\|\Psi_{\sigma}\|$ .

We now construct $\Phi$ by induction on the $d$ -skeleton of $T$ .

•

Vertices: For each vertex $v\in V(T)$ , define $\Phi(v)=(v,g_{2}(v),\dots,g_{m}(v))=\Psi_{\{v\}}$ . Clearly $\Phi(g(v))=\Psi_{\{g(v)\}}=g(\Psi_{\{v\}})=g(\Phi(v))$ as proved above.
•

Induction Hypothesis: Suppose that we have defined $\Phi:T^{(d)}\xrightarrow{G}\text{Hom}(K_{m},H)$ for the $d$ -skeleton of $T$ , in such a way that $\Phi(\sigma)\subset\|\Psi_{\sigma}\|$ .
•

Inductive Step: Separate the $(d+1)$ -cells of $T$ into $G$ -orbits (this is possible because $G$ acts freely). Let $\mathcal{O}=G\sigma$ be one of such orbits, with $\sigma\in T^{(d+1)}$ a generator. Let $\tau_{0},\tau_{1},\dots,\tau_{d}$ be the $d$ -faces of $\sigma$ . By the induction hypothesis, $\Phi$ is defined such that $\Phi(\tau_{i})\subset\|\Psi_{\tau_{i}}\|\subset\|\Psi_{\sigma}\|$ . Thus $\Phi$ is defined as a map

$\Phi:\partial\sigma=\bigcup_{i=0}^{d}\tau_{i}\to\bigcup_{i=0}^{d}\|\Psi_{\tau_{i}}\|\subset\|\Psi_{\sigma}\|,$

hence we can extend $\Phi$ to $\sigma$ , such that $\Phi(\sigma)\subset\|\Psi_{\sigma}\|$ . For each other $(d+1)$ -cell $\omega\in\mathcal{O}$ , there is a $g\in G$ , such that $\omega=g(\sigma)$ , so define

$\Phi(\omega):=g(\Phi(\sigma))\subset g\left(\|\Psi_{\sigma}\|\right)\subset\|\Psi_{g\sigma}\|=\|\Psi_{\omega}\|.$

Note this agrees on the $d$ -faces of $\omega$ , since we supposed $\Phi$ was a $G$ -map on the $d$ -skeleton of $T$ . Finally, repeating this for all the $G$ -orbits of $(d+1)$ -cells, we get $\Phi:T^{(d+1)}\xrightarrow{G}\text{Hom}(K_{m},H)$ satisfying the induction hypothesis.

This produces the $G$ -map $\Phi:T\xrightarrow{G}\text{Hom}(K_{m},H)$ and finishes the proof. _■

6 Upper Bounds

We now focus on the upper bound in Theorem 3.4. Note that if $K$ is a $G$ -space of $G$ -index $k$ , $K\xrightarrow{G}E_{k}G$ , so by Theorem 4.1, $\text{cov}_{G}\left(K\right)\leq\text{cov}_{G}\left(E_{k}G\right)=\text{cov}_{G}\left(k\right)$ . Hence, we only need to prove an upper bound for finite $G$ classifying spaces. We do this by combining Theorem 6.1, which provides a recursive upper bound, and Theorem 6.2, which bounds $\text{cov}_{G}\left(1\right)$ . We finish this section with Theorem 6.5, which we use to compute upper bounds for $\text{cov}_{\mathbb{Z}_{m}}\left(d\right)$ , for some values of $m$ and $d$ , with the aid of a computer.

Theorem 6.1.

Let $G$ be a finite group and $d\geq 2$ an integer. Then

\text{cov}_{G}\left(d\right)\leq\text{cov}_{G}\left(d-1\right)+|G|-1.

Proof.

Let $K=G*M$ where $M$ is a $(d-1)$ -dimensional classifying space for $G$ , so $K$ is a $d$ -dimensional classifying space for $G$ . The elements of $K$ can be described as linear combinations $tg\oplus(1-t)\mu$ where $g\in G,\mu\in M$ and $0\leq t\leq 1$ , and thus $h\in G$ acts by

h(tg\oplus(1-t)\mu)=hg\oplus(1-t)h(\mu).

Let $k=\text{cov}_{G}\left(d-1\right)$ , so there is a closed $G$ -cover $M=F_{1},\dots,F_{k}$ . For each $i=1,\dots,k$ , and each $g\in G,g\neq\mathbbm{1}$ , define the closed sets

	$\displaystyle F_{i,g}$	$\displaystyle=\left\{tg\oplus(1-t)\mu\in K:\mu\in F_{i},0\leq t\leq 1/2\right\}\text{ and }$
	$\displaystyle\overline{F}_{i,g}$	$\displaystyle=\left\{tg\oplus(1-t)\mu\in K:\mu\in F_{i},1/2\leq t\leq 1\right\}.$

So $F_{i,g}\cup\overline{F}_{i,g}=g*F_{i}$ . Also define the closed sets

\displaystyle F_{i,\mathbbm{1}}

\displaystyle=\left\{t\mathbbm{1}\oplus(1-t)\mu\in K:\mu\in F_{i},0\leq t\leq 1\right\}=\mathbbm{1}*F_{i}.

Finally, let $m=|G|$ and enumerate $G=\{\mathbbm{1},g_{1},g_{2},\dots,g_{m-1}\}$ . Define $E_{1},\dots,E_{k},E_{k+1},\dots,E_{m+k-1}$ as follows

	$\displaystyle E_{i}$	$\displaystyle=\bigcup_{g\in G}F_{i,g}\text{ for }1\leq i\leq k\text{ and}$
	$\displaystyle E_{k+i}$	$\displaystyle=\bigcup_{i=1}^{k}\overline{F}_{j,g_{i}}\text{ for }1\leq i\leq m-1.$

Clearly the $(m+k-1)$ sets $E_{i}$ are closed and cover $K$ . We claim they are a $G$ -cover of $K$ .

Suppose there is some index $1\leq i\leq k$ and some $h\in G,h\neq\mathbbm{1}$ such that $E_{i}\cap hE_{i}\neq\emptyset$ . Then, there must be some $g,g^{\prime}\in G$ such that $x\in F_{i,g}\cap hF_{i,g^{\prime}}\neq\emptyset$ . Thus we can write $x$ as

x=tg\oplus(1-t)\mu=\tau hg^{\prime}\oplus(1-\tau)h\nu,

for some $\mu,\nu\in F_{i}$ , $0\leq t,\tau\leq 1$ . Then, it must be that $(1-t)\mu=(1-\tau)h\nu$ . If $(1-t),(1-\tau)\neq 0$ we must have $\mu=h\nu$ , but since $F_{i}\cap hF_{i}=\emptyset$ , this is impossible. If instead $(1-t)=(1-\tau)=0$ , then it has to be that $g=g^{\prime}=\mathbbm{1}$ and then $x=\mathbbm{1}=h\mathbbm{1}=h$ , but $h\neq\mathbbm{1}$ so this is impossible as well.

Suppose there is some index $1\leq i\leq m-1$ , and some $h\in G,h\neq\mathbbm{1}$ such that $E_{k+i}\cap hE_{k+i}\neq\emptyset$ . Then, there must be some $1\leq j,\alpha\leq k$ such that $x\in\overline{F}_{j,g_{i}}\cap h\overline{F}_{\alpha,g_{i}}\neq\emptyset$ . Thus we can write $x$ as

x=tg_{i}\oplus(1-t)\mu=\tau hg_{i}\oplus(1-\tau)h\nu,

for some $\mu\in F_{j}$ , $\nu\in F_{\alpha}$ , $1/2\leq t,\tau\leq 1$ . Then, it must be that $tg_{i}=\tau hg_{i}$ , and since $t,\tau\neq 0$ , we must have $g_{i}=hg_{i}$ , but since $h\neq\mathbbm{1}$ , this is impossible.

Therefore $E_{r}\cap hE_{r}=\emptyset$ for all $1\leq r\leq k+m-1$ and all $h\in G,h\neq\mathbbm{1}$ as desired. ∎

Now we state the upper bound for the 1-dimensional case.

Theorem 6.2.

Let $G$ a finite group. Then

\text{cov}_{G}\left(1\right)\leq|G|+1.

Combining this Theorem with the lower bound in Theorem 5.1, gives $\text{cov}_{G}\left(1\right)=|G|+1$ . To prove it, we need to first establish some lemmas. Let us start proving the case when $G$ is a cyclic group acting on the 1-dimensional classifying space $\mathbb{S}^{1}$ .

Lemma 6.3.

Consider $\mathbb{S}^{1}$ as a $\mathbb{Z}_{m}$ space, then

\text{cov}_{\mathbb{Z}_{m}}\left(\mathbb{S}^{1}\right)\leq m+1.

Proof.

Note $\mathbb{Z}_{m}$ acts on $\mathbb{S}^{1}$ via rotations of $2\pi/m$ . Enumerate $\mathbb{Z}_{m}=\{\mathbbm{1},\nu,\dots,\nu^{m-1}\}$ . Note that for any $x\in\mathbb{S}^{1}$ and any $1\leq k\leq m-1$ we have

\mathbbm{d}_{\mathbb{S}^{1}}\left(x,\nu^{k}(x)\right)\geq\mathbbm{d}_{\mathbb{S}^{1}}\left(x,\nu(x)\right)=\frac{2\pi}{m}.

For each $i=0,\dots,m$ , let $F_{i}$ be the closed circular arc $[\frac{2i\pi}{m+1},\frac{2(i+1)\pi}{m+1}]$ . Clearly $\text{diam}\left(F_{i}\right)=\frac{2\pi}{m+1}<\frac{2\pi}{m}$ , so it is impossible to have $x$ and $\nu^{k}(x)$ on the same $F_{i}$ , that is $F_{i}\cap\nu^{k}F_{i}=\emptyset$ for all $i=0,\dots,m$ and all $k=1,\dots,m-1$ . Therefore, the $F_{i}$ ’s are a $\mathbb{Z}_{m}$ -cover of $\mathbb{S}^{1}$ using $(m+1)$ closed sets, and the result follows. ∎

Lemma 6.4.

Let $K=\mathbb{Z}_{m}*\mathbb{Z}_{m}$ , so $K$ is trivially a $\mathbb{Z}_{m}$ -space. As a simplicial complex, the vertices of $K$ are two disjoint copies of $\mathbb{Z}_{m}$ . Denote these vertices by $1,\dots,m$ if they come from the first copy, and $\overline{1},\dots,\overline{m}$ , from the second. Then, there exists a closed $\mathbb{Z}_{m}$ -cover $K=A_{0}\cup\dots\cup A_{m}$ , with $(m+1)$ closed sets, such that $i,\overline{i}\in A_{i}$ for each $i\in\mathbb{Z}_{m}=\{1,\dots,m\}$ .

Proof.

Let $\Phi:K\to\mathbb{S}^{1}$ be defined as follows. For the vertices of $K$ , let $\Phi(i)=\Phi(\overline{i})=(2\pi i)/m\in\mathbb{S}^{1}$ . For the edges $\{i,\overline{j}\}\in K$ , $\Phi(\{i,\overline{j}\})=[\frac{2\pi i}{m},\frac{2\pi j}{k}]$ . This defines $\Phi$ on the simplicial complex $K$ , and is straightforward to check it is both continuous and a $\mathbb{Z}_{m}$ -map.

Lemma 6.3 ensures there is a $\mathbb{Z}_{m}$ -cover $F_{0},\dots,F_{m}$ of $\mathbb{S}^{1}$ . Clearly the points $\frac{2\pi i}{m}$ must be in different sets $F_{i}$ for it to be a $\mathbb{Z}_{m}$ -cover, so we may assume $\frac{2\pi i}{m}\in F_{i}$ for $i=1,\dots,m$ . Finally, the pullback cover $A_{i}=\Phi^{-1}(F_{i})$ for $i=0,\dots,m$ produces the desired $\mathbb{Z}_{m}$ -cover. ∎

Regarding the closed sets of a $\mathbb{Z}_{m}$ -cover as colors, we can give an intuitive interpretation of Lemma 6.4. If the vertices of $K$ already have colors assigned, such that $c(i)=c(\overline{i})$ for all $i$ , and $c(i)\neq c(j)$ whenever $i\neq j$ , then we can extend such coloring to $K$ , adding just one more color in order to get a $\mathbb{Z}_{m}$ -cover. This interpretation is the key to prove Theorem 6.2, where finding a $G$ -cover for $G*G$ can be broken into finding $G$ -covers for disjoint cyclic orbits of edges, using only the colors already assigned to the vertices and at most one more color.

Proof of Theorem 6.2.

Let $m=|G|$ and enumerate $G=\{g_{1}=\mathbbm{1},g_{2},\dots,g_{m}\}$ . Let $K=G*G$ , and denote its vertices by $g_{1},\dots,g_{m}$ and $\overline{g_{1}},\dots,\overline{g_{m}}$ , as in Lemma 6.4. All points $x\in\|K\|$ can be written as $tg_{i}\oplus(1-t)\overline{g_{j}}$ , for some $g_{i},g_{j}\in G$ and some $0\leq t\leq 1$ . The edges of $K$ are all edges of the form $\{g_{i},\overline{g_{j}}\}$ , for $1\leq i,j\leq m$ . To ease our notation, we will denote an edge $\{g_{i},\overline{g_{j}}\}$ simply as $g_{i}\sim g_{j}$ , where it is understood that the element on the left denotes that vertex and the element on the right denotes the overlined version of the vertex. In particular, $g\sim g$ is valid, and denotes the edge $\{g,\overline{g}\}\in K$ for any $g\in G$ .

We will construct a closed $G$ -cover of $K$ by gradually adding closed subsets of $K$ to the initial color classes $C_{0},\dots C_{m}$ , initialized as $C_{0}=\emptyset$ and $C_{i}=\{g_{i}\}\cup\{\overline{g_{i}}\}$ for $1\leq i\leq m$ . Note they are indeed closed, since they are either empty or exactly two points.

For an easier exposition, we will say that a closed subset $F\subset\|K\|$ is colored with color $g_{i}$ , to mean that we add the set $F$ to $C_{i}$ , defining $C_{i}^{\prime}=C_{i}\cup F_{i}$ . This is a slight abuse of notation, since it is possible for some points to be part of many sets $C_{i}$ . Note that by doing this finitely many times, the color classes will remain closed.

We want that $C_{i}\cap gC_{i}=\emptyset$ for all $g\in G,g\neq\mathbbm{1}$ , $0\leq i\leq m$ . This failing is equivalent to the existence of a point $x\in\|K\|$ , an index $0\leq i\leq m$ and an element $g\in G$ , $g\neq\mathbbm{1}$ such that $x$ and $gx$ both have color $g_{i}$ . Since in our initial coloring the vertices of $K$ have different colors, $x$ must be in the interior of some edge $a\sim b$ , and thus $gx$ is in the edge $ga\sim gb$ . Thus, to prevent the existence of such $x$ , we just need to focus on properly extending the color classes $C_{0},\dots,C_{m}$ , on the $G$ -orbit $\mathcal{O}(a\sim b):=\{ga\sim gb:g\in G\}$ , for each edge $a\sim b\in K$ separately. When we say properly extending, we mean that $C_{0}\cap\mathcal{O}(a\sim b),\dots,C_{m}\cap\mathcal{O}(a\sim b)$ is a closed $G$ -cover of $\mathcal{O}(a\sim b)$ . We will now focus on doing this on one such orbit.

Let $a\sim b$ be an edge of $K$ , and $\mathcal{O}=\{ga\sim gb:g\in G\}$ be its $G$ -orbit. By interpreting each edge as an assignment $\sigma(ga)=gb$ , we can see $\sigma$ as a permutation of the elements of $G$ . Recall that all finite permutations can be regarded as a disjoint union of cycles (see e.g. [Lan02, p. 30]), so $\sigma$ partitions $G$ into $r$ cycles of the form

	$\displaystyle a_{1}^{(1)}\mapsto\sigma(a_{1}^{(1)})=a_{2}^{(1)}\mapsto\sigma(a_{2}^{(1)})$	$\displaystyle=a_{3}^{(1)}\mapsto\cdots\mapsto\sigma(a_{k_{1}}^{(1)})=a_{1}^{(1)}$
	$\displaystyle a_{1}^{(2)}\mapsto\sigma(a_{1}^{(2)})=a_{2}^{(2)}\mapsto\sigma(a_{2}^{(2)})$	$\displaystyle=a_{3}^{(2)}\mapsto\cdots\mapsto\sigma(a_{k_{2}}^{(2)})=a_{1}^{(2)}$
		$\displaystyle\vdots$
	$\displaystyle a_{1}^{(r)}\mapsto\sigma(a_{1}^{(r)})=a_{2}^{(r)}\mapsto\sigma(a_{2}^{(r)})$	$\displaystyle=a_{3}^{(r)}\mapsto\cdots\mapsto\sigma(a_{k_{r}}^{(r)})=a_{1}^{(r)}$

where $k_{j}$ is the length of the $j$ -th cycle.

And at the same time, this partitions $\mathcal{O}$ into $r$ disjoint subsets of the form

\mathcal{O}_{j}=\left\{a_{1}^{(j)}\sim a_{2}^{(j)},a_{2}^{(j)}\sim a_{3}^{(j)},\dots,a_{k_{j}}^{(j)}\sim a_{1}^{(j)}\right\}.

Each $\mathcal{O}_{j}$ can be seen itself as a 1-dimensional simplicial complex, and moreover it is naturally a $\mathbb{Z}_{k_{j}}$ -space, where $\mathbb{Z}_{k_{j}}$ acts by cyclically permuting the edges. Thus, we can regard $\mathcal{O}_{j}\subset\mathbb{Z}_{k_{j}}*\mathbb{Z}_{k_{j}}$ . Lemma 6.4 gives a coloring for the whole space $\mathbb{Z}_{k_{j}}*\mathbb{Z}_{k_{j}}$ just using the colors already assigned to the vertices $a_{i}^{(j)}$ and at most one more color (which we will assign to the color class $C_{0}$ ), so we may restrict this coloring to $\mathcal{O}_{j}$ . In the especial case when $\sigma$ is already a cycle, this finishes the proof. For the general case when $r\geq 2$ , still Lemma 6.4 will be our building block, but we need to be careful so that the different cycles don’t produce points $x$ and $gx$ with the same color.

Take each edge $a_{i}^{(j)}\sim a_{i+1}^{(j)}$ (the addition $i+1$ must be understood modulo $k_{j}$ ) and divide it into $r$ closed intervals $P_{i,1}^{(j)},P_{i,2}^{(j)},\dots,P_{i,r}^{(j)}$ intersecting only at their endpoints. More formally, we identify $a_{i}^{(j)}\sim a_{i+1}^{(j)}$ isometrically with the real segment $[0,1]$ by sending $a_{i}^{(j)}$ to 0 and $a_{i+1}^{(j)}$ to 1. Then $P_{k,i}^{(j)}$ is the preimage of the subinterval $\left[(k-1)/n,k/n\right]$ . Notice then that for any $g\in G$ , and any $1\leq k\leq r$ the set $gP_{i,k}^{(j)}$ is always another interval $P_{i^{\prime},k}^{(j^{\prime})}$ , i.e. it is part of a different edge that may be part of a different orbit $\mathcal{O}_{j^{\prime}}$ , but will always be on the same relative position over the edge.

We finally produce the coloring for $\mathcal{O}=\{a_{i}^{(j)}\sim a_{i+1}^{(j)}:1\leq i\leq k_{j},1\leq j\leq r\}$ by coloring each subinterval $P_{i,k}^{(j)}$ , as follows.

1.

Color each subinterval $P_{i,k}^{(j)}$ where $k<j$ with the color $a_{i}^{(j)}$ . I.e. color the first $(j-1)$ subintervals of each edge, with the color of the left vertex.
2.

Color each subinterval $P_{i,k}^{(j)}$ where $k>j$ with the color $a_{i+1}^{(j)}$ . I.e. color the last $(r-j)$ subintervals of each edge, with the color of the right vertex.
3.

Fix each $1\leq j\leq r$ . Notice that the endpoints of the subintervals $P_{i,j}^{(j)}$ , were already assigned colors $a_{i}^{(j)}$ and $a_{i+1}^{(j)}$ respectively. By cycling on the edges $a_{i}^{(j)}\sim a_{i+1}^{(j)}$ , we also cycle on the subintervals $P_{i,j}^{(j)}$ , so themselves can be seen as a subset of the $\mathbb{Z}_{k_{j}}$ -complex $\mathbb{Z}_{k_{j}}*\mathbb{Z}_{k_{j}}$ . Thus lemma 6.4 gives a closed coloring for $P_{1,j}^{(j)},\dots,P_{k_{j},j}^{(j)}$ using only the colors already assigned to the $a_{i}^{(j)}$ ’s and color 0 (color class $C_{0}$ ).

Checking that this coloring produces a closed $G$ -cover of $\mathcal{O}$ , is straightforward. By repeating this process for all the $G$ -orbits of edges in $K$ , we get the desired $G$ -cover with $m+1$ closed sets. ∎

A possible proof of Conjecture 3.5, would be to adapt the technique of the proof of Theorem 6.2 to higher dimensions. Doing this, would require to first prove Conjecture 3.6 item 1, regarding $\mathbb{Z}_{m}$ spaces. While we haven’t been able to do this generally, even for dimension 2, we have been able to explicitly find some $\mathbb{Z}_{m}$ -covers for small values of $m$ aided by a computer. The following Theorem allows us to find $G$ -covers computing the chromatic number of relatively small graphs. More details on the specific graphs and techniques used to produce the examples of Figure 1(d) are included in the Appendix.

Theorem 6.5.

Let $K$ be a compact geometric $G$ -simplicial complex. Let $T$ be a triangulation of $K$ , such that it is still a $G$ -simplicial complex. Define the graph $H$ to be the graph with vertices $V(T)$ and with edges $v\sim w$ whenever there exists a $g\in G,g\neq\mathbbm{1}$ such that $\{v,gw\}\in T$ . Then

\text{cov}_{G}\left(K\right)\leq\chi(H).

Proof.

If $H$ has loops, its chromatic number is infinite and the result is trivial; so suppose $H$ has no loops. Let $c$ be a coloring of $H$ using $\chi(H)$ colors, so $c:V(T)\to\{1,\dots,\chi(H)\}$ .

Let $B=\text{Bar}(T)$ be the Barycentric subdivision of $T$ . Recall $\|B\|=\|T\|=\|K\|$ and that the simplices of $B$ can be identified with chains of simplices of $T$ . Since $T$ is a $G$ -simplicial complex, applying $g$ to a chain $\sigma_{1}\prec\sigma_{2}\prec\dots\sigma_{r}$ of simplices of $T$ , produces $g\sigma_{1}\prec g\sigma_{2}\prec\dots\prec g\sigma_{r}$ , another chain of simplices of $T$ . So $B$ is a $G$ -simplicial complex as well. Recall that the facets of $B$ correspond to maximal chains of simplices of $T$ , so for each facet $\tau\in B$ there is a unique vertex $v\in V(T)$ such that $v\in\tau$ .

For each vertex $v\in V(T)$ , we define $F(v)$ as follows

F(v)=\bigcup\{\|\tau\|:\tau\in\text{Facets}(B)\text{ and }v\in\tau\}

Note that the geometric representations of the facets of $B$ give a closed cover of $\|K\|$ , and so the sets $F(v)$ are also a closed cover. Also note that $gF(v)=F(gv)$ for all $g\in G,v\in V(T)$ .

Define the closed sets $C_{1},\dots,C_{\chi(H)}$ as

C_{i}=\bigcup_{\begin{subarray}{c}v\in V(T)\\ c(v)=i\end{subarray}}F(v).

Then the sets $C_{i}$ are a closed cover for $\|K\|$ , and we claim they are a $G$ -cover. To see this, suppose by way of contradiction that there is a point $x$ in $\|K\|$ , an index $i$ , and an element $g\in G$ , $g\neq\mathbbm{1}$ such that $x,gx\in C_{i}$ . This means there are vertices $u,v\in V(T)$ with $c(u)=c(v)=i$ , such that $x\in F(u)$ and $gx\in F(v)$ . Thus $gx\in gF(u)=F(gu)$ and $gx\in F(v)$ .

Then, there are simplices $\tau_{1},\tau_{2}\in\text{Facets}(B)$ , such that $gu\in\tau_{1},v\in\tau_{2}$ and $gx\in\|\tau_{1}\|\cap\|\tau_{2}\|$ . Thus, there is a nontrivial face $\tau=\tau_{1}\cap\tau_{2}$ in $B$ . We claim this means $\{v,gu\}\in T$ , and so $v\sim u$ in $H$ , but they both had the same color $i$ , giving the desired contradiction.

To finish the proof we establish now our last claim. Since $gu\in\tau_{1}$ , $v\in\tau_{2}$ , and $\tau=\tau_{1}\cap\tau_{2}\neq\emptyset$ , we can describe them as chains of simplices in $T$ :

	$\displaystyle\tau_{1}$	$\displaystyle=\{gu\prec a_{2}\prec\dots\prec a_{r}\}$
	$\displaystyle\tau_{2}$	$\displaystyle=\{v\prec b_{2}\prec\dots\prec b_{s}\}\text{ and}$
	$\displaystyle\tau$	$\displaystyle=\{c_{1}\prec\dots\prec c_{t}\}$

Where each $c_{i}=a_{i_{j}}=b_{i_{k}}$ for some indices. Thus $c_{1}=a_{j}=b_{k}$ for some indices, so $gu\prec c_{1}$ and $v\prec c_{1}$ , so $\{gu,v\}\subset c_{1}$ . But $c_{1}$ is a simplex of $T$ , so $\{gu,v\}\in T$ , as we claimed. ∎

7 Random $\bm{G}$ -Borsuk Graphs

In this section, we focus on the chromatic number of random $G$ -Borsuk graphs, and find thresholds for $\varepsilon$ depending on $n$ , the number of vertices, such that asymptotically almost surely we can more precisely bound its chromatic number.

Definition 7.1 (Random $G$ -Borsuk graphs).

Let $G$ be a finite group, and $K$ a compact $G$ -space. We define the random $G$ -Graph on $K$ , denoted by $\mathcal{G}_{G}\left(n,\varepsilon\right)$ , as the $G$ -Borsuk graph $\mathcal{G}_{G}\left(X(n),\varepsilon\right)$ , where $X(n)=\{x_{1},\dots,x_{n}\}$ is a set of $n$ i.i.d. uniform random points on $K$ .

Note that the definition of a random $G$ -Borsuk graph also depends on the specific underlying $G$ -space, however for simplicity we don’t include $K$ in the notation and instead make it clear from the context.

Since a random $G$ -Borsuk graph is an induced subgraph of a $G$ -Borsuk graph, Theorem 4.1 states its chromatic number must be at most $\text{cov}_{G}\left(K\right)\leq\text{cov}_{G}\left(k\right)$ (here $k=\text{ind}_{G}\left(K\right)$ ), with equality if the random sampling is dense enough. In this section we will prove Theorem 7.2, which establishes, up to a constant, what $\varepsilon(n)$ provides a dense enough sample. On the other hand, when $\varepsilon(n)$ is small enough to provide a sufficiently sparse sample, then the chromatic number is a.a.s. bounded above by $\text{cov}_{G}\left(k-1\right)$ , which if Conjecture 3.5 is true must be strictly less than $\text{cov}_{G}\left(K\right)$ .

Theorem 7.2.

Consider a finite group $G$ and a finite geometric $G$ -simplicial complex $K$ of dimension $d$ . Suppose $K$ is pure $d$ -dimensional, i.e. all of its maximal faces have dimension $d$ . And let $k=\text{ind}_{G}\left(K\right)$ . Then, there exist constants $C_{1}$ and $C_{2}$ (independent from $n$ ), such that:

1.

If $\varepsilon\geq C_{1}\left(\frac{\log n}{n}\right)^{1/d}$ , then a.a.s. $\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))=\text{cov}_{G}\left(K\right).$
2.

If $\varepsilon\leq C_{2}\left(\frac{\log n}{n}\right)^{1/k}$ , then a.a.s. $\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))\leq\text{cov}_{G}\left(k-1\right).$

Theorem 3.9 follows by taking $K$ a $E_{d}G$ space, since then $k=\text{ind}_{G}\left(K\right)=\dim(K)=d$ .

The case $G=\mathbb{Z}_{2}$ corresponds to Random Borsuk Graphs, which was already established in Theorems 1.1 and 1.2 of [KMF20]. The main ideas behind the proofs of this generalization remain the same. We first establish some intermediate results before jumping into the proof.

7.1 Some Geometric Lemmas

For the “sparse case”, our approach relies on being able to project the vertices of the $G$ -Borsuk graph onto the $(d-1)$ -skeleton of the classifying space via a $G$ -map. This will be possible as long as vertices that where close to each other remain close after the projection. This will follow from the following lemmas studying such projections on planes and $d$ -simplices.

Lemma 7.3.

Let $O$ be a point on the plane and let $\ell$ be a line such that the distance from $O$ to $\ell$ is at least $d_{1}>0$ . Let $A$ and $B$ be two points such that the following hold

•

$A,B$ and $O$ lie all on the same semi-plane with respect to $\ell$ ;
•

the rays $\vec{OA}$ and $\vec{OB}$ intersect $\ell$ ;
•

$\mathbbm{d}\left(O,A^{\prime}\right),\mathbbm{d}\left(O,B^{\prime}\right)\leq d_{2}$ , where $A^{\prime}=OA\cap\ell$ and $B^{\prime}=OB\cap\ell$ ;
•

$\mathbbm{d}\left(O,A\right),\mathbbm{d}\left(O,B\right)\geq\kappa\varepsilon$ ; and
•

$\mathbbm{d}\left(A,B\right)\leq\varepsilon$ .

Then

\mathbbm{d}\left(A^{\prime},B^{\prime}\right)\leq\frac{d_{2}^{2}}{\kappa d_{1}}.

Proof.

Note

\sin(\measuredangle OA^{\prime}B^{\prime})=\frac{\mathbbm{d}\left(O,\ell\right)}{\mathbbm{d}\left(O,A^{\prime}\right)}\geq\frac{d_{1}}{d_{2}}.

By Law of Sines on the triangle $\Delta AOB$ ,

\sin(\measuredangle AOB)=\frac{\mathbbm{d}\left(A,B\right)\sin(\measuredangle OBA)}{\mathbbm{d}\left(O,A\right)}\leq\frac{\mathbbm{d}\left(A,B\right)}{\mathbbm{d}\left(O,A\right)}\leq\frac{\varepsilon}{\kappa\varepsilon}=\frac{1}{\kappa}.

Note $\measuredangle A^{\prime}OB^{\prime}=\measuredangle AOB$ , so by Law of Sines on the triangle $\Delta A^{\prime}OB^{\prime}$ we get

\mathbbm{d}\left(A^{\prime},B^{\prime}\right)=\frac{\mathbbm{d}\left(O,B^{\prime}\right)\sin(\measuredangle A^{\prime}OB^{\prime})}{\sin(\measuredangle OA^{\prime}B^{\prime})}\leq\frac{d_{2}\frac{1}{\kappa}}{\frac{d_{1}}{d_{2}}}=\frac{d_{2}^{2}}{\kappa d_{1}}

∎

Lemma 7.4.

Let $\Delta$ be a geometric $d$ -simplex of diameter at most $d_{2}$ . Let $O$ be an interior point such that $\mathbbm{d}\left(\partial\Delta,O\right)\geq d_{1}$ . Take any two points $A,B\in\Delta$ with $\mathbbm{d}\left(A,B\right)\leq\varepsilon$ and $\mathbbm{d}\left(O,A\right),\mathbbm{d}\left(O,B\right)\geq\kappa\varepsilon$ . Let $A^{\prime}$ and $B^{\prime}$ be the intersection of the rays $OA$ and $OB$ with the boundary of $\Delta$ respectively. Then $\mathbbm{d}_{\partial\Delta}\left(A^{\prime},B^{\prime}\right)\leq 2(d+1)d_{2}^{2}/(\kappa d_{1})$ .

Proof.

The case $d=1$ is trivial, so we suppose $d\geq 2$ . Let $\tau_{1}$ and $\tau_{2}$ be the $(d-1)$ -faces of $\Delta$ that intersect the rays $\vec{OA}$ and $\vec{OB}$ , respectively. So $A^{\prime}\in\tau_{1}$ and $B^{\prime}\in\tau_{2}$ . We distinguish two cases:

If $\tau_{1}=\tau_{2}$ . Denote $\tau=\tau_{1}=\tau_{2}$ , so both $A^{\prime}$ and $B^{\prime}$ lie on the same $(d-1)$ -face $\tau$ . In this case, let $\Pi$ be the plane through $O,A$ and $B$ . The intersection $\tau\cap\Pi$ must be a line segment containing $A^{\prime}$ and $B^{\prime}$ . Note that if $\ell$ is the line containing $\tau\cap\Pi$ , then $O,A,B$ and $\ell$ satisfy all the hypothesis of Lemma 7.3, so

\mathbbm{d}_{\partial\Delta}\left(A^{\prime},B^{\prime}\right)\leq\frac{d_{2}^{2}}{\kappa d_{1}}\leq 2(d+1)\frac{d_{2}^{2}}{\kappa d_{1}}.

If $\tau_{1}\neq\tau_{2}$ . Consider the line segment $\overline{AB}$ , which lies in the interior of $\Delta$ , and let $p:\overline{AB}\to\partial\Delta$ be the projection on $\partial\Delta$ from $O$ , i.e. the intersection of rays $\vec{OX}$ for all points $X\in\overline{AB}$ . Note $p(\overline{AB})$ will be a polygonal line from $A^{\prime}\in\tau_{1}$ to $B^{\prime}\in\tau_{2}$ , passing through faces $\tau_{1}=\sigma_{1},\sigma_{2},\dots,\sigma_{r}=\tau_{2}$ of $\partial\Delta$ , where $r\leq(d+1)$ . Let $E^{\prime}_{i}=p(\overline{AB})\cap\sigma_{i}\cap\sigma_{i+1}$ for each $i=1,\dots,r-1$ , and say $E_{0}^{\prime}=A^{\prime}$ and $E_{r}^{\prime}=B^{\prime}$ . Correspondingly, let $E_{i}\in\overline{AB}$ such that $p(E_{i})=E_{i}^{\prime}$ . For each $i=1,\dots,r$ , let $\Pi_{i}$ be the plane through $E_{i-1},E_{i}$ and $O$ . As in the first case, let $\ell_{i}$ be the line containing $\Pi_{i}\cap\sigma_{i}$ . Clearly $\mathbbm{d}\left(E_{i-1},E_{i}\right)\leq\varepsilon$ , and, given $\kappa>1$ , we also know $\mathbbm{d}\left(\overline{AB},O\right)\geq\frac{\kappa\varepsilon}{2}$ , so $\mathbbm{d}\left(E_{i-1},O\right),\mathbbm{d}\left(E_{i},O\right)\geq\kappa\varepsilon/2$ , then these points and $\ell_{i}$ satisfy the hypothesis of Lemma 7.3 with $\kappa/2$ , so $\mathbbm{d}_{\partial\Delta}\left(E_{i-1}^{\prime},E_{i}^{\prime}\right)\leq\frac{2d_{2}^{2}}{\kappa d_{1}}$ . Then

\mathbbm{d}_{\partial\Delta}\left(A^{\prime},B^{\prime}\right)\leq\mathbbm{d}_{\partial\Delta}\left(E_{0}^{\prime},E_{1}^{\prime}\right)+\dots+\mathbbm{d}_{\partial\Delta}\left(E_{r-1}^{\prime},E_{r}^{\prime}\right)\leq r\frac{2d_{2}^{2}}{\kappa d_{1}}\leq 2\frac{(d+1)d_{2}^{2}}{\kappa d_{1}}.

∎

We will use the next lemma to translate the volume of balls on $E_{k}G$ back to $K$ , where the random points are drawn.

Lemma 7.5.

Let $\sigma$ be a geometric $d$ -dimensional simplex, $\tau$ a $k$ -face of $\sigma$ , and $\Psi:\sigma\to\tau$ a simplicial map that leaves $\tau$ invariant. Then there exists a constant $C$ such that for each measurable subset $E\subset\sigma$ , we have

\text{Vol}_{d}\!\left(E\right)\leq C\text{Vol}_{k}\!\left(\Psi(E)\right).

Proof.

Let $e_{1},e_{2},\dots,e_{d}$ be the standard vector basis of $\mathbb{R}^{d}$ , and let $e_{0}=\vec{0}$ be the origin. For each $m\leq d$ , the points $\{e_{0},\dots,e_{m}\}$ are affinely independent, so their convex hull is a geometric $m$ -simplex which we denote $\Delta_{m}$ . For each $r\leq m$ , let $\pi_{r}:\Delta_{m}\to\Delta_{r}$ be the projection map to the first $r$ coordinates. Note $\pi_{r}$ can be seen as the simplicial map given by the vertex mapping

\pi_{r}(e_{i})=\begin{cases}e_{i}&\text{ if }i\leq r\\ e_{0}&\text{ if }i>r\end{cases}.

We start by establishing the result when $k=d-1$ . Enumerate the vertices of $\sigma$ , $V(\sigma)=\{a_{0},\dots,a_{d}\}$ , such that $V(\tau)=\{a_{0},\dots,a_{d-1}\}$ . Since the map $\Psi$ is determined by its mapping of the vertices, $\Psi(a_{i})=a_{i}$ for all $0\leq 1\leq d-1$ and $\Psi(a_{d})$ coincides with one of the other vertices, so shuffling the labels if necessary, $\Psi(a_{d})=a_{0}$ .

Then, there exists a unique affine transformation $\Phi:\sigma\to\Delta_{d}$ such that $\Phi(a_{i})=e_{i}$ for $0\leq i\leq d$ . Let $\varphi=\Phi|_{\tau}$ , note then $\varphi:\tau\to\Delta_{d-1}$ is an affine map. Moreover, both $\Phi$ and $\varphi$ are bijective, so there exist invertible matrices $A,A^{\prime}$ and vectors $b,b^{\prime}$ such that $\Phi(x)=Ax+b$ and $\varphi(x)=A^{\prime}x+b^{\prime}$ . We then get that the following diagram of simplicial maps commutes

where $\pi=\pi_{d-1}$ . In particular, we have $\varphi^{-1}\circ\pi\circ\Phi=\Psi$ . Let us also point out that for any set $F\subset\Delta_{d}$ , we have $F\subset\pi(F)\times[0,1]$ .

Then, the volume of any measurable set $E\in\sigma$ satisfies:

	$\displaystyle\text{Vol}_{d}\!\left(E\right)$	$\displaystyle=\frac{\text{Vol}_{d}\!\left(\Phi E\right)}{\|\det A\|}$
		$\displaystyle\leq\frac{\text{Vol}_{d}\!\left((\pi\Phi E)\times[0,1]\right)}{\|\det A\|}=\frac{\text{Vol}_{d-1}\!\left(\pi\Phi E\right)\cdot 1}{\|\det A\|}$
		$\displaystyle=\frac{\|\det A^{\prime}\|}{\|\det A\|}\text{Vol}_{d-1}\!\left(\varphi^{-1}\pi\Phi E\right)=C\text{Vol}_{d-1}\!\left(\Psi E\right).$

We now extend the result for any $k<d$ . Suppose $V(\sigma)=\{a_{0},\dots,a_{d}\}$ and $V(\tau)=\{a_{0},\dots,a_{k}\}$ . For each $k+1\leq i\leq d$ , define the $i$ -face $\tau_{i}\subset\sigma$ by $\tau_{i}=\{a_{0},\dots,a_{k},a_{k+1},\dots,a_{i}\}$ , so $\tau_{k}=\tau$ and $\tau_{d}=\sigma$ . Also for each $k+1\leq i\leq d$ , define the map $\Psi_{i}:\tau_{i}\to\tau_{i-1}$ as the simplicial map given by

\Psi_{i}(a_{j})=\begin{cases}a_{j},\text{ if }0\leq j\leq i-1\\ \Psi(a_{i}),\text{ if }j=i\end{cases}.

Thus $\Psi$ factors through the faces $\tau_{i}$ as depicted in the following commutative diagram

Finally, each $\Psi_{i}:\tau_{i}\to\tau_{i-1}$ satisfies the hypothesis of the theorem for the special case that we already proved, so for each $E\subset\sigma=\tau_{d}$ measurable set, we get

	$\displaystyle\text{Vol}_{d}\!\left(E\right)$	$\displaystyle\leq C_{d}\text{Vol}_{d-1}\!\left(\Psi_{d}(E)\right)$
		$\displaystyle\leq C_{d}C_{d-1}\text{Vol}_{d-2}\!\left(\Psi_{d-1}\Psi_{d}(E)\right)$
		$\displaystyle\vdots$
		$\displaystyle\leq\left(\prod_{i=k+1}^{d}C_{i}\right)\text{Vol}_{k}\!\left(\Psi_{d}\Psi_{d-1}\dots\Psi_{k+1}(E)\right)=C\text{Vol}_{k}\!\left(\Psi(E)\right)$

∎

7.2 Other Preliminary Results

We state the following Lemma without proof. While the proof should be straightforward, it is quite technical so we omit it. Refer to [BH99] for more on geodesics of geometric simplicial complexes, with the intrinsic metric.

Lemma 7.6.

Let $K$ be a geometric simplicial complex and $\varepsilon_{0}$ small. Then, there exists a constant $N$ , depending only on $K$ , such that for any $x,y\in K$ with $\mathbbm{d}\left(x,y\right)\leq\varepsilon_{0}$ , there is a polygonal path from $x$ to $y$ of length $\mathbbm{d}\left(x,y\right)$ , made up of at most $N$ line segments, each of which is contained in a face of $K$ .

Theorem 7.7.

Let $G$ be a finite group, and $K$ a finite geometric $G$ -simplicial complex of dimension $d$ , such that $G$ acts on $K$ via isometries. Moreover, suppose $K$ is pure $d$ -dimensional, and let $L=K^{(d-1)}$ its $(d-1)$ -skeleton. Fix a constant $d_{1}>0$ , and let $X_{0}\subset K$ be a collection of one point in the interior of each $d$ -face of $K$ , such that $gX_{0}=X_{0}$ for all $g\in G$ , and $\mathbbm{d}\left(X_{0},L\right)\geq d_{1}$ . Given $\varepsilon_{0}>0$ , there exists a constant $\kappa$ depending only on $K$ , $\varepsilon_{0}$ and $d_{1}$ , such that for any $\varepsilon$ small enough, there is a graph homomorphism

\Phi:\mathcal{G}_{G}\left(K\setminus B(X_{0},\kappa\varepsilon),\varepsilon\right)\to\mathcal{G}_{G}\left(L,\varepsilon_{0}\right).

Here $B(X_{0},\kappa\varepsilon):=\bigcup_{x\in X_{0}}B(x,\kappa\varepsilon)$ .

Proof.

For each $d$ -face $\sigma_{i}\in K$ , let $x_{i}\in X_{0}$ be the point in $\sigma_{i}$ . For $x\in\sigma_{i}\setminus\{x_{i}\}$ , define $\varphi_{i}(x)$ to be the unique point of intersection of the ray $\vec{x_{i}x}$ with the boundary $\partial\sigma_{i}$ . Note this map $\varphi_{i}:\sigma_{i}\setminus\{x_{i}\}\to\partial\sigma_{i}$ is continuous and it restricts to the identity on $\partial\sigma_{i}$ . Moreover, for any $g\in G$ , since $g$ acts as a linear map, the ray $\vec{x_{i}x}$ is mapped to the ray $\vec{g(x_{i})g(x)}$ , so if $g(x_{i})=x_{j}\in X_{0}$ , we get

g\left(\varphi_{i}(x)\right)=\varphi_{j}\left(g(x)\right).

Let $K_{d}$ be the collection of $d$ -faces of $K$ , and let $d_{2}=\max_{\sigma\in K_{d}}\text{diam}\left(\sigma\right)$ . Let $N$ be the constant from Lemma 7.6 corresponding to $\varepsilon_{0}$ . Define $\kappa=2\frac{N(d+1)d_{2}^{2}}{d_{1}\varepsilon_{0}}$ . Let $\varepsilon<\varepsilon_{0}$ be small enough so that $B(x_{i},\kappa\varepsilon)\subset\text{interior}(\sigma_{i})$ for all $i$ . Then, by Lemma 7.4, for each $i$ and $x,y\in\sigma_{i}\setminus B(x_{i},\kappa\varepsilon)$ such that $\mathbbm{d}_{K}\left(x,y\right)\leq\varepsilon$ we get $\mathbbm{d}_{L}\left(\varphi_{i}(x),\varphi_{i}(y)\right)\leq\varepsilon_{0}/N$ .

Define $\Phi:K\setminus B(X_{0},\kappa\varepsilon)\to L$ by pasting all the maps $\varphi_{i}$ . That is, if $x\in\text{int}\left(\sigma_{i}\right)$ for some $i$ , let $\Phi(x)=\varphi_{i}(x)$ , and if $x\in L$ , let $\Phi(x)=x$ . Since all the maps $\varphi_{i}$ are continuous and they all restrict to the identity on $L$ , pasting them produces a continuous map. Moreover, $\Phi$ is a $G$ -map:

\Phi(g(x))=\varphi_{i}(g(x))=g(\varphi_{j}(x))=g\Phi(x),

where $i$ and $j$ are the indices such that $g(x)\in\sigma_{i}$ and $x\in\sigma_{j}$ ; and $\Phi(g(x))$ is defined since $x\in\sigma_{i}\setminus B(x_{i},\kappa\varepsilon)$ and $g$ is an isometry, so $g(x)\in\sigma_{j}\setminus B(x_{j},\kappa\varepsilon)$ .

We now consider the induced map

\Phi:V(\mathcal{G}_{G}\left(K\setminus B(X_{0},\kappa\varepsilon),\varepsilon\right))\to V(\mathcal{G}_{G}\left(L,\varepsilon_{0}\right)),

by checking that it respects the adjacency of vertices, we will have a graph homomorphism as desired. Note that to do this is enough to prove that $\mathbbm{d}_{L}\left(\Phi(x),\Phi(y)\right)\leq\varepsilon_{0}$ whenever $\mathbbm{d}_{K}\left(x,y\right)\leq\varepsilon$ , and $x,y\in K\setminus B(X_{0},\kappa\varepsilon)$ . Indeed, if $x\sim y$ in $\mathcal{G}_{G}\left(K\setminus B(x_{0},\kappa\varepsilon),\varepsilon\right)$ then there is a $g\in G$ , $g\neq\mathbbm{1}$ , such that $\mathbbm{d}_{K}\left(x,gy\right),x\in K\setminus B(X_{0},\kappa\varepsilon)$ and since $g$ is an isometry, $gy\in K\setminus B(X_{0},\kappa\varepsilon)$ . Thus if our claim holds, $\mathbbm{d}_{L}\left(\Phi(x),g\Phi(y)\right)=\mathbbm{d}_{L}\left(\Phi(x),\Phi(gy)\right)\leq\varepsilon_{0}$ and $\Phi(x)\sim\Phi(y)$ in $\mathcal{G}_{G}\left(L,\varepsilon_{0}\right)$ as desired.

We now prove the claim. Let $x,y\in K\setminus B(X_{0},\kappa\varepsilon)$ , such that $\mathbbm{d}_{K}\left(x,y\right)\leq\varepsilon<\varepsilon_{0}$ . Then, there is a shortest polygonal path in $K$ between $x$ and $y$ of length less than $\varepsilon$ . This path passes through the $d$ -faces $\tau_{1},\tau_{2},\dots,\tau_{r}$ , where $x\in\text{interior}(\tau_{1})$ , $y\in\text{interior}(\tau_{r})$ and $r\leq N$ by Lemma 7.6. For each $i=1,\dots,r-1$ , let $z_{i}$ be the intersection of this shortest path with $\tau_{i}\cap\tau_{i+1}$ , let $z_{0}=x$ and $z_{r}=y$ . Note $\mathbbm{d}_{K}\left(z_{i},z_{i+1}\right)\leq\varepsilon$ for all $i=0,\dots r-1$ , and $x_{i}\in L$ for $i\neq 0,r+1$ , so $\mathbbm{d}_{K}\left(X_{0},z_{i}\right)>\kappa\varepsilon$ .

Take $i\in\{1,\dots,r\}$ . If $\tau_{i}=\sigma_{j}$ is a $d$ -face of $K$ , as we noted before $z_{i-1},z_{i}\in\sigma_{j}\setminus B(x_{j},\kappa\varepsilon)$ and $\mathbbm{d}_{K}\left(z_{i-1},z_{i}\right)\leq\varepsilon$ , so $\mathbbm{d}_{L}\left(\Phi(z_{i-1}),\Phi(z_{i})\right)=\mathbbm{d}_{L}\left(\varphi(z_{i-1}),\varphi(z_{i})\right)\leq\frac{2(d+1)d_{2}^{2}}{\kappa d_{1}}\leq\frac{\varepsilon_{0}}{N}$ . If instead $\tau_{i}\in L$ , there is some $d$ -face $\sigma_{j}$ such that $\tau_{i}\leq\sigma_{j}$ , and again $z_{i-1},z_{i}\in\sigma_{j}\setminus B(x_{j},\kappa\varepsilon)$ and $\mathbbm{d}_{K}\left(z_{i-1},z_{i}\right)=\varepsilon$ , so $\mathbbm{d}_{L}\left(\Phi(z_{i-1}),\Phi(z_{i})\right)\leq\frac{\varepsilon_{0}}{N}$ . Therefore,

\mathbbm{d}_{L}\left(\Phi(x),\Phi(y)\right)\leq\sum_{i=1}^{r}\mathbbm{d}_{L}\left(\Phi(z_{i-1}),\Phi(z_{i})\right)\leq\varepsilon_{0},

which finishes the proof. ∎

Recall that a $\bm{\delta}$ -net $\mathcal{B}$ of a compact metric space $K$ , is a finite subset such that for each $x\in K$ , there is a $y\in\mathcal{B}$ such that $\mathbbm{d}_{K}\left(x,y\right)<\delta$ . Similarly, a $\bm{\delta}$ -apart set $\mathcal{B}$ of $K$ , is a finite subset such that for any $x,y\in\mathcal{B}$ with $x\neq y$ , $\mathbbm{d}_{K}\left(x,y\right)>\delta$ . The next lemma bounds the cardinality of $\delta$ -nets and $\delta$ -apart sets for geometric simplices, the technique mimics what we did for $d$ -Spheres on [KMF20].

Lemma 7.8.

Let $\Delta$ be a geometric $d$ -simplex. Then there exist constants $C_{1}(\Delta)$ and $C_{2}(\Delta)$ such that for every $\delta>0$ small enough, there is a $\delta$ -net $\mathcal{B}$ that is also a $\delta$ -apart set, such that

\frac{C_{1}(\Delta)}{\delta^{d}}\leq|\mathcal{B}|\leq\frac{C_{2}(\Delta)}{\delta^{d}}

Proof.

Regard $\Delta$ as embedded in $\mathbb{R}^{d}$ , with its incenter at the origin. Let $\delta>0$ small. Since $\Delta$ is compact, we can construct $\mathcal{B}$ inductively. Indeed, choose any point $y_{1}\in\Delta$ . Then, for each $n\geq 2$ , if $B_{n}=\cup_{i=1}^{n}B(y_{i},\delta)\subsetneq\Delta$ , choose any $y_{n+1}\in\Delta B_{m}$ . Otherwise, stop and let $\mathcal{B}=\{y_{1},y_{2},\dots,y_{n}\}$ . The process stops by compactness. Clearly $\mathcal{B}$ is a $\delta$ -net and a $\delta$ -apart set. Note $\Delta\subset\bigcup B(y_{i},\delta)$ , thus

	$\displaystyle\text{Vol}\!\left(\Delta\right)\leq\text{Vol}\!\left(\bigcup B(y_{i},\delta)\right)$	$\displaystyle\leq\|\mathcal{B}\|\text{Vol}\!\left(B(y_{i},\delta)\right)=\|\mathcal{B}\|\omega_{d}\delta^{d}\text{, so}$
	$\displaystyle\frac{\text{Vol}\!\left(\Delta\right)}{\omega_{d}\delta^{d}}$	$\displaystyle\leq\|\mathcal{B}\|.$

Here $\omega_{d}$ is the volume of the unit $d$ -ball. If $\delta$ is smaller than the inradius of $\Delta$ , we always have $B(x,\delta/2)\subset 2\Delta$ , for all $x\in\Delta$ . Since the $y_{i}^{\prime}s$ are a $\delta$ -apart set, clearly $B(y_{i},\delta/2)\cap B(y_{j},\delta/2)=\emptyset$ whenever $i\neq j$ , and so we have

	$\displaystyle 2^{d}\text{Vol}\!\left(\Delta\right)=\text{Vol}\!\left(2\Delta\right)\geq\text{Vol}\!\left(\biguplus B(y_{i},\delta/2)\right)$	$\displaystyle=\|\mathcal{B}\|\text{Vol}\!\left(B(y_{i},\delta/2)\right)=\|\mathcal{B}\|\frac{\omega_{d}\delta^{d}}{2^{d}}\text{, so}$
	$\displaystyle\frac{4^{d}\text{Vol}\!\left(\Delta\right)}{\omega_{d}\delta^{d}}$	$\displaystyle\geq\|\mathcal{B}\|.$

Thus setting $C_{1}(\Delta)=\frac{\text{Vol}\!\left(\Delta\right)}{\omega_{d}}$ and $C_{2}(\Delta)=\frac{4^{d}\text{Vol}\!\left(\Delta\right)}{\omega_{d}}$ , we get the result. ∎

Lemma 7.9.

Let $G$ be a finite group and $K$ a finite geometric $G$ -simplicial complex. Denote $k=\text{ind}_{G}\left(K\right)\leq\text{dim}(K)=d$ . Then, there exists a Lipschitz $G$ -simplicial map $\Phi:K\xrightarrow{G}E_{k}G$ and a constant $\overline{C}$ such that

\text{Vol}_{d}\!\left(\Phi^{-1}\left(B(x,\delta)\right)\right)\leq\overline{C}\text{Vol}_{k}\!\left(B(x,\delta)\right)

for all $x$ and $\delta$ such that $B(x,\delta)$ is contained in the interior of a $k$ -face of $E_{k}G$ .

Proof.

Since $k=\text{ind}_{G}\left(K\right)$ , by definition there is some $G$ -map $\Phi:K\xrightarrow{G}\ E_{k}G$ . Moreover, by the simplicial approximation theorem, we may assume that $\Phi$ is a simplicial map, substituting $K$ and $E_{k}G$ by some finer subdivisions if necessary. While the more general simplicial approximation theorem doesn’t guarantee that we still get a $G$ -map, this can be achieved by the standard procedure of defining it on a representative of each $G$ -orbit and then extending it appropriately (see e.g. [Mat08, Koz08]). Since a simplicial map induces a map between the geometric complexes via linear extensions, $\Phi:K\xrightarrow{G}E_{k}G$ is just a piece-wise linear map, determined by the images of the vertices of $K$ . As such, and since linear maps are continuous iff they are bounded, $\Phi$ must be a Lipschitz map.

Suppose now that $B(x,\delta)$ is contained in the interior of $k$ -face $\tau$ of $E_{k}G$ . Since $\Phi$ is a simplicial map, $\Phi^{-1}(\tau)$ is a sub-simplicial complex of $K$ . Clearly the $d$ -volume of $\Phi^{-1}(B(x,\delta))\cap\sigma$ is zero whenever $\dim(\sigma)<d$ . At the same time, if $\sigma$ is a face of $\Phi^{-1}(\tau)$ such that $\dim(\Phi(\sigma))<k$ , then $B(x,\delta)\cap\Phi(\sigma)=\emptyset$ so $\Phi^{-1}(B(x,\delta))\cap\sigma=\emptyset$ . Hence, the $d$ -volume of $\Phi^{-1}(B(x,\delta))$ only depends on it intersection with the $d$ -faces of $\Phi^{-1}(\tau)$ that are mapped onto $\tau$ surjectively.

Denote $K_{d}(\tau)=\left\{\sigma\in K:\dim(\sigma)=d\text{ and }\Phi(\sigma)=\tau\right\}$ and let $\sigma\in K_{d}(\tau)$ . Enumerate $\sigma=\{a_{0},a_{1},\dots,a_{d}\}$ such that if $\omega=\{a_{0},\dots,a_{k}\}$ , then $\Phi(\omega)=\tau$ . Thus, for each $a_{i}$ with $i>k$ , $\Phi(a_{i})=\Phi(a_{j})$ for exactly one index $0\leq j\leq k$ . Let $\Psi:\sigma\to\omega$ be the simplicial map given by the assignment of vertices

\Psi(a_{i})=\begin{cases}a_{i},\text{ if }0\leq i\leq k\\ a_{j},\text{ s.t. }\Phi(a_{i})=\Phi(a_{j}),\text{ if }k+1\leq i\leq d\end{cases},

and let $\varphi=\Phi|_{\omega}$ the restriction of $\Phi$ to $\omega$ . Note that these two maps give the factorization $\Phi=\Psi\circ\varphi$ . Note also that $\varphi$ is a bijective affine transformation, so there exists an invertible matrix $A$ and a vector $b$ such that $\varphi(x)=Ax+b$ . Let $E(\sigma)=\Phi^{-1}(B(x,\delta))\cap\sigma$ , clearly $E(\sigma)$ is a measurable subset, and applying Lemma 7.5 to $\sigma$ , $\omega$ and the map $\Psi$ , there exists a constant $C(\sigma)$ such that

	$\displaystyle\text{Vol}_{d}\!\left(E\right)$	$\displaystyle\leq C(\sigma)\text{Vol}_{k}\!\left(\Psi(E)\right)=\frac{C(\sigma)}{\|\det A\|}\text{Vol}_{k}\!\left(\varphi\Psi(E)\right)$
		$\displaystyle=\frac{C(\sigma)}{\|\det A\|}\text{Vol}_{k}\!\left(\Phi(E)\right)\leq\frac{C(\sigma)}{\|\det A\|}\text{Vol}_{k}\!\left(B(x,\delta)\right)$
		$\displaystyle=\overline{C}(\sigma)\text{Vol}_{k}\!\left(B(x,\delta)\right).$

Thus, letting

\hat{C}(\tau)=\sum_{\sigma\in K_{d}(\tau)}\overline{C}(\sigma),\phantom{xx}\text{and}\phantom{xx}\overline{C}=\max_{\begin{subarray}{c}\tau\in E_{k}G\\ \dim(\tau)=k\end{subarray}}\hat{C}(\tau),

we get the desired inequality. ∎

7.3 Proof of Theorem 7.2

7.3.1 Dense Case

If $\varepsilon\to 0$ slowly enough, with high probability the random vertices will form a small net, and so Theorem 4.2 will guarantee that the chromatic number is the same as $\text{cov}_{G}\left(K\right)$ . The argument behind is a union bound, and the independence of the random vertices.

Proof of dense case.

Note that as soon as $\varepsilon(n)$ is small enough, Theorem 4.2 item 2 gives the upper bound

\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))\leq\text{cov}_{G}\left(K\right).

Let $K_{d}=\{\sigma\in K|\dim(\sigma)=d\}$ be the set of $d$ -faces of $K$ . Thus, since $K$ is pure $d$ -dimensional, we have $\lVert K\rVert=\left\lVert\bigcup_{\sigma\in K_{d}}\sigma\right\rVert$ . By Lemma 7.8, for each $d$ -face $\sigma\in K_{d}$ , there exist constants $\overline{C}(\sigma)$ such that for any given $\delta>0$ small, we can find a $\delta$ -net $\mathcal{B}(\sigma)$ of $\sigma$ such that $|\mathcal{B}(\sigma)|\leq\overline{C}(\sigma)\delta^{-d}$ . Define a global $\overline{C}:=\sum_{\sigma\in K_{d}}\overline{C}(\sigma)$ . Hence, by defining $\mathcal{B}=\bigcup_{\sigma\in K_{d}}\mathcal{B}(\sigma)$ we can always find a $\delta$ -net of $K$ such that $|\mathcal{B}|\leq\overline{C}\delta^{-d}$ .

Similarly, the volume of a $d$ -ball of radius $\delta$ is proportional to $\delta^{d}$ . And it is known that for a $d$ -face $\sigma$ , if $\delta$ is small enough and $x\in\sigma$ then

V(B(x,\delta)\cap\sigma)\geq c(\sigma)\delta^{d},

for a constant $c(\sigma)>0$ that depends on the hyper-angle of the sharpest corner of $\sigma$ . Define $c:=\frac{\min_{\sigma\in K_{d}}c(\sigma)}{V(K)}$ , thus for any point $x\in K$ and $\delta>0$ small, we have

\frac{V(B(x,\delta)\cap K)}{V(K)}\geq\frac{V(B(x,\delta)\cap\sigma)}{V(K)}\geq\frac{c(\sigma)}{V(K)}\delta^{d}\geq c\delta^{d}.

Let $D$ be as in Theorem 4.2 item 1. Then, we claim that $C_{1}=\frac{2D}{\sqrt[d]{c}}$ is as stated in the theorem. That is, if $\varepsilon\geq C_{1}(\log n/n)^{1/d}$ , then we will show that a.a.s. $\text{cov}_{G}\left(K\right)\leq\chi\left(\mathcal{G}_{G}\left(n,\varepsilon\right)\right)$ .

For each $n$ , let $\delta=\varepsilon(n)/(2D)$ , and consider the corresponding $\delta$ -net of $K$ , $\mathcal{B}=\{y_{1},\dots,y_{N}\}$ . For each $i=1,\dots,N$ define the closed set $F_{i}=B(y_{i},\delta)\cap K$ . Then $K=\cup_{i=1}^{N}F_{i}$ , $\frac{V(F_{i})}{V(K)}\geq c\delta^{d}$ , and $N\leq\overline{C}\delta^{-d}\leq\overline{C}c(n/\log n)$ as discussed above.

Let $X=\{x_{1},\cdots,x_{n}\}$ be the vertices of the random $G$ -Borsuk graph, i.e. they are i.i.d. uniform random points on $K$ . The computations below will establish that a.a.s. $X$ is a $(\varepsilon/D)-net$ of $K$ , and thus Theorem 4.2 item 1 gives the desired lower bound for the chromatic number.

For any $i=1,\dots,N$ and $j=1,\dots,n$ we have

\displaystyle\mathbb{P}\left[x_{j}\in F_{i}\right]

\displaystyle=\frac{V(F_{i})}{V(K)}\geq c\delta^{d}=c\frac{\varepsilon^{d}}{(2D)^{d}}\geq\frac{\log n}{n}.

Then, the probability that some of the sets $F_{i}$ doesn’t contain any vertex of $X$ is

	$\displaystyle\mathbb{P}\left[\bigvee_{i=1}^{N}(X\cap F_{i}=\emptyset)\right]$	$\displaystyle\leq\sum_{i=1}^{N}\mathbb{P}\left[X\cap F_{i}=\emptyset\right]=\sum_{i=1}^{N}\mathbb{P}\left[x_{j}\not\in F_{i}\right]^{n}$
		$\displaystyle\leq\sum_{i=1}^{N}(1-\log n/n)^{n}\leq N(1-\log n/n)^{n}$
		$\displaystyle\leq\overline{C}c\frac{n}{\log n}e^{-\log n}=\frac{\overline{C}c}{\log n}\to 0\text{ as }n\to\infty.$

Thus, a.a.s. every set $F_{i}$ will contain some vertex of $X$ , and hence the set $X$ is a $2\delta=(\varepsilon/D)$ -net of $K$ as desired. ∎

7.3.2 Sparse Case

When $\varepsilon\to 0$ fast, and if $K=E_{k}G$ , a.a.s. there will be a point $x_{0}\in K$ , not too close to $K^{(k-1)}$ , such that its orbit under $G$ is always at a distance at least $\kappa\varepsilon$ of all the random vertices of $\mathcal{G}_{G}\left(n,\varepsilon\right)$ . In this case, Theorem 7.7 provides a graph homomorphism from the random $G$ -Borsuk graph on $K$ to a $G$ -Borsuk graph on $K^{(k-1)}$ , and so Theorem 4.2 gives the desired upper bound. When $K$ is not a finite classifying space, the same will still be true by looking at the pre-images of the $G$ -map $\Phi:K\to E_{k}G$ .

The idea behind the proof is to consider the pre-images of open balls around many orbits $Gx_{0}$ in $E_{k}G$ , and prove that a.a.s. there will be at least one of them that doesn’t contain any vertex of $\mathcal{G}_{G}\left(n,\varepsilon\right)$ . To get spacial independence of random events, we consider a Poissonization of the random vertices, i.e. we draw them via a Poisson Point Process instead. We include a couple of results about Poisson Point Processes and the Poisson distribution without proof, for their proofs and a complete discussion refer to [Pen03] or [Kin93].

Theorem 7.10 (Poissonization).

Let $x_{1},x_{2},\dots$ , be uniform random variables on a compact metric space $K$ . Let $m\sim\text{Pois}(\lambda)$ and let $\eta$ be the random counting measure associated to the point process $P_{\lambda}$ = $\{x_{1},x_{2},\dots,x_{m}\}$ . Then $P_{\lambda}$ is a Poisson Point Process and for a Borel $A\subset K$ , $\eta(A)\sim\text{Pois}\left(\lambda\frac{V(A)}{V(K)}\right)$ .

Lemma 7.11.

For $n\geq 0$ , $\mathbb{P}\left[\text{Pois}\left(2n\right)<n\right]\leq e^{-0.306n}.$

To make our proofs cleaner, we address the probabilistic part in the following lemma.

Lemma 7.12.

Let $K$ be a compact metric space pure $d$ -dimensional. Let $D$ be a constant such that for each $n$ , there are $N=N(n)$ disjoint closed sets $F_{1},\dots,F_{N}\subset K$ such that

1.

$\frac{\text{Vol}\!\left(F_{r}\right)}{\text{Vol}\!\left(K\right)}\leq\frac{\log n}{3n}$ for all $r=1,\dots,N$ ; and
2.

$N\geq\frac{Dn}{\log n}$ .

Let $X_{n}=\{x_{1},\dots,x_{n}\}$ be a collection of $n$ i.i.d. uniform random points on $K$ with corresponding counting measure $\eta_{1}^{n}$ . Then

\mathbb{P}\left[\bigvee_{r=1}^{N}\eta_{1}^{n}(F_{i})=0\right]\to 1\text{ as }n\to\infty.

Proof.

We use the fact that the $F_{r}$ ’s are disjoint, by considering instead the Poissonization of the random points, so that we get spatial independence. Hence let $x_{1},x_{2},\dots$ be uniform random variables on $K$ , let $M\sim\text{Pois}\left(2n\right)$ , and consider the Poisson Point Process $\{x_{1},\dots,x_{M}\}$ , as described in Theorem 7.10. Letting $\eta$ be the corresponding counting measure, we get

	$\displaystyle\mathbb{P}\left[\bigwedge_{r=1}^{N}\eta(F_{r})>0\right]$	$\displaystyle=\prod_{r=1}^{N}\mathbb{P}\left[\eta(F_{r})>0\right]$
		$\displaystyle=\prod_{r=1}^{N}\left(1-\mathbb{P}\left[\text{Pois}\left(\frac{2n\text{Vol}\!\left(F_{r}\right)}{\text{Vol}\!\left(K\right)}\right)=0\right]\right)$
		$\displaystyle=\prod_{r=1}^{N}\left(1-e^{-\frac{2n\text{Vol}\!\left(F_{r}\right)}{\text{Vol}\!\left(K\right)}}\right)\leq\left(1-e^{-(2/3)\log n}\right)^{N}$
		$\displaystyle\leq\exp\left(-Nn^{-2/3}\right)\leq\exp\left(-\frac{Dn^{1/3}}{\log n}\right)\to 0\text{ as }n\to\infty.$

Thus $\mathbb{P}\left[\bigvee_{r=1}^{N}\eta(F_{r})=0\right]\to 1$ as $n\to\infty$ . Clearly when $M\geq n$ , $\eta(F_{r})=0$ implies $\eta_{1}^{n}(F_{r})=0$ as well. Thus, applying Lemma 7.11, we get

	$\displaystyle\mathbb{P}\left[\bigvee_{r=1}^{N}\eta(F_{r})=0\right]$	$\displaystyle\leq\mathbb{P}\left[\bigvee_{r=1}^{N}\eta_{1}^{n}(F_{r})=0\right]+\mathbb{P}\left[M<n\right]$
		$\displaystyle\leq\mathbb{P}\left[\bigvee_{r=1}^{N}\eta_{1}^{n}(F_{r})=0\right]+o(1).$

From where the desired result follows. ∎

Proof of Sparse Case.

Let $M$ be a geometric realization of $E_{k}G$ such that $G$ acts on $M$ via isometries. Then, let $\Phi:K\xrightarrow{G}M$ be the simplicial $G$ -map and $C$ the corresponding constant given by Lemma 7.9. Let $\lambda$ be the Lipschitz constant of $\Phi$ .

Let $L=M^{(k-1)}$ be the $(k-1)$ -skeleton of $M$ . Restricting the action of $G$ to $L$ we also get a geometric $G$ -simplicial complex. Moreover, $\dim(L)=k-1$ and, since $M$ is $k$ -connected, $L$ must be $(k-1)$ -connected, thus $L$ is a $(k-1)$ -classifying space of $G$ , and $\text{cov}_{G}\left(L\right)=\text{cov}_{G}\left(k-1\right)$ . Let $\varepsilon_{0}>0$ be as in Theorem 4.2, that is, for any $X\subset L$ and any $0<\varepsilon\leq\varepsilon_{0}$ ,

\chi\left(\mathcal{G}_{G}\left(X,\varepsilon\right)\right)\leq\text{cov}_{G}\left(L\right)=\text{cov}_{G}\left(k-1\right).

Let $M_{d}$ be the set of $d$ -faces of $M$ . Let $d_{1}=(1-\rho)\min_{\sigma\in M_{d}}{\text{inradius}(\sigma)}$ , for $\rho<1$ any fixed constant close to 1. And let $\kappa$ be the constant given by Theorem 7.7, corresponding to $\varepsilon_{0}$ and $d_{1}$ . Partition the $d$ -faces of $M$ into $G$ -orbits, and let $\mathcal{C}=\{\sigma_{1},\dots\sigma_{m}\}$ be a collection of one representative per orbit, where $m=|\mathcal{C}|$ .

We will prove that the constant

C_{2}=\frac{1}{\kappa\lambda}\left(\frac{\text{Vol}_{d}\!\left(K\right)}{3m|G|C\omega_{k}}\right)^{1/k},

where $\omega_{k}$ is the volume of the unit $k$ -ball, is as stated in the theorem. That is, if $\varepsilon(n)\leq C_{2}(\log n/n)^{1/k}$ , then a.a.s. $\chi(\mathcal{G}_{G}\left(n,\varepsilon\right))\leq\text{cov}_{G}\left(L\right)$ .

For a $d$ -face $\sigma$ , denote by $\rho\sigma$ the homothetic copy of $\sigma$ obtained by scaling it by a factor of $\rho$ with respect to its incenter. Note that

\mathbbm{d}\left(\rho\sigma,\partial\sigma\right)=(1-\rho)\text{inradius}(\sigma)\geq d_{1}.

Fix $n$ large enough so that $\varepsilon$ satisfies $\kappa\lambda\varepsilon\ll d_{1}$ , and let $\delta=2\kappa\lambda\varepsilon$ . For each $1\leq i\leq m$ , Lemma 7.8 guarantees there is a constant $\overline{C}(\rho\sigma_{i})$ and a $\delta$ -apart set $\mathcal{B}_{i}=\{y_{1}^{i},\dots,y_{|\mathcal{B}_{i}|}^{i}\}\subset\rho\sigma_{i}$ such that,

\frac{\overline{C}(\rho\sigma_{i})}{\delta^{k}}\leq|\mathcal{B}_{i}|.

Let $\overline{C}=\min_{i}{\overline{C}(\rho\sigma_{i})}$ and $N=\min_{i}|\mathcal{B}_{i}|$ , then $\overline{C}/\delta^{k}\leq N$ .

For each $r=1,\dots,N$ construct the set $Y_{r}$ , as

Y_{r}:=\{gy_{r}^{i}:g\in G,1\leq i\leq m\}.

Note this construction guarantees $Y_{r}=gY_{r}$ for all $g\in G$ , it has one point in the interior of each $d$ -face of $M$ , and $\mathbbm{d}\left(Y_{r},L\right)\geq d_{1}$ . Thus, for each $1\leq r\leq N$ , Theorem 7.7 guarantees that there is a graph homomorphism

\mathcal{G}_{G}\left(M\setminus B(Y_{r},\kappa\lambda\varepsilon),\lambda\varepsilon\right)\to\mathcal{G}_{G}\left(L,\varepsilon_{0}\right).

Note that because the points in $Y_{r}$ come from $\delta$ -apart sets and $\kappa\lambda\varepsilon<d_{1}$ , then $B(Y_{r},\kappa\lambda\varepsilon)\cap B(Y_{r^{\prime}},\kappa\lambda\varepsilon)=\emptyset$ whenever $r\neq r^{\prime}$ , and $B(Y_{r},\kappa\lambda\varepsilon)$ is a disjoint union of $k$ -balls.

For each $r=1,\dots N$ , let $F_{r}=\Phi^{-1}\left(B(Y_{r},\kappa\lambda\varepsilon)\right)$ , thus by Lemma 7.9, we get

	$\displaystyle\text{Vol}_{d}\!\left(F_{r}\right)$	$\displaystyle=\sum_{y\in Y_{r}}\text{Vol}_{d}\!\left(\Phi^{-1}\left(B(y,\kappa\lambda\varepsilon)\right)\right)\leq\sum_{y\in Y_{r}}C\text{Vol}_{k}\!\left(B(y,\kappa\lambda\varepsilon)\right)$
		$\displaystyle=\|Y_{r}\|C\omega_{k}(\kappa\lambda\varepsilon)^{k}\leq m\|G\|C\omega_{k}(\kappa\lambda C_{2})^{k}\left(\frac{\log n}{n}\right)$
		$\displaystyle\leq\frac{\text{Vol}_{d}\!\left(K\right)\log n}{3n}.$

So $\frac{\text{Vol}_{d}\!\left(F_{r}\right)}{\text{Vol}_{d}\!\left(K\right)}\leq\frac{\log n}{3n}$ for all $r=1,\dots N$ , and we also have

N\geq\frac{\overline{C}}{(2\kappa\lambda\varepsilon)^{k}}\geq\frac{\overline{C}}{(2\kappa\lambda C_{2})^{k}}\cdot\frac{n}{\log n}=C^{\prime}\frac{n}{\log n}.

Thus we can apply Lemma 7.12 to $X_{n}\subset K$ , $n$ i.i.d. uniform random points on $K$ , so a.a.s. there exists some index $r$ such that $X_{n}\cap F_{r}=\emptyset$ . Finally, since $\Phi$ is a Lipschitz $G$ -map, by Theorem 4.1 item 2, it induces a graph homomorphism, and so we have the following composition of graph homomorphisms

\displaystyle\mathcal{G}_{G}\left(X_{n},\varepsilon\right)\hookrightarrow\mathcal{G}_{G}\left(K\setminus F_{r},\varepsilon\right)\xrightarrow{\Phi}\mathcal{G}_{G}\left(M\setminus B(Y_{r},\kappa\lambda\varepsilon),\lambda\varepsilon\right)\to\mathcal{G}_{G}\left(L,\varepsilon_{0}\right)

So we get the desired result

\chi\left(\mathcal{G}_{G}\left(n,\varepsilon\right)\right)\leq\chi\left(\mathcal{G}_{G}\left(L,\varepsilon_{0}\right)\right)\leq\text{cov}_{G}\left(L\right)=\text{cov}_{G}\left(k-1\right).

∎

8 Further Questions

•

While we have some computer-aided examples suggesting that Conjecture 3.5 might be true, it is still open. Thus, natural follow up questions would be to prove or disprove Conjectures 3.6 and 3.5. Towards this end, it would be interesting to produce $G$ -covers for more small groups in dimensions 2 and 3. In particular, it would be useful to be able to compute $\text{cov}_{\mathbb{Z}_{m}}\left(2\right)$ and $\text{cov}_{\mathbb{Z}_{m}}\left(3\right)$ with more efficient algorithms, rather than solving an integer programming problem.
•

For the random $G$ -Borsuk graphs, we wonder whether there exist similar thresholds to that in Theorem 3.9 for each possible chromatic number. We state this question as a conjecture.

Conjecture 8.1.

Let $G$ be a finite group, and $K$ a geometric $E_{d}G$ space. Then, for each $1\leq k\leq d+1$ , there exist constants $C_{k},\overline{C}_{k}$ and functions $f_{k}:\mathbb{N}\to\mathbb{R}^{+}$ , such that:

If $C_{k}f_{k}(n)\leq\varepsilon(n)\leq\overline{C}_{k}f_{k+1}(n)$ , then a.a.s. $\chi\left(\mathcal{G}_{G}\left(n,\varepsilon\right)\right)=\text{cov}_{G}\left(k\right)$ .

In particular, Theorem 3.9 shows the conjecture is true for $k=d$ , taking $f_{d}(n)=\left(\log n/n\right)^{1/d}$ and $f_{d+1}(n)=\varepsilon_{0}$ from Theorem 4.2.

9 Acknowledgments

The author wants to thank his advisor Matthew Kahle, for fruitful conversations, frequent words of encouragement, and for kindly proof-reading and suggesting improvements to parts of this paper.

Appendix A Computer-aided Examples

In this appendix we describe the approach taken to compute the values of Table 1 and the graphs on Figure 1(d). Let us start by describing a general method for any finite group $G$ , and then we will discuss our specific approach in dimensions 2 and 3 for cyclic groups.

General approach

1.

Suppose $L$ is a $E_{d}G$ classifying space where $G$ acts via isometries. Moreover, suppose we know $\text{cov}_{G}\left(d\right)=|G|+d$ and we have a corresponding closed $G$ -cover of $L$ .
2.

Take $K=G*L$ , so $K$ is a $E_{d+1}G$ classifying space, and $G$ acts on $K$ via isometries.
3.

Let $\Delta$ be a subdivision operation that respects the $G$ -action, that is, an algorithm that takes $K$ and produces a $G$ -simplicial complex $\Delta K$ with the same geometric realization $\|\Delta K\|=\|K\|$ , with $V(K)\subset V(\Delta K)$ , and such that the action of $G$ restricted to $\Delta K$ is again a $G$ -action via simplicial maps. Denote by $\Delta_{k}K$ the repeated application of $\Delta$ . Note that we can realize $L\hookrightarrow K$ , so $\Delta$ restricted to $L$ also produces a subdivision of $L$
4.

For $T=\Delta_{k}K$ , let $H(T)$ be the graph with vertices $V(T)$ and edges $u\sim v$ whenever there is a $g\in G$ , $g\neq\mathbbm{1}$ s.t. $\{u,gv\}\in T$ . Similarly, we define $H(T_{0})$ for $T_{0}=\Delta_{k}L$ .
5.

Let $k$ be the minimum integer such that the known $G$ -cover for $L$ produces a proper graph coloring for $H(T_{0})$ , where $T_{0}=\Delta_{k}L$ . Thus $\chi(H(T_{0}))=\text{cov}_{G}\left(d\right)=|G|+d$ .
6.

Let $c_{0}:V(T_{0})\to\{1,\dots,|G|+d\}$ be this coloring.

Let $T=\Delta_{k}K$ , and $H=H(T)$ . We define a partial coloring $c:V(T)\to\{1,\dots|G|+d,|G|+d+1\}$ , as follows

c(v)=\begin{cases}c_{0}(v_{0})&\text{ if }v_{0}\in T\cap L\\ |G|+d+1&\text{ if }v=t\mathbbm{1}\oplus(1-t)v_{0}\text{ for some }t>0,v_{0}\in V(T_{0})\end{cases}

8.

We then attempt to extend this partial coloring to the remaining vertices of $H$ : $\{tg\oplus(1-t)v_{0}:g\in G,g\neq\mathbbm{1},v_{0}\in V(T_{0}),0<t\leq 1\}$ . We do this by solving the corresponding integer programming problem. If this is possible, we continue with the next step. Otherwise, we increase $k$ by one and repeat steps 6-7.
9.

If the partial coloring can be extended to a proper coloring for $H$ , Theorem 6.5 guarantees $\text{cov}_{G}\left(d+1\right)\leq\chi(H)=|G|+d+1$ , and as in its proof, coloring the Barycentric Subdivision with the corresponding colors of the vertices of $T$ , provides a $G$ -cover for $K$ .
10.

This whole process may be repeated for dimension $d+2$ , using the $G$ -cover of $K$ found as the starting point.

For Cyclic Groups

2D Case

Let $\mathbb{Z}_{m}=\{\mathbbm{1},\nu,\nu^{2},\dots,\nu^{m-1}\}$ be a cyclic group of order $m$ . Let $C_{m}$ be the cycle of length $m$ , with its vertices labeled by the elements of $\mathbb{Z}_{m}$ . It is convenient to think of the rational points of $C_{m}$ as labeled by elements in the module $\mathbb{Q}[\mathbb{Z}_{m}]$ . That is, the rational points in the segment $[\nu^{i},\nu^{i+1}]$ can be described as $\alpha\nu^{i}+(1-\alpha)\nu^{i+1}$ , for $0\leq\alpha\leq 1$ , $\alpha\in\mathbb{Q}$ . Thus, taking left multiplication in the module $\mathbb{Q}[\mathbb{Z}_{m}]$ corresponds to the $\mathbb{Z}_{m}$ -action on $\|C_{m}\|$ .

1.

We take $E_{1}\mathbb{Z}_{m}=\mathbb{S}^{1}=C_{m}$ , so $\text{cov}_{\mathbb{Z}_{m}}\left(1\right)=m+1$ and can be realized by dividing $\mathbb{S}^{1}$ into $(m+1)$ -arcs of the same size.
2.

Consider $E_{2}=\mathbb{Z}_{m}*C_{m}$ . Its vertices are of the form $\alpha g\oplus(1-\alpha)g$ for $g\in G$ and $\alpha\in\{0,1\}$ . Similarly, we can label all rational points in $\|\mathbb{Z}_{m}*C_{m}\|$ by elements of the module $\mathbb{Q}[\mathbb{Z}_{m}]^{2}$ . That is, $x=\alpha g\oplus(1-\alpha)b$ for $0\leq\alpha\leq 1$ , $\alpha\in\mathbb{Q}$ , $g\in\mathbb{Z}_{m}$ and $b$ a rational point in $\|C_{m}\|$ .
3.
For the subdivision operation, we take $\Delta$ to be the medial triangle subdivision. This process subdivides each triangle as follows:
1. (a)
  
  Take a triangle $\{v_{1},v_{2},v_{3}\}$ , with labels $v_{i}=a_{i}\oplus b_{i}$ for $a_{i},b_{i}\in\mathbb{Q}[\mathbb{Z}_{m}]$ .
2. (b)
  
  Let $v_{ij}=\frac{v_{i}+v_{j}}{2}=\frac{a_{i}+a_{j}}{2}\oplus\frac{b_{i}+b_{j}}{2}$ .
3. (c)
  
  Then, return the 4 triangles $\{v_{1},v_{12},v_{13}\}$ , $\{v_{2},v_{12},v_{23}\}$ , $\{v_{3},v_{13},v_{23}\}$ and $\{v_{12},v_{23},v_{13}\}$ .
Notice that this process still produces a triangulation where all the vertices are rational points of $\|\mathbb{Z}_{m}*C_{2}\|$ . Moreover, it clearly respects the $\mathbb{Z}_{m}$ -action and when restricted to $\|C_{m}\|$ , it simply halves each segment.
4.

We then follow steps 4-9 of the general approach. In our examples for $m=2,\dots,6$ , we took values of $k=3$ or $4$ .

Since $\|Z_{m}*C_{m}\|$ can be seen as $m$ independent disks identified by their boundaries, we can plot the vertices of $T$ into $m$ unit disks with centers at the points $(R\cos(2\pi k/m),R\sin(2\pi k/m))$ for some large radius $R$ . Then, we color a fine mesh of points in the disks with the color of their closest vertex to produce Figure 1(d).

3D Case for $\bm{\mathbb{Z}_{3}}$

So far, for the 3-dimensional case we have only been able to compute $\text{cov}_{\mathbb{Z}_{3}}\left(3\right)$ . For this we use the $E_{2}\mathbb{Z}_{3}$ space and the $\mathbb{Z}_{2}$ -cover described before. Just as before, we can think of labeling all its rational points by elements of the module $\mathbb{Q}[\mathbb{Z}_{m}]$ . We then apply the general approach to find a $\mathbb{Z}_{3}$ -cover of $E_{3}\mathbb{Z}_{3}=\mathbb{Z}_{3}*E_{2}\mathbb{Z}_{3}=(\mathbb{Z}_{3}^{*2})*C_{3}$ , by choosing an appropriate subdivision procedure. For this, we subdivide each tetrahedron into 4 medial tetrahedra and one central octahedron, that we further subdivide into 8 tetrahedra. That is, we proceed as follows:

1.

Take a tetrahedron $\{v_{1},v_{2},v_{3},v_{4}\}$ .
2.

For each pair of indices $1\leq i<j\leq 4$ , define the point $v_{ij}=\frac{v_{i}+v_{j}}{2}$ .

Define the point $w=\frac{v_{1}+v_{2}+v_{3}+v_{4}}{4}$ .

Then, return the 12 tetrahedra:

	$\displaystyle\{v_{1},v_{12},v_{13},v_{14}\},$	$\displaystyle\{v_{2},v_{12},v_{23},v_{24}\},\{v_{3},v_{13},v_{23},v_{34}\},\{v_{4},v_{14},v_{24},v_{34}\}$
	$\displaystyle\{v_{12},v_{13},v_{14},w\},$	$\displaystyle\{v_{12},v_{23},v_{24},w\},\{v_{13},v_{23},v_{34},w\},\{v_{14},v_{24},v_{34},w\},$
	$\displaystyle\{v_{12},v_{14},v_{24},w\},$	$\displaystyle\{v_{12},v_{13},v_{23},w\},\{v_{13},v_{14},v_{34},w\},\{v_{23},v_{24},v_{34},w\}$

Notice that this procedure restricted to $E_{2}\mathbb{Z}_{3}$ is just the medial triangle subdivision used in the 2-dimensional case. Moreover, $\Delta K$ is still a $\mathbb{Z}_{3}$ -simplicial complex. Thus we can finish this case by following steps 4-9 of the general approach. In our computations, we use $k=3$ , which produces a graph with 9,129 vertices, however, solving the related integer programming problem in [Gurobi] is almost immediate.

References

[BH99] M. R. Bridson and A. Haefliger. M $\kappa$ -polyhedral complexes. In Metric Spaces of Non-Positive Curvature, pages 97–130. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999. doi:10.1007/978-3-662-12494-9.
[BK03] E. Babson and D. N. Kozlov. Topological obstructions to graph colorings. Electron. Res. Announc. Amer. Math. Soc., 9:61–68, 2003.
[BK06] E. Babson and D. N. Kozlov. Complexes of graph homomorphisms. Israel J. Math., 152:285–312, 2006.
[BM14] A. Barg and O. Musin, editors. Discrete Geometry and Algebraic Combinatorics, volume 625 of Contemporary Mathematics. American Mathematical Society, 2014.
[Dan18] H. R. Daneshpajouh. New construction of graphs with high chromatic number and small clique number. Discrete Comput. Geom., 59(1):238–245, 2018. doi:10.1007/s00454-017-9934-3.
[HN04] P. Hell and J. Nešetřil. Graphs and homomorphisms, volume 28 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2004.
[Kah07] M. Kahle. The neighborhood complex of a random graph. J. Combin. Theory Ser. A, 114(2):380–387, 2007. doi:10.1016/j.jcta.2006.05.004.
[Kin93] J. F. C. Kingman. Poisson Processes (Oxford Studies in Probability). Clarendon Press, jan 1993. URL https://www.xarg.org/ref/a/0198536933/.
[KMF20] M. Kahle and F. Martinez-Figueroa. The chromatic number of random Borsuk graphs. Random Structures Algorithms, 56(3):838–850, 2020. doi:10.1002/rsa.20897.
[Koz08] D. Kozlov. Combinatorial algebraic topology, volume 21 of Algorithms and Computation in Mathematics. Springer, Berlin, 2008.
[Lan02] S. Lang. Algebra, volume 211 of Graduate Texts in Mathematics. Springer-Verlag, New York, third edition, 2002. doi:10.1007/978-1-4613-0041-0.
[Lov78] L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3):319–324, 1978. doi:10.1016/0097-3165(78)90022-5.
[Mat02] J. Matoušek. Lectures on discrete geometry. Springer, New York, 2002.
[Mat08] J. Matoušek. Using the Borsuk–Ulam Theorem. Springer Berlin Heidelberg, 2008. doi:10.1007/978-3-540-76649-0.
[Pen03] M. Penrose. Random Geometric Graphs (Oxford Studies in Probability). Oxford University Press, jul 2003. URL https://www.xarg.org/ref/a/0198506260/.
[PRS17] R. I. Prosanov, A. M. Raĭgorodskiĭ, and A. A. Sagdeev. Improvements of the Frankl-Rödl theorem and the geometric consequences. Dokl. Akad. Nauk, 475(2):137–139, 2017. doi:10.1134/s106456241704007x.
[Rai12] A. M. Raigorodskii. On the chromatic numbers of spheres in ${\mathbb{R}}^{n}$ . Combinatorica, 32(1):111–123, 2012. doi:10.1007/s00493-012-2709-9.
[Sag18] A. A. Sagdeev. An improved Frankl-Rödl theorem and some of its geometric consequences. Problemy Peredachi Informatsii, 54(2):45–72, 2018. doi:10.1134/s0032946018020047.
[Gurobi] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://www.gurobi.com.
[SageMath] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.2), 2021. URL https://www.sagemath.org.

	$\displaystyle\text{Vol}_{d}\!\left(E\right)$	$\displaystyle=\frac{\text{Vol}_{d}\!\left(\Phi E\right)}{\|\det A\|}$
		$\displaystyle\leq\frac{\text{Vol}_{d}\!\left((\pi\Phi E)\times[0,1]\right)}{\|\det A\|}=\frac{\text{Vol}_{d-1}\!\left(\pi\Phi E\right)\cdot 1}{\|\det A\|}$
		$\displaystyle=\frac{\|\det A^{\prime}\|}{\|\det A\|}\text{Vol}_{d-1}\!\left(\varphi^{-1}\pi\Phi E\right)=C\text{Vol}_{d-1}\!\left(\Psi E\right).$

Generalized Borsuk Graphs

Abstract

1 Introduction

2 Background

Definition 2.1 (GG-spaces).

Definition 2.2 (Simplicial GG-spaces).

Definition 2.3 (GG-maps).

Definition 2.4 (Finite Classifying Spaces).

Examples 2.5.

Definition 2.6 (GG-index).

Theorem 2.7 ([Mat08, Prop. 6.2.4]).

Definition 2.8.

Definition 2.9.

3 Definitions and Results

Definition 3.1 (GG-Borsuk Graphs).

Definition 3.2 (GG-covering number).

Notation:

Theorem 3.3.

Theorem 3.4.

Conjecture 3.5.

Conjecture 3.6.

Corollary 3.7 (Generalization of LSB-Theorem).

Proof.

Definition 3.8 (Random GG-Borsuk graphs).

Theorem 3.9.

Corollary 3.10.

Proof.

4 Properties of cov𝑮\bm{\text{cov}_{G}}

Theorem 4.1.

Proof.

Theorem 4.2.

Proof.

Lemma 4.3.

Proof.

5 Lower Bound

Theorem 5.1.

Definition 5.2.

Definition 5.3.

Lemma 5.4.

Proof.

5.1 Hom​(𝑲𝒎,⋅)\bm{\text{Hom}(K_{m},\cdot)} as 𝑮\bm{G}-space.

5.2 Proof of Theorem 5.1

6 Upper Bounds

Theorem 6.1.

Proof.

Theorem 6.2.

Lemma 6.3.

Proof.

Lemma 6.4.

Proof.

Proof of Theorem 6.2.

Theorem 6.5.

Proof.

7 Random 𝑮\bm{G}-Borsuk Graphs

Definition 7.1 (Random GG-Borsuk graphs).

Theorem 7.2.

7.1 Some Geometric Lemmas

Lemma 7.3.

Proof.

Lemma 7.4.

Proof.

Lemma 7.5.

Proof.

7.2 Other Preliminary Results

Lemma 7.6.

Theorem 7.7.

Proof.

Lemma 7.8.

Proof.

Lemma 7.9.

Proof.

7.3 Proof of Theorem 7.2

7.3.1 Dense Case

Proof of dense case.

7.3.2 Sparse Case

Theorem 7.10 (Poissonization).

Lemma 7.11.

Lemma 7.12.

Proof.

Proof of Sparse Case.

Definition 2.1 ( $G$ -spaces).

Definition 2.2 (Simplicial $G$ -spaces).

Definition 2.3 ( $G$ -maps).

Definition 2.6 ( $G$ -index).

Definition 3.1 ( $G$ -Borsuk Graphs).

Definition 3.2 ( $G$ -covering number).

Definition 3.8 (Random $G$ -Borsuk graphs).

4 Properties of $\bm{\text{cov}_{G}}$

5.1 $\bm{\text{Hom}(K_{m},\cdot)}$ as $\bm{G}$ -space.

7 Random $\bm{G}$ -Borsuk Graphs

Definition 7.1 (Random $G$ -Borsuk graphs).

3D Case for $\bm{\mathbb{Z}_{3}}$