remark remark∎

# Neighborhood Variants of the KKM Lemma,
Lebesgue Covering Theorem, and Sperner’s Lemma on the Cube

Jason Vander Woude  Department of Mathematics and School of Computing,
University of Nebraska-Lincoln  Peter Dixon  Independent Researcher  A. Pavan
Department of Computer Science, Iowa State University  Jamie Radcliffe
Department of Mathematics, University of Nebraska-Lincoln  N. V. Vinodchandran
School of Computing, University of Nebraska-Lincoln

###### Abstract

We establish a “neighborhood” variant of the cubical KKM lemma and the
Lebesgue covering theorem and deduce a discretized version which is a
“neighborhood” variant of Sperner’s lemma on the cube. The main result is the
following: for any coloring of the unit $d$-cube $[0,1]^{d}$ in which points
on opposite faces must be given different colors, and for any $\varepsilon>0$,
there is an $\ell_{\infty}$ $\varepsilon$-ball which contains points of at
least $(1+\frac{\varepsilon}{1+\varepsilon})^{d}$ different colors, (so in
particular, at least $(1+\frac{2}{3}\varepsilon)^{d}$ different colors for all
sensible $\varepsilon\in(0,\frac{1}{2}]$).

###### Contents

  1. 1 Introduction
    1. 1.1 The Lebesgue Covering Theorem and the KKM Lemma on the Cube
    2. 1.2 Sperner’s Lemma on the Cube
    3. 1.3 Outline
    4. 1.4 Notation
  2. 2 Proof of the Theorem 1.3 (Neighborhood KKM-Lebesgue Theorem).
  3. 3 Proof of the Theorem 1.12 (Neighborhood Sperner Lemma).
  4. 4 Discussion
  5. 5 Acknowledgements
  6. A Skipped Proofs
    1. A.1 Equivalence of the KKM Lemma, Lebesgue Covering Theorem, and Color Variant
    2. A.2 Background for the Theorem 1.3 (Neighborhood KKM-Lebesgue Theorem).
  7. B Proof of the Folklore 2 Proof of the Theorem 1.3 (Neighborhood KKM-Lebesgue Theorem).

######  Note.

The main result of this paper (*kkm-lebesgue-variant ( (Neighborhood KKM-
Lebesgue Theorem).)) along with most contents of the appendices originally
appeared in a theoretical computer science paper of ours currently in the
computer science category of ArXiv [10]. The purpose of the present article is
to highlight this result on its own and make it more visible to the
mathematical community. It is reproduced here along with a detailed
motivation, additional discussion, and a discretized version of the result
that does not appear in [10]. We note, however, that [10] contains additional
results including an analogous result for $\mathbb{R}^{d}$ (as compared to
$[0,1]^{d}$ here) which will not be discussed in this paper; in that context a
slightly better bound of $(1+2\varepsilon)^{d}$ (as compared to
$(1+\frac{2}{3}\varepsilon)^{d}$ here) can be achieved. Furthermore, [10]
includes results for every norm on $\mathbb{R}^{d}$ (not just
$\ell_{\infty}$), but this is less natural on $[0,1]^{d}$, so in this paper we
focus only on the $\ell_{\infty}$ norm.

##  1 Introduction

The Lebesgue covering theorem (see [6] or [3, Theorem IV 2]), Sperner’s lemma
on the cube (see [1]), and the KKM lemma on the cube (see [5, 11, 4, 8]) are
all known to be naturally equivalent in that any of the three results can be
used to fairly directly prove any of the others. Informally, they guarantee
that in any well-behaved coloring/covering of the $d$-dimensional cube, there
exists a point at the closure of at least $d+1$ colors/sets. We prove the
following “neighborhood” variant(s) of these results by considering an open
ball instead of a point: for any well-behaved coloring/covering of the
$d$-dimensional cube and any $\varepsilon>0$, there exists a placement of the
$\ell_{\infty}$ $\varepsilon$-ball (i.e. a cube of side length $2\varepsilon$)
which intersects at least $(1+\frac{\varepsilon}{1+\varepsilon})^{d}$
colors/sets. Thus, while the traditional results give a linear bound ($d+1$)
on the number of colors/sets, for any fixed $\varepsilon$, our neighborhood
variant gives an exponential (in $d$) bound on the number of colors/sets.

We first state a theorem which is naturally equivalent111 The equivalence is
discussed in subsec:kkm-lebesgue and proved in subsec:kkm-lebesgue-coloring-
equivalence.  to both the cubical KKM lemma and the Lebesgue covering theorem
but stated in terms of colorings to be more convenient to work with (kkm-
lebesgue). Then we formally state our main result (kkm-lebesgue-variant) which
is a neighborhood variant of kkm-lebesgue. As direct corollaries of kkm-
lebesgue-variant, we obtain neighborhood variants of both the cubical KKM
lemma and the Lebesgue covering theorem. We also demonstrate that under an
appropriate perspective, our main result implies a neighborhood variant of
Sperner’s lemma on the cube.

Below, we consider $[0,1]^{d}$ to be the standard unit $d$-cube and
$V=\\{0,1\\}^{d}$ to be its set of vertices. A face $F$ of the cube
$[0,1]^{d}$ is a product set $F=\prod_{i=1}^{d}F_{i}$ where each $F_{i}$ is
one of three sets: $\\{0\\}$, $\\{1\\}$, or $[0,1]$. For a set
$X\subseteq\mathbb{R}^{d}$ and coordinate $i\in[d]$, we will use the
projection notation $\pi_{i}(X)=\\{x_{i}:\vec{x}\in X\\}$. Two faces
$F,F^{\prime}$ are said to be opposite each other if there is some coordinate
$i_{0}\in[d]$ such that $F_{i_{0}}=\\{0\\}$ and $F_{i_{0}}^{\prime}=\\{1\\}$
(or vice versa). We will frequently say that a pair of points
$\vec{x},\vec{x}\,^{\prime}\in[0,1]^{d}$ belong to opposite faces if there is
an opposite pair of faces $F,F^{\prime}$ with $\vec{x}\in F$ and
$\vec{x}\,^{\prime}\in F^{\prime}$. Equivalently, a pair of points
$\vec{x},\vec{x}\,^{\prime}\in[0,1]^{d}$ belong to opposite faces if there is
some coordinate $i_{0}\in[d]$ such that $x_{i_{0}}=0$ and
$x^{\prime}_{i_{0}}=1$ (or vice versa). A final equivalent characterization is
that a pair of points $\vec{x},\vec{x}\,^{\prime}\in[0,1]^{d}$ belong to
opposite faces if
$\left\lVert\vec{x}-\vec{x}\,^{\prime}\right\rVert_{\infty}=1$. We will say
that a set $S$ does not contain points of opposite faces if for every pair of
opposite faces $F,F^{\prime}$ at least one of $S\cap F$ and $S\cap F^{\prime}$
is empty. Equivalently, $S$ does not contain points of opposite faces if no
pair of points from $S$ are $\ell_{\infty}$ distance $1$ apart.

######  Definition 1.1 (Sperner-Lebesgue-Knaster-Kuratowski-Mazurkiewicz
Coloring).

For a set $\Lambda\subseteq[0,1]^{d}$ (possibly $\Lambda=[0,1]^{d}$), an SLKKM
coloring of $\Lambda$ is a function $\chi:\Lambda\to C$ for some set $C$ such
that $\chi$ does not map points on opposite faces to the same color. If
$\left\lvert C\right\rvert<\infty$, we call $\chi$ a finite SLKKM coloring.

######  Theorem 1.2 (KKM-Lebesgue Theorem).

Given a finite SLKKM coloring $\chi$ of $[0,1]^{d}$, there exists a point
$\vec{p}\in[0,1]^{d}$ belonging to the closure of at least $d+1$ color sets
(i.e. $\big{\lvert}\\{c\in
C:\vec{p}\in\overline{\chi^{-1}(c)}\\}\big{\rvert}\geq d+1$).

The main result of this paper is that if we are interested in a small cubical
region (an open $\ell_{\infty}$ $\varepsilon$-ball), rather than a single
point as in the  (KKM-Lebesgue Theorem)., then for any SLKKM coloring we can
find a point $\vec{p}$ where the open $\ell_{\infty}$ $\varepsilon$-ball at
$\vec{p}$ intersects a significant number of colors. The focus on an open ball
instead of a point is why we consider this to be a “neighborhood” variant of
the cubical KKM lemma and the Lebesgue covering theorem. In the statement
below, $B^{\circ}_{\infty}(\varepsilon,\vec{p})$ denotes the open
$\varepsilon$-ball at $\vec{p}$ with respect to the $\ell_{\infty}$ norm.

######  Theorem 1.3 (Neighborhood KKM-Lebesgue Theorem).

Given an SLKKM coloring of $[0,1]^{d}$, for any $\varepsilon\in(0,\infty)$
there exists a point $\vec{p}\in[0,1]^{d}$ such that
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ contains points of at least
$\left\lceil\big{(}1+\frac{\varepsilon}{1+\varepsilon}\big{)}^{d}\right\rceil$
different colors. In particular, if $\varepsilon\in(0,\frac{1}{2}]$ then
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ contains points of at least
$\left\lceil\big{(}1+\frac{2}{3}\varepsilon\big{)}^{d}\right\rceil$ different
colors.

The proof will be given in sec:proof, but for now we offer three comments
about this theorem. First, we no longer need a finiteness assumption (as in
the  (KKM-Lebesgue Theorem).) because we are not working with closures222 The
reason the  (KKM-Lebesgue Theorem). requires finiteness is because for a
finite collection of sets, the union of closures equals the closure of unions,
but this property does not hold in general for infinite collections. Even
without the finiteness condition, it is still the case that there exists a
point $\vec{p}$ such that every open set containing $\vec{p}$ intersects at
least $d+1$ colors. See for example the proof of kkm-implies-kkm-lebesgue
where this is demonstrated. The  (KKM-Lebesgue Theorem). does not hold in
general without the finiteness hypothesis as demonstrated by the non-finite
SLKKM coloring which assigns a unique color to each point of $[0,1]^{d}$. .
Second, restricting to $\varepsilon\leq\frac{1}{2}$ in the above statement is
reasonable because for $\varepsilon>\frac{1}{2}$ the $\ell_{\infty}$
$\varepsilon$-ball can be placed at the center of the unit cube and is then a
superset of the cube and hence it contains all the points in the cube. Note
that no two vertices of the cube can have the same color in an SLKKM coloring
as they belong to opposite faces. This means that every SLKKM coloring uses at
least $2^{d}$ colors (and there exist SLKKM colorings with only $2^{d}$
colors—e.g. color each of the $2^{d}$ orthants a distinct color). Thus, for
$\varepsilon>\frac{1}{2}$, we don’t need the bound of
$\left\lceil\big{(}1+\frac{\varepsilon}{1+\varepsilon}\big{)}^{d}\right\rceil$
in the  (Neighborhood KKM-Lebesgue Theorem). since we just demonstrated a
better (tight) bound of $2^{d}$. For this reason, it is sensible to only
consider $\varepsilon\leq\frac{1}{2}$ in the statement of the  (Neighborhood
KKM-Lebesgue Theorem). and consequently obtain the cleaner (and only
moderately worse) bound of
$\left\lceil\big{(}1+\frac{2}{3}\varepsilon\big{)}^{d}\right\rceil$.

Third, while the statement is given for fixed $\varepsilon$ and $d$, we have
already encountered applications of this theorem where $\varepsilon$ is a
function of the dimension $d$ (see [9, 10]), so we briefly note the asymptotic
behavior of this bound. If $\varepsilon\in O\left(\frac{1}{d}\right)$, then
our lower bound on the number of colors given by the  (Neighborhood KKM-
Lebesgue Theorem). is an $O(1)$ bound333 This is because
$\lim_{d\to\infty}(1+\frac{c}{d})^{d}=e^{c}$.  which is asymptotically worse
than the value $d+1$ given in the  (KKM-Lebesgue Theorem).. However, if
$\varepsilon\in\omega\left(\frac{\ln(d)}{d}\right)$ then our bound is super-
polynomial in the dimension444 Let $k=(1+\frac{2}{3}\varepsilon)^{d}$. Because
$\varepsilon\in(0,\frac{1}{2}]$ we have
$\frac{2}{3}\varepsilon\in(0,\frac{1}{3}]$. Using the inequality
$\ln(1+x)\geq\frac{x}{2}$ for small enough $x$ (in particular for
$x\in(0,\frac{1}{3}]$) we have
$\ln(k)=d\ln(1+\frac{2}{3}\varepsilon)\geq\frac{1}{3}d\varepsilon$, so
$\varepsilon\leq\frac{3\ln(k)}{d}$. Thus, if the bound $k$ is polynomial in
$d$, then $\varepsilon\in O\left(\frac{\ln(d)}{d}\right)$, so if
$\varepsilon\in\omega\left(\frac{\ln(d)}{d}\right)$ the $k$ is not polynomial
in $d$. . In particular, if $\varepsilon\in\Theta(1)$, then our bound is
asymptotically exponential in $d$.

###  1.1 The Lebesgue Covering Theorem and the KKM Lemma on the Cube

We will now briefly discuss the standard statements of the Lebesgue covering
theorem and the cubical version of the KKM Lemma and how they relate to the
(KKM-Lebesgue Theorem). (*kkm-lebesgue). We can capture the hypotheses of the
Lebesgue covering theorem and the cubical KKM lemma with the following two
definitions. A Lebesgue cover is a finite closed cover of $[0,1]^{d}$ with no
set containing points on opposite faces. Informally, a KKM cover is a finite
closed cover of $[0,1]^{d}$ with the sets of the cover associated to the
vertices of the cube; we require that any point in a face $F$ is covered by
one of the sets corresponding to the vertices defining $F$.

######  Definition 1.4 (Lebesgue Cover).

A Lebesgue cover of $[0,1]^{d}$ is an indexed family
$\mathcal{C}=\\{C_{n}\\}_{n\in[N]}$ of closed subsets of $\mathbb{R}^{d}$ (for
some $N\in\mathbb{N}$) which covers $[0,1]^{d}$ such that for each $n\in[N]$,
$C_{n}$ does not contain points on opposite faces of the cube.

######  Definition 1.5 (KKM Cover).

A KKM cover of $[0,1]^{d}$ is an indexed family
$\mathcal{C}=\\{C_{\vec{v}}\\}_{\vec{v}\in\\{0,1\\}^{d}}$ of closed subsets of
$\mathbb{R}^{d}$ such that for each face $F$ of the cube,
$F\subseteq\bigcup_{\vec{v}\in F\cap\\{0,1\\}^{d}}C_{\vec{v}}$. (In
particular, the cube itself is a face, so the cube is covered.)

While the two notions of covers are different from each other555 For example,
consider the indexed family
$\mathcal{C}=\\{C_{\vec{v}}\\}_{\vec{v}\in\\{0,1\\}^{d}}$ where
$C_{\vec{v}}=[0,1]^{d}$ for each $\vec{v}$; this is a KKM cover, but not a
Lebesgue cover. Conversely, a finite Lebesgue cover with cardinality exceeding
$\left\lvert\\{0,1\\}^{d}\right\rvert=2^{d}$ is not a KKM cover. , they are
both sufficient to guarantee the same conclusion as in the  (KKM-Lebesgue
Theorem).: at least $d+1$ sets in the cover meet at some point.

######  Theorem 1.6 (Lebesgue Covering Theorem).

Given a Lebesgue cover of $[0,1]^{d}$, there exists a point
$\vec{p}\in[0,1]^{d}$ belonging to at least $d+1$ sets in the cover (i.e.
$\left\lvert\\{n\in[N]:\vec{p}\in C_{n}\\}\right\rvert\geq d+1$).

######  Theorem 1.7 (Cubical KKM Lemma).

Given a KKM cover of $[0,1]^{d}$, there exists a point $\vec{p}\in[0,1]^{d}$
belonging to at least $d+1$ sets in the cover (i.e.
$\left\lvert\\{\vec{v}\in\\{0,1\\}^{d}:\vec{p}\in
C_{\vec{v}}\\}\right\rvert\geq d+1$).

These results are well known and can be found for example in [5, 11, 4, 8, 1]
for the  (Cubical KKM Lemma). and in [6] or [3, Theorem IV 2] for the
(Lebesgue Covering Theorem).. Though the  (Lebesgue Covering Theorem)., the
(Cubical KKM Lemma)., and the  (KKM-Lebesgue Theorem). (our coloring
combination of the two) are all naturally equivalent to each other (a careful
proof of this folklore result is given in subsec:kkm-lebesgue-coloring-
equivalence), we chose to use the  (KKM-Lebesgue Theorem). to represent these
two more famous results and motivate our main result (the  (Neighborhood KKM-
Lebesgue Theorem).) for the following reasons.

For our purposes, we don’t want to work directly with a KKM cover because we
need to deal with extensions along boundaries that are cumbersome to work with
for a KKM cover since sets can intersect opposite faces. We also don’t want to
work with Lebesgue covers because the definition of a Lebesgue cover actually
implies that every set in the cover (when viewed as a subset of $[0,1]^{d}$)
has $\ell_{\infty}$ diameter strictly less than $1$, but we are okay with sets
that have diameter $1$ as long as they don’t contain points on opposite faces
(i.e. no points in the set attain $\ell_{\infty}$ distance $1$ from each
other). Also, we don’t want to require the sets to be closed which is formally
a requirement of both types of covers.

Nonetheless, as one may expect, our main result (the  (Neighborhood KKM-
Lebesgue Theorem).) can be equivalently restated by replacing the SLKKM
coloring hypothesis with either a Lebesgue cover (corollary:neighborhood-
lebesgue) or a KKM cover (corollary:neighborhood-kkm). The proofs that these
corollaries follow from the  (Neighborhood KKM-Lebesgue Theorem). are given
after the statements below. As this direction of the implications is
sufficient to prove all three results, we don’t provide the proofs of the
reverse implications of the equivalence, but the main ideas are identical to
those used to prove the equivalence of the  (Cubical KKM Lemma)., the
(Lebesgue Covering Theorem)., and the  (KKM-Lebesgue Theorem). (found in
subsec:kkm-lebesgue-coloring-equivalence).

######  Corollary 1.8 (Neighborhood Lebesgue Theorem).

Given a Lebesgue cover of $[0,1]^{d}$, for any $\varepsilon\in(0,\infty)$
there exists a point $\vec{p}\in[0,1]^{d}$ such that
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects at least
$\left\lceil\big{(}1+\frac{\varepsilon}{1+\varepsilon}\big{)}^{d}\right\rceil$
sets in the cover. In particular, if $\varepsilon\in(0,\frac{1}{2}]$ then
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects at least
$\left\lceil\big{(}1+\frac{2}{3}\varepsilon\big{)}^{d}\right\rceil$ sets in
the cover.

######  Corollary 1.9 (Neighborhood KKM Theorem).

Given a KKM cover of $[0,1]^{d}$, for any $\varepsilon\in(0,\infty)$ there
exists a point $\vec{p}\in[0,1]^{d}$ such that
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects at least
$\left\lceil\big{(}1+\frac{\varepsilon}{1+\varepsilon}\big{)}^{d}\right\rceil$
sets in the cover. In particular, if $\varepsilon\in(0,\frac{1}{2}]$ then
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects at
least$\left\lceil\big{(}1+\frac{2}{3}\varepsilon\big{)}^{d}\right\rceil$ sets
in the cover.

###### Proof of corollary:neighborhood-lebesgue from the  (Neighborhood KKM-
Lebesgue Theorem). (*kkm-lebesgue-variant).

Let $N\in\mathbb{N}$ and $\mathcal{C}=\\{C_{n}\\}_{n\in[N]}$ be a Lebesgue
cover of $[0,1]^{d}$. Because this is a cover, every point of $[0,1]^{d}$
belongs to some set, so define $\chi$ as follows:

$\displaystyle\chi$ $\displaystyle:[0,1]^{d}\to[N]$
$\displaystyle\chi(\vec{x})$ $\displaystyle=\min\\{n\in[N]:\vec{x}\in
C_{n}\\}.$

This is trivially a finite SLKKM coloring of $[0,1]^{d}$ because the codomain
of $\chi$ is finite and for $\vec{x}^{(0)}$ and $\vec{x}^{(1)}$ on opposite
faces, there is no $n\in[N]$ for which both $\vec{x}^{(0)}\in C_{n}$ and
$\vec{x}^{(1)}\in C_{n}$ and thus $\\{n\in[N]:\vec{x}^{(0)}\in C_{n}\\}$ and
$\\{n\in[N]:\vec{x}^{(1)}\in C_{n}\\}$ are disjoint, so
$\chi(\vec{x}^{(0)})\not=\chi(\vec{x}^{(1)})$.

Note that $\chi^{-1}(n)$ is the set of points of color $n$. By the
(Neighborhood KKM-Lebesgue Theorem)., there exists $\vec{p}\in[0,1]^{d}$ such
that

$\left\lvert\\{n\in[N]:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap\chi^{-1}(n)\\}\right\rvert\geq\left(1+\tfrac{\varepsilon}{1+\varepsilon}\right)^{d}.$

Fix such a $\vec{p}$ for the remainder of the proof. For each $n\in[N]$,
observe that $\chi^{-1}(n)\subseteq C_{n}$ because for any
$\vec{x}\in\chi^{-1}(n)$ we have $\chi(\vec{x})=n$, so by definition of $\chi$
we have $\vec{x}\in C_{n}$. The following subset containment then follows
immediately:

$\\{n\in[N]:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap\chi^{-1}(n)\not=\emptyset\\}\quad\subseteq\quad\\{n\in[N]:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap
C_{n}\not=\emptyset\\}.$

and since the former has cardinality at least
$(1+\frac{\varepsilon}{1+\varepsilon})^{d}$, so does the latter, which proves
the result. (The “in particular” part of the result is just an arithmetic fact
which is demonstrated in the proof of the  (Neighborhood KKM-Lebesgue
Theorem). (*kkm-lebesgue-variant).) ∎

###### Proof of corollary:neighborhood-kkm from the  (Neighborhood KKM-
Lebesgue Theorem). (*kkm-lebesgue-variant).

Let $\mathcal{C}=\\{C_{\vec{v}}\\}_{\vec{v}\in\\{0,1\\}^{d}}$ be a KKM cover
of $[0,1]^{d}$. For each $\vec{x}\in[0,1]^{d}$, let $F_{\vec{x}}$ denote the
smallest face of the cube containing $\vec{x}$ (i.e. $F_{\vec{x}}$ is the
intersection of all faces containing $\vec{x}$, and it is well-known and
easily verified that this intersection is also a face). By the defining
property of a KKM cover, we have $F_{\vec{x}}\subseteq\bigcup_{\vec{v}\in
F_{\vec{x}}\cap\\{0,1\\}^{d}}C_{\vec{v}}$, so in particular there exists some
$\vec{v}\in F_{\vec{x}}\cap\\{0,1\\}^{d}$ with $\vec{x}\in C_{\vec{v}}$.
Define the function $\chi$ as follows where $\min_{\mathrm{lex}}$ denotes the
minimum element in a subset of $\\{0,1\\}^{d}$ under the lexicographic
ordering:

$\displaystyle\chi$ $\displaystyle:[0,1]^{d}\to\\{0,1\\}^{d}$
$\displaystyle\chi(\vec{x})$ $\displaystyle=\min_{\mathrm{lex}}\\{\vec{v}\in
F_{\vec{x}}\cap\\{0,1\\}^{d}:\vec{x}\in C_{\vec{v}}\\}$

We have already demonstrated that the the set in the definition is not empty,
so $\chi$ is well-defined.

We claim that $\chi$ is a finite SLKKM coloring of $[0,1]^{d}$. The finiteness
is trivial because the codomain of $\chi$ is finite, so we need only show it
is an SLKKM coloring. Suppose $F^{(0)}$ and $F^{(1)}$ are opposite faces of
the cube (i.e. there is some coordinate $j\in[d]$ such that
$\pi_{j}(F^{(0)})=\\{0\\}$ and $\pi_{j}(F^{(1)})=\\{1\\}$) and let
$\vec{x}^{(0)}\in F^{(0)}$ and $\vec{x}^{(1)}\in F^{(1)}$. Because
$\pi_{j}(F^{(0)})\cap\pi_{j}(F^{(1)})=\emptyset$, it follows that $F^{(0)}\cap
F^{(1)}=\emptyset$, so $F^{(0)}$ and $F^{(1)}$ are disjoint sets.

Now consider the faces $F_{\vec{x}^{(0)}}$ and $F_{\vec{x}^{(1)}}$. Because
$\vec{x}^{(0)}\in F^{(0)}$ and $F_{\vec{x}^{(0)}}$ is by definition the
intersection of all faces containing $\vec{x}^{(0)}$, we have
$F_{\vec{x}^{(0)}}\subseteq F^{(0)}$ (and similarly replacing “$0$” with
“$1$”) so that also $F_{\vec{x}^{(0)}}$ and $F_{\vec{x}^{(1)}}$ are disjoint.
By definition of $\chi$ we have $\chi(\vec{x}^{(0)})\in F_{\vec{x}^{(0)}}$ and
$\chi(\vec{x}^{(1)})\in F_{\vec{x}^{(1)}}$ showing that
$\chi(\vec{x}^{(0)})\not=\chi(\vec{x}^{(1)})$, so $\chi$ is an SLKKM coloring.

By the  (Neighborhood KKM-Lebesgue Theorem)., there exists
$\vec{p}\in[0,1]^{d}$ such that

$\left\lvert\\{\vec{v}\in\\{0,1\\}^{d}:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap\chi^{-1}(\vec{v})\not=\emptyset\\}\right\rvert\geq\left(1+\tfrac{\varepsilon}{1+\varepsilon}\right)^{d}.$

Fix such a $\vec{p}$ for the remainder of the proof. For each
$\vec{v}\in\\{0,1\\}^{d}$, observe that $\chi^{-1}(\vec{v})\subseteq
C_{\vec{v}}$ because for any $\vec{x}\in\chi^{-1}(\vec{v})$ we have
$\chi(\vec{x})=\vec{v}$, so by definition of $\chi$ we have $\vec{x}\in
C_{\vec{v}}$. The following subset containment then follows immediately:

$\\{\vec{v}\in\\{0,1\\}^{d}:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap\chi^{-1}(\vec{v})\not=\emptyset\\}\quad\subseteq\quad\\{\vec{v}\in\\{0,1\\}^{d}:B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap
C_{\vec{v}}\not=\emptyset\\}.$

and since the former has cardinality at least
$(1+\frac{\varepsilon}{1+\varepsilon})^{d}$, so does the latter which proves
the result. (The “in particular” part of the result is just an arithmetic fact
which is demonstrated in the proof of the  (Neighborhood KKM-Lebesgue
Theorem). (*kkm-lebesgue-variant).) ∎

###  1.2 Sperner’s Lemma on the Cube

In light of the fact that our main result can (and should) be viewed as a
neighborhood variant of the  (Lebesgue Covering Theorem). and the  (Cubical
KKM Lemma)., it is natural to ask whether we can obtain a discretized version
of our result to serve as a neighborhood version of Sperner’s lemma on the
cube, and the answer is yes.

It is important to note that there are multiple natural ways to adapt
Sperner’s lemma from the simplex to the cube. For example, [1] considers
subdividing the cube into simplices and using $2^{d}$ colors (because this is
natural in the broader polytope setting in which they work) while [5]
considers subdividing the cube into smaller cubes but still using $2^{d}$
colors, and [11] considers a subdivision into smaller cubes with either
$2^{d}$ colors or with $d+1$ colors.

Clearly, it would not make sense to try to consider our style of result for
the cubical adaptions of Sperner’s lemma which use $d+1$ colors because we
cannot possibly hope in general for some $\varepsilon$-ball to intersect
$\left\lceil\big{(}1+\frac{2}{3}\varepsilon\big{)}^{d}\right\rceil$-many
colors if only $d+1$ colors are used. Thus, the natural context for us is the
cubical adaptions of Sperner’s lemma in which $2^{d}$ colors are used.

Another observation is that arbitrary triangulations or cube decompositions of
$[0,1]^{d}$ defined by some set of points $\Lambda$ are not strong enough for
us. We are working with an $\varepsilon$-ball, so we need to have some
information about how close together points in $\Lambda$ are from each other.
We define below the notion we will use to make our main result discrete;
informally, a set $\Lambda$ is called $\rho$-proximate if every point within a
face $F$ is distance at most $\rho$ from a point in $\Lambda$ which belongs to
the same face $F$. In the formal definition below, while $\Lambda$ can be
thought of as a discrete set, this is not necessary.

######  Definition 1.10 ($\rho$-Proximate Set).

Let $\Lambda\subseteq[0,1]^{d}$. For $\rho\in[0,\infty)$, $\Lambda$ is called
$\rho$-proximate if for every face $F$ of $[0,1]^{d}$ and for every
$\vec{x}\in F$, there exists $\vec{y}\in F\cap\Lambda$ such that
$\left\lVert\vec{x}-\vec{y}\right\rVert_{\infty}\leq\rho$.

######  Remark 1.11.

We could have equivalently rephrased the last part of the definition as
“$\ldots$ for every face $F$ of $[0,1]^{d}$ and for every $\vec{x}\in F$, we
have $F\cap\Lambda\cap\overline{B}_{\infty}(\rho,\vec{x})\not=\emptyset$”. Or
we could have equivalently rephrased it as “$\ldots$ for every face $F$ of
$[0,1]^{d}$, we have $F\subseteq\bigcup_{\vec{p}\in
F\cap\Lambda}\overline{B}_{\infty}(\rho,\vec{p})$”. Or we could have
equivalently rephrased it as “$\ldots$ for every face $F$ of $[0,1]^{d}$, we
have $F\subseteq(F\cap\Lambda)+\overline{B}_{\infty}(\rho,\vec{0})$” where
“$+$” denotes the Minkowski sum of the two sets.

Of particular note is that for any $\rho\in[0,1]$ (taking $n=\left\lfloor
1/\rho\right\rfloor$) the grid
$\\{0,\rho,2\rho,\ldots,(n-1)\rho,n\rho,1\\}^{d}$ of $(n+2)^{d}$ points is
$\rho$-proximate. This grid occurs naturally in many contexts and is one of
the simplest settings in which we can consider discretizing the main result.

Now, if we discretize the coloring hypothesis of the  (Neighborhood KKM-
Lebesgue Theorem). to a set of points that are $\rho$-proximate, then we get
the same conclusion as the  (Neighborhood KKM-Lebesgue Theorem). but have to
account for this spacing using the triangle inequality. Therefore, an
“effective $\varepsilon$” of “$\varepsilon-\rho$” appears in the result.

######  Theorem 1.12 (Neighborhood Sperner Lemma).

Let $\rho\in[0,\infty)$ and $\Lambda\subseteq[0,1]^{d}$ be $\rho$-proximate.
Let $\rho^{\prime}=\min(\rho,\frac{1}{2})$. Given an SLKKM coloring of
$\Lambda$, for any $\varepsilon\in(0,\infty)$ there exists a point
$\vec{p}\in[0,1]^{d}$ such that $B^{\circ}_{\infty}(\varepsilon,\vec{p})$
contains points of at least
$\left\lceil\Big{(}1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})}\Big{)}^{d}\right\rceil$
different colors. In particular, if $\varepsilon\in(0,\frac{1}{2}]$ then
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ contains points of at least
$\left\lceil\big{(}1+\frac{2}{3}(\varepsilon-\rho^{\prime})\big{)}^{d}\right\rceil$
different colors.

The proof is given in sec:sperner.

######  Remark 1.13.

The  (Neighborhood Sperner Lemma). and the  (Neighborhood KKM-Lebesgue
Theorem). are in fact naturally equivalent. We will prove the  (Neighborhood
Sperner Lemma). as a corollary of the  (Neighborhood KKM-Lebesgue Theorem).
showing one direction of the equivalence. For the other direction, we recover
the statement of the  (Neighborhood KKM-Lebesgue Theorem). from the
(Neighborhood Sperner Lemma). in the special case that $\Lambda=[0,1]^{d}$ and
$\rho=0$ (because $[0,1]^{d}$ is $0$-proximate).

It should be unsurprising that the definition of $\rho$-proximate includes the
property that every point of the cube is within distance $\rho$ of a point in
$\Lambda$ because we want to show that some point $\vec{p}$ is
$\varepsilon$-close to many colors, so we need to know that the color classes
(and thus the points in $\Lambda$) are not all mutually far apart666 A set
with this requirement is called a $\rho$-net in some contexts. . The condition
that such points must belong to the same face may be less obvious but probably
not surprising considering the nature of Sperner’s lemma and the KKM lemma;
the reason we need such a property is demonstrated by the set
$\Lambda=(0,1)^{d}$. If we didn’t require that the point $\vec{y}$ in
defn:proximate is in both $F$ and $\Lambda$, then the set $\Lambda=(0,1)^{d}$
would be $\rho$-proximate for each $\rho\in(0,\infty)$, and yet it would be a
valid SLKKM coloring to assign every point of $\Lambda$ the same color, and
thus we could not guarantee the existence of an $\varepsilon$-ball
intersecting more than $1$ color. As a consequence of this requirement in
defn:proximate, we obtain the following simple property.

######  Remark 1.14.

If $\Lambda$ is $\rho$-proximate for some $\rho\in[0,\infty)$, then $\Lambda$
contains all vertices of the cube (i.e. $\Lambda\supseteq\\{0,1\\}^{d}$). This
is because for any vertex $\vec{v}\in\\{0,1\\}^{d}$, the singleton set
$F=\prod_{i=1}^{d}\\{v_{i}\\}=\\{\vec{v}\\}$ is a face of the cube, so by
definition of $\rho$-proximate, for each $\vec{x}\in F$, there is some
associated $\vec{y}\in F\cap\Lambda$, so in particular
$F\cap\Lambda\not=\emptyset$. Since $F$ contains only the point $\vec{v}$, we
must have $\vec{v}\in\Lambda$.

###  1.3 Outline

The remainder of the paper is laid out as follows. In sec:notation, we briefly
state additional notation we use. In sec:proof, we prove the  (Neighborhood
KKM-Lebesgue Theorem).. In sec:sperner, we prove the  (Neighborhood Sperner
Lemma). as a corollary. We finish in sec:discussion with a short discussion of
how we hope the bounds might be improved, and we mention some limitations on
what is possible. Proofs of lemmas omitted from the main text are included in
sec:appendix. For completeness, we include a proof of the folklore Proof of
the Theorem 1.3 (Neighborhood KKM-Lebesgue Theorem). (*lower-bound-cover-
number-Rd) in appendix:measure-theory which is stated later and is central to
the proof of the  (Neighborhood KKM-Lebesgue Theorem)..

###  1.4 Notation

We write
$B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{p})$
(resp. $B^{\circ}_{\infty}(\varepsilon,\vec{p})$) to indicate the open ball of
radius $\varepsilon$ at $\vec{p}$ with respect to a generic norm
$\left\lVert\cdot\right\rVert$ (resp. the $\ell_{\infty}$ norm). Similarly, we
use
$\overline{B}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{p})$
and $\overline{B}_{\infty}(\varepsilon,\vec{p})$ for closed balls. We use
$v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d}$ to denote the volume
of the unit radius ball in dimension $d$ with respect to a generic norm
$\left\lVert\cdot\right\rVert$. We write $m$ for the Lebesgue measure and
$m_{out}$ for the induced outer measure. For two sets
$A,B\subseteq\mathbb{R}^{d}$, we write $A+B$ to indicate the Minkowski sum
$A+B=\left\\{\vec{a}+\vec{b}:\vec{a}\in A\text{ and }\vec{b}\in B\right\\}$.

##  2 Proof of the  (Neighborhood KKM-Lebesgue Theorem).

We will require a few lemmas for the proof which we state here. Proofs are
provided in appendix-sub:brunn-minkowski. The first result will later allow us
to pass a result through a limit because the answer will be an integer.

factrestatableSmallerCeiling For any $\alpha\in\mathbb{R}$, there exists
$\gamma\in\mathbb{R}$ such that $\gamma<\alpha$ and
$\left\lceil\gamma\right\rceil=\left\lceil\alpha\right\rceil$.

The second result is an inequality that can be proved using basic calculus.
The interpretation of the result is that (for appropriate parameters) in the
expression $(x^{1/d}+\alpha)^{d}$ we can “approximately factor out” the $x$
term because there is both a $d$th root and $d$th power involved to get the no
larger expression $x(1+\alpha)^{d}$. lemmarestatableBrunnMinkowskiBoundLemma
For $d\in[1,\infty)$ and $x\in[0,1]$ and $\alpha\in[0,\infty)$, it holds that
$(x^{1/d}+\alpha)^{d}\geq x(1+\alpha)^{d}$.

The third result is a consequence of the  (Generalized Brunn-Minkowski
Inequality). (discussed in appendix-sub:brunn-minkowski) which says that for
non-empty measurable sets $A,B\subseteq\mathbb{R}^{d}$ for which $A+B$ is also
measurable, it holds that
$m(A+B)\geq\big{(}m(A)^{\frac{1}{d}}+m(B)^{\frac{1}{d}}\big{)}^{d}$. The main
content of our corollary is dealing with non-measurable sets in such a way
that we can apply the  (Generalized Brunn-Minkowski Inequality)..
corollaryrestatableOuterMeasureBrunnMinkowskiBoundLInfty Let $d\in\mathbb{N}$
and $Y\subseteq\mathbb{R}^{d}$ and $\varepsilon\in(0,\infty)$. Then
$Y+B^{\circ}_{\infty}(\varepsilon,\vec{0})$ is open (and thus Borel
measurable), and
$m(Y+B^{\circ}_{\infty}(\varepsilon,\vec{0}))\geq\left(m_{out}(Y)^{\frac{1}{d}}+2\varepsilon\right)^{d}$.

The final result we need is heavily based on the ideas behind the common proof
of Blitchfeldt’s theorem and can be viewed as a continuous version of the
pigeonhole principle with multiplicity. It says that if we have a family of
subsets of $S$ and in total their measure is at least $k\cdot m(S)$, then
there is a point belonging to at least $\left\lceil k\right\rceil$ sets in the
family. While this is a known result, it is frequently enough stated
informally or only in the (very simple) special case $\left\lceil
k\right\rceil=2$ that for completeness and convenience we include a proof in
appendix:measure-theory.

[Continuous Multi-Pigeonhole Principle]proposition-
knownrestatableLowerBoundCoverNumberRd Let $d\in\mathbb{N}$ and
$S\subset\mathbb{R}^{d}$ be measurable with finite measure. Let $\mathcal{A}$
be a family of measurable subsets of $S$ and let
$k=\left\lceil\frac{\sum_{A\in\mathcal{A}}m(A)}{m(S)}\right\rceil$. If
$k<\infty$, then there exists $\vec{p}\in S$ such that $\vec{p}$ belongs to at
least $k$ members of $\mathcal{A}$. If $k=\infty$, then for any integer $n$,
then there exists $\vec{p}\in S$ such that $\vec{p}$ belongs to at least $n$
members of $\mathcal{A}$.

Now we are ready to prove the main result of this work restated below. The
proof is illustrated in fig:sperner-kkm-coloring.

(a) Initial coloring $\chi$

(b) Extended coloring $\gamma$

(c) Red points ($Y_{\text{red}}$)

(e) Purple points ($Y_{\text{purple}}$)

(g) Gray points ($Y_{\text{gray}}$)

(d) Ball added ($Y_{\text{red}}+B_{\vec{v}}$)

(f) Ball added ($Y_{\text{purple}}+B_{\vec{v}}$)

(h) Ball added ($Y_{\text{gray}}+B_{\vec{v}}$)

Figure 1:  1(a) shows an SLKKM coloring $\chi$ of the unit cube
$[-\frac{1}{2},\frac{1}{2}]^{d}$ for $d=2$ (i.e. no color includes points on
opposite edges). 1(b) shows the natural extension $\gamma$ of that coloring to
$[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$. The extension is
obtained by mapping each point
$\vec{y}\in[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ to the
point $\vec{x}\in[-\frac{1}{2},\frac{1}{2}]^{d}$ for which each coordinate
value is restricted to be within $[-\frac{1}{2},\frac{1}{2}]$, and then
$\vec{y}$ is given whatever color $\vec{x}$ had. 1(c), 1(e), and 1(g) show
three of the five colors and demonstrate that there is at least one quadrant
of the $\varepsilon$-ball that can be Minkowski summed with the color so that
the sum remains a subset of the extended cube. For red it is the lower right
quadrant, for purple it is the upper right, and for gray it could be the upper
left (shown) or the upper right. 1(d), 1(f), and 1(h) show the resulting
Minkowski sum for each color. Utilizing the Brunn-Minkowski inequality, this
set will have substantially greater area—by a factor of at least
$(1+\frac{\varepsilon}{1+\varepsilon})^{d}$.

See 1.3

###### Proof.

For convenience, we will assume that the cube is
$[-\frac{1}{2},\frac{1}{2}]^{d}$ rather than $[0,1]^{d}$. Let $C$ be a set (of
colors) and $\chi\colon[-\frac{1}{2},\frac{1}{2}]^{d}\to C$ be an SLKKM
coloring of the unit cube $[-\frac{1}{2},\frac{1}{2}]^{d}$. Let
$C^{\prime}=\operatorname{range}(\chi)$ so that we know every color in
$C^{\prime}$ appears for some point in the cube.

We first deal with the case where $C^{\prime}$ has infinite cardinality777 If
one accepts the axiom of choice, then we don’t need to deal with this as a
special case, but by doing so, we can avoid requiring the axiom of choice in
the proof. . If $C^{\prime}$ has infinite cardinality, then because we can
cover the cube with finitely many $\varepsilon$-balls, one of these balls must
contain points of infinitely many colors, so the result is true. Thus, we
assume from now on that $C^{\prime}$ has finite cardinality.

For each color $c\in C^{\prime}$ we will let $X_{c}$ denote the set of points
assigned color $c$ by $\chi$—that is, $X_{c}=\chi^{-1}(c)$. Note that the
hypothesis that no color includes points of opposite faces formally means that
that for every color $c\in C^{\prime}$, the set $X_{c}$ has the property that
for each coordinate $i\in[d]$, the projection
$\pi_{i}(X_{c})=\\{x_{i}:\vec{x}\in X_{c}\\}$ does not contain both
$-\frac{1}{2}$ and $\frac{1}{2}$.

The first step in the proof is to extend the coloring $\chi$ to the larger
cube $[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ in a natural
way. Consider the following function $f$ which truncates points in the larger
interval to be in the smaller interval:

$\displaystyle
f\colon[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]\to[-\tfrac{1}{2},\tfrac{1}{2}]$
$\displaystyle
f(y)\operatorname{\overset{def}{=}}\begin{cases}-\frac{1}{2}&y\leq-\frac{1}{2}\\\
y&y\in(-\frac{1}{2},\frac{1}{2})\\\ \frac{1}{2}&y\geq\frac{1}{2}\end{cases}$

Let
$\vec{f}\colon[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}\to[-\tfrac{1}{2},\tfrac{1}{2}]^{d}$
be the function which is $f$ in each coordinate:
$\vec{f}(\vec{y})\operatorname{\overset{def}{=}}\langle
f(y_{i})\rangle_{i=1}^{d}$.

Now extend the coloring $\chi$ to the coloring
$\gamma\colon[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}\to
C^{\prime}$ defined by

$\gamma(\vec{x})\operatorname{\overset{def}{=}}\chi\big{(}\vec{f}\left(\vec{x}\right)\big{)}.$

For each color $c\in C^{\prime}$, let $Y_{c}=\gamma^{-1}(c)$ denote the points
assigned color $c$ by $\gamma$ and note that $X_{c}\subseteq Y_{c}$.
Consistent with this notation, we will typically refer to a point in the unit
cube as $\vec{x}$ and a point in the extended cube as $\vec{y}$.

We make the following claim which implies that for each color $c\in
C^{\prime}$, the set $Y_{c}$ of points of that color in the extended coloring
are contained in a set bounded away from one side of the extended cube
$[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ in each coordinate.

######  Claim A.

For each color $c\in C^{\prime}$ there exists an orientation
$\vec{v}\in\\{-1,1\\}^{d}$ such that
$Y_{c}\subseteq\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]$.

###### Proof of Claim.

Fix an arbitrary coordinate $i\in[d]$. Note that for every $\vec{y}\in Y_{c}$
we have $\vec{f}(\vec{y})\in X_{c}$ which is to say that the $\vec{y}$ has the
same color in the extended coloring as $f(\vec{y})$ does in the original
coloring (see justification888 For every $\vec{y}\in Y_{c}$ we have (by
definition of $Y_{c}$) that $\gamma(\vec{y})=c$ and (by definition of
$\gamma$) that $\gamma(\vec{y})=\chi(\vec{f}(\vec{y}))$ showing that
$\chi(f(\vec{y}))=c$ and thus (by definition of $X_{c}$) that $f(\vec{y})\in
X_{c}$. ).

Note that if there is some $\vec{y}\in Y_{c}$ with $y_{i}\leq-\frac{1}{2}$,
then $f(y_{i})=-\frac{1}{2}$ so the fact that $X_{c}\ni\vec{f}(\vec{y})$
implies that $\pi_{i}(X_{c})\ni f(y_{i})=-\frac{1}{2}$. Similarly, if there is
some $\vec{y}\in Y_{c}$ with $y_{i}\geq\frac{1}{2}$, then
$\pi_{i}(X_{c})\ni\frac{1}{2}$. Recall that by hypothesis, $\pi_{i}(X_{c})$
does not contain both $-\frac{1}{2}$ and $\frac{1}{2}$ which means it is
either the case that for all $\vec{y}\in Y_{c}$ we have $y_{i}>-\frac{1}{2}$
(so $\pi_{i}(Y_{c})\subseteq(-\frac{1}{2},\frac{1}{2}+\varepsilon]$) or it is
the case that for all $\vec{y}\in Y_{c}$ we have $y_{i}<\frac{1}{2}$ (so
$\pi_{i}(Y_{c})\subseteq[-\frac{1}{2}-\varepsilon,\frac{1}{2})$).

Thus we can choose $v_{i}\in\\{-1,1\\}$ such that $\pi_{i}(Y_{c})\subseteq
v_{i}\cdot(-\frac{1}{2},\frac{1}{2}+\varepsilon]$. Since this is true for each
coordinate $i\in[d]$ we can select $\vec{v}\in\\{-1,1\\}^{d}$ such that

$Y_{c}\subseteq\prod_{i=1}^{d}\pi_{i}(Y_{c})\subseteq\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]$

as claimed. ∎

For an orientation $\vec{v}\in\\{-1,1\\}^{d}$, let $B_{\vec{c}}$ denote the
set
$B_{\vec{v}}\operatorname{\overset{def}{=}}\prod_{i=1}^{d}-v_{i}\cdot(0,\varepsilon)$
which should be interpreted as a on open orthant of the $\ell_{\infty}$
$\varepsilon$-ball centered at the origin—specifically the orthant opposite
the orientation $\vec{v}$. Building on kkm-lebesgue-variant-subclaim-1, we get
the following:

######  Claim B.

For each color $c\in C^{\prime}$, there exists an orientation
$\vec{v}\in\\{-1,1\\}^{d}$ such that
$Y_{c}+B_{\vec{v}}\subseteq[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}$.

###### Proof of Claim.

Let $\vec{v}$ be an orientation given in kkm-lebesgue-variant-subclaim-1 for
color $c$. We get the following chain of containments:

$\displaystyle Y_{c}+B_{\vec{v}}$
$\displaystyle=Y_{c}+\left(\prod_{i=1}^{d}-v_{i}\cdot(0,\varepsilon)\right)$
(Def’n of $B_{\vec{v}}$)
$\displaystyle\subseteq\left(\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]\right)+\left(\prod_{i=1}^{d}-v_{i}\cdot(0,\varepsilon)\right)$
(kkm-lebesgue-variant-subclaim-1)
$\displaystyle=\left(\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]\right)+\left(\prod_{i=1}^{d}v_{i}\cdot(-\varepsilon,0)\right)$
(Factor a negative)
$\displaystyle=\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon)$
(Minkowski sum of rectangles)
$\displaystyle\subseteq[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}.$
($v_{i}\in\\{-1,1\\}$)

This proves the claim. ∎

We also claim that $Y_{c}+B_{\vec{v}}$ has substantial measure.

######  Claim C.

For each color $c\in C^{\prime}$ and any orientation
$\vec{v}\in\\{-1,1\\}^{d}$, the set $Y_{c}+B_{\vec{v}}$ is Borel measurable
and $m(Y_{c}+B_{\vec{v}})\geq
m_{out}(Y_{c})\cdot\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}$.

###### Proof of Claim.

Let $M=(1+\varepsilon)^{d}$ which is the measure of
$\prod_{i=1}^{d}v_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]$, and
because by kkm-lebesgue-variant-subclaim-1, $Y_{c}$ is a subset of some such
set, we have $m_{out}(Y_{c})\leq M$.

We have that $Y_{c}+B_{\vec{v}}$ is Borel measurable and that
$m\left(Y_{c}+B_{\vec{v}}\right)\geq\left(m_{out}(Y_{c})^{\frac{1}{d}}+\varepsilon\right)^{d}$
by outer-measure-brunn-minkowsi-bound-l-infty (because $B_{\vec{v}}$ is some
translation of $B^{\circ}_{\infty}(\frac{\varepsilon}{2},\vec{0})$ and
translations are irrelevant to the measure concerns of outer-measure-brunn-
minkowsi-bound-l-infty). Thus, we have the following chain of inequalities:

$\displaystyle m(Y_{c}+B_{\vec{v}})$
$\displaystyle\geq\left(m_{out}(Y_{c})^{1/d}+\varepsilon\right)^{d}$ (Above)
$\displaystyle=M\cdot\left(\frac{m_{out}(Y_{c})^{1/d}}{M^{1/d}}+\frac{\varepsilon}{M^{1/d}}\right)^{d}$
(Factor out $M$) $\displaystyle\geq
M\cdot\left(\frac{m_{out}(Y_{c})}{M}\right)\cdot\left(1+\frac{\varepsilon}{M^{1/d}}\right)^{d}$
(brunn-minkowski-bound-lemma)
$\displaystyle=m_{out}(Y_{c})\cdot\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}$
(Simplify and use $M=(1+\varepsilon)^{d}$)

∎

Now, consider the indexed family $\mathcal{A}=\\{Y_{c}+B_{\vec{v}(c)}\\}_{c\in
C^{\prime}}$ (where $\vec{v}(c)$ is an orientation for $c$ as in kkm-lebesgue-
variant-subclaim-1 and subclaim-2) noting that this family has finite
cardinality because $C^{\prime}$ has finite cardinality. Considering the sum
of measures of sets in $\mathcal{A}$, we have the following:

$\displaystyle\sum_{A\in\mathcal{A}}m(A)$ $\displaystyle=\sum_{c\in
C^{\prime}}m\left(Y_{c}+B_{\vec{v}(c)}\right)$ (Def’n of $\mathcal{A}$;
measurability was shown above)
$\displaystyle\geq\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\cdot\sum_{c\in
C^{\prime}}m_{out}(Y_{c})$ (subclaim-3 and linearity of summation)
$\displaystyle\geq\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\cdot
m_{out}\left(\bigcup_{c\in C^{\prime}}Y_{c}\right)$ (Countable/finite
subaddativity of outer measures)
$\displaystyle=\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\cdot
m_{out}\left([-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}\right)$
(The $Y_{c}$’s partition
$[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}$)
$\displaystyle=\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\cdot(1+2\varepsilon)^{d}$
(Evaluate outer measure)

By subclaim-2, each member of $\mathcal{A}$ is a subset of
$[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$, so by lower-bound-
cover-number-Rd, there exists a point
$\vec{p}\in[-\tfrac{1}{2}-\varepsilon,\tfrac{1}{2}+\varepsilon]^{d}$ that
belongs to at least

$\left\lceil\frac{\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\cdot(1+2\varepsilon)^{d}}{(1+2\varepsilon)^{d}}\right\rceil=\left\lceil\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\right\rceil$

sets in $\mathcal{A}$. That is, $\vec{p}$ belongs to $Y_{c}+B_{\vec{v}(c)}$
for at least
$\left\lceil\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\right\rceil$
colors $c\in C^{\prime}$. For each such color $c$, it follows that
$\vec{p}+(-\varepsilon,\varepsilon)^{d}$ intersects $Y_{c}$ (see
justification999 If $\vec{p}\in Y_{c}+B_{\vec{v}(c)}\subseteq
Y_{c}+(-\varepsilon,\varepsilon)^{d}$, then by definition of Minkowski sum
there exists $\vec{y}\in Y_{c}$ and $\vec{b}\in(-\varepsilon,\varepsilon)^{d}$
such that $\vec{p}=\vec{y}+\vec{b}$ so $Y_{c}\ni\vec{y}=\vec{p}-\vec{b}$ and
also $\vec{p}-\vec{b}\in\vec{p}+(-\varepsilon,\varepsilon)^{d}$ demonstrating
that these two sets contain a common point. ). Note that
$\vec{p}+(-\varepsilon,\varepsilon)^{d}=B^{\circ}_{\infty}(\varepsilon,\vec{p})$
showing that $B^{\circ}_{\infty}(\varepsilon,\vec{p})$ contains points of at
least
$\left\lceil\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\right\rceil$
colors (according to the coloring of $\gamma$ since we are discussing sets
$Y_{c}$).

What we really want, though, is a point in the unit cube that has this
property rather than a point in the extended cube, and we want it with respect
to the original coloring $\chi$ rather than the extended coloring $\gamma$. We
will show that the point $\vec{f}\left(\vec{p}\right)$ suffices.

######  Claim D.

If $c\in C^{\prime}$ is a color for which
$B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap Y_{c}\not=\emptyset$, then also
$B^{\circ}_{\infty}(\varepsilon,\vec{f}\left(\vec{p}\right))\cap
X_{c}\not=\emptyset$.

###### Proof of Claim.

Let $\vec{y}\in B^{\circ}_{\infty}(\varepsilon,\vec{p})\cap Y_{\vec{c}}$. Then
because $\vec{y}\in B^{\circ}_{\infty}(\varepsilon,\vec{p})$, we have
$\left\lVert\vec{y}-\vec{p}\right\rVert_{\infty}<\varepsilon$, so for each
coordinate $i\in[d]$ we have $\left\lvert
y_{i}-p_{i}\right\rvert<\varepsilon$. It is easy to analyze the $9$ cases (or
$3$ by symmetries) arising in the definition of $f$ to see that this implies
$\left\lvert f(y_{i})-f(p_{i})\right\rvert<\varepsilon$ as well (i.e. $f$ maps
pairs of values in its domain so that they are no farther apart), thus
$\left\lVert\vec{f}\left(\vec{y}\right)-\vec{f}\left(\vec{p}\right)\right\rVert_{\infty}<\varepsilon$
and thus $\vec{f}\left(\vec{y}\right)\in
B^{\circ}_{\infty}(\varepsilon,\vec{f}\left(\vec{p}\right))$.

Also, as justified in a prior footnote8, for any $\vec{y}\in Y_{c}$ we have
$\vec{f}(\vec{y})\in X_{c}$ so that $\vec{f}\left(\vec{y}\right)\in
B^{\circ}_{\infty}(\varepsilon,\vec{f}\left(\vec{p}\right))\cap X_{c}$ which
shows that the intersection is non-empty. ∎

Thus, because $B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects $Y_{c}$ for
at least
$\left\lceil\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\right\rceil$
choices of color $c\in C^{\prime}$, by kkm-lebesgue-variant-subclaim-4
$\vec{f}\left(\vec{p}\right)$ is a point in the unit cube for which
$B^{\circ}_{\infty}(\varepsilon,\vec{f}\left(\vec{p}\right))$ intersects
$X_{c}$ for at least
$\left\lceil\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\right\rceil$
different colors $c\in C^{\prime}$. That is, this ball contains points from at
least this many of the original color sets.

The final step in the proof of the theorem is to clean up the expression with
an inequality. Note that $C^{\prime}$ must contain of at least $2^{d}$ colors
because each of the $2^{d}$ corners of the unit cube must be assigned a unique
color since any pair of corners belong to an opposite pair of faces on the
cube. For this reason it is trivial that for $\varepsilon>\frac{1}{2}$ there
is a point $\vec{p}$ such that $B^{\circ}_{\infty}(\varepsilon,\vec{p})$
intersects at least $2^{d}$ colors: just let $\vec{p}$ be the midpoint of the
unit cube. Thus, the only interesting case is $\varepsilon\in(0,\frac{1}{2}]$,
and for such $\varepsilon$ we have $1+\varepsilon\leq\frac{3}{2}$ and thus
$\frac{\varepsilon}{1+\varepsilon}\geq\frac{2}{3}\varepsilon$ showing that
$\left(1+\frac{\varepsilon}{1+\varepsilon}\right)^{d}\geq(1+\frac{2}{3}\varepsilon)^{d}$
which completes the proof.

∎

##  3 Proof of the  (Neighborhood Sperner Lemma).

Now we restate and prove the  (Neighborhood Sperner Lemma).. Basically, we
assign each point of $[0,1]^{d}$ to a color of a point in $\Lambda$ nearby in
a careful way and show that the resulting coloring still doesn’t use the same
color on opposite faces. We then use the  (Neighborhood KKM-Lebesgue Theorem).
to find the point $\vec{p}$ and pass back the result because $\Lambda$
approximates $[0,1]^{d}$. Part of the proof is illustrated in fig:proof-of-
sperner-variant.

(a) A $\rho$-proximate set $\Lambda$ with $\rho=\frac{1}{6}$

(b) Coloring $\chi:\Lambda\to\\{R,B,P,Y\\}$

(c) Sperner/KKM $\gamma:[0,1]^{2}\to\\{0,1\\}^{2}$

(d) $\gamma$ emphasized

Figure 2:  2(a) shows a set $\Lambda\subseteq[0,1]^{2}$ which is
$\rho$-proximate for $\rho=\frac{1}{6}$ (i.e. every vertex is displayed, every
point of each edge is within distance $\frac{1}{6}$ of some displayed point on
the same edge, and every point in the interior is within distance
$\frac{1}{6}$ of some displayed point). The distance $\rho$ is shown visually
in the upper left. 2(b) shows an SLKKM coloring of $\Lambda$ (i.e. a function
$\chi:\Lambda\to C=\\{R_{ed},B_{lue},P_{urple},Y_{ellow}\\}$ in which no color
is used on opposite faces). 2(c) shows how this coloring is used to produce a
coloring of $[0,1]^{2}$ (i.e. a function $\gamma:[0,1]^{d}\to\\{0,1\\}^{2}$):
an order is put on the set of colors $C$ (in this case
$R_{ed},B_{lue},P_{urple},Y_{ellow}$ as shown at the top of 2(c)) and each
point $\vec{x}$ of the cube is mapped to the first color in the ordering for
which there is a point $\vec{y}\in\Lambda$ of this color that is (1) within
distance $\rho$ of $\vec{x}$, and (2) is in the smallest face containing
$\vec{x}$. For example, if $\vec{x}$ is on an edge, then the only points
$\vec{y}$ considered are points in $\Lambda$ on the same edge which are
distance at most $\rho$ away. 2(d) clarifies the coloring $\gamma$ by
emphasizing the colors on the vertices, the edges, and the boundaries between
colors.

See 1.12

###### Proof.

Let $C$ be a set and $\chi:\Lambda\to C$ denote the coloring of $\Lambda$, and
let $C^{\prime}=\operatorname{range}(\chi)$.

We first deal with the case where $C^{\prime}$ has infinite cardinality101010
If one accepts the axiom of choice, then we don’t need to deal with this as a
special case, but by doing so, we can avoid requiring the axiom of choice in
the proof. . If $C^{\prime}$ has infinite cardinality, then because we can
cover the cube (and thus $\Lambda$) with finitely many $\varepsilon$-balls,
one of these balls must contain points of infinitely many colors, so the
result is true. Thus, we assume from now on that $C^{\prime}$ has finite
cardinality.

The next step in the proof is the following observation.

######  Claim A.

If $\rho\geq\frac{1}{2}$ then the fact that $\Lambda$ is $\rho$-proximate
implies that $\Lambda$ is $\frac{1}{2}$-proximate.

###### Proof of Claim.

For any face $F$ of the cube, we have $F=\prod_{i=1}^{d}F_{i}$ where each
$F_{i}$ is $\\{0\\}$, $\\{1\\}$, or $[0,1]$. This means that any $\vec{x}\in
F$, we can find a vertex $\vec{v}$ of the cube (a point where each coordinate
$v_{i}$ is $0$ or $1$) which also belongs to $F$ such that in each coordinate
we have $\left\lvert x_{i}-v_{i}\right\rvert\leq\frac{1}{2}$. Since $\vec{v}$
is a vertex, by vertices-in-proximate-set-remark, we have $\vec{v}\in\Lambda$.
Thus, $\vec{v}\in F\cap\Lambda$ and
$\left\lVert\vec{x}-\vec{v}\right\rVert_{\infty}\leq\frac{1}{2}$. ∎

Thus, we may continue knowing that $\Lambda$ is not only $\rho$-proximate but
in fact $\rho^{\prime}$-proximate where
$\rho^{\prime}=\min(\rho,\frac{1}{2})$. Next we comment on what happens if the
term $(\varepsilon-\rho^{\prime})$ is non-positive. Essentially, we have to
take show that the expressions
$(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})$ and
$(1+\frac{2}{3}(\varepsilon-\rho^{\prime}))$ are never large negative values
to make sure the bound we are giving does not take on large positive values
when $d$ is even.

######  Claim B.

The stated result holds when $\varepsilon\leq\rho^{\prime}$.

###### Proof of Claim.

Note that when $\varepsilon\leq\rho^{\prime}$, then because
$\rho^{\prime}\in[0,\frac{1}{2}]$ this implies
$\varepsilon\in(0,\frac{1}{2}]$, so
$(\varepsilon-\rho^{\prime})\in(-\frac{1}{2},0]$. On the interval
$x\in(-\frac{1}{2},0]$, the expression $1+\frac{1}{1+x}$ is in $(0,1]$, so we
have
$1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})}\in(0,1]$
and thus
$(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})^{d}\in(0,1]$,
so
$\left\lceil(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})^{d}\right\rceil=1$.
Similarly, because $(\varepsilon-\rho^{\prime})\in(-\frac{1}{2},0]$, we have
$\frac{2}{3}(\varepsilon-\rho^{\prime})\in(-\frac{1}{3},0]$, so
$1+\frac{2}{3}(\varepsilon-\rho^{\prime})\in(\frac{2}{3},1]$, so
$(1+\frac{2}{3}(\varepsilon-\rho^{\prime}))^{d}\in(0,1]$, and again
$\left\lceil(1+\frac{2}{3}(\varepsilon-\rho^{\prime}))^{d}\right\rceil=1$.
Because $\Lambda$ is non-empty (by vertices-in-proximate-set-remark) it is
trivial to find a point where the $\varepsilon$ ball contains points of at
least $1$ color showing that the result is true when
$\varepsilon\leq\rho^{\prime}$. ∎

Thus, we assume from now on that $\varepsilon>\rho^{\prime}$ which implies
$(\varepsilon-\rho^{\prime})\in(0,\infty)$ (the hypothesis we need on the ball
radius to apply the  (Neighborhood KKM-Lebesgue Theorem).).

Next, for each $\vec{x}\in[0,1]^{d}$, let $F^{(\vec{x})}$ denote the smallest
face containing $\vec{x}$ (i.e. the intersection of all faces containing
$\vec{x}$) and let $C^{(\vec{x})}$ denote the set of colors present in the
face $F^{(\vec{x})}$ and within $\rho^{\prime}$ of $\vec{x}$ (formally,
$C^{(\vec{x})}=\\{\chi(\vec{y}):\vec{y}\in
F^{(\vec{x})}\cap\Lambda\cap\overline{B}_{\infty}(\rho^{\prime},\vec{x})\\}$)
noting that $C^{(\vec{x})}$ is non-empty by proximate-rephrasing-remark.

Let $\gamma:[0,1]^{d}\to C^{\prime}\subseteq C$ map each $\vec{x}$ to
some111111 Because $C^{\prime}$ has finite cardinality, this does not require
the axiom of choice.  color in $C^{(\vec{x})}$. We claim that $\gamma$ is an
SLKKM coloring so that we will be able to apply the  (Neighborhood KKM-
Lebesgue Theorem). to $\gamma$.

######  Claim C.

The coloring $\gamma$ is does not assign the same color to points on opposite
faces.

###### Proof of Claim.

We show that points on opposite faces are assigned different colors by
$\gamma$. Let $F^{(0)}$ and $F^{(1)}$ be opposite faces of the cube—that is,
there is some coordinate $j$ such that $\pi_{j}(F^{(0)})=\\{0\\}$ and
$\pi_{j}(F^{(1)})=\\{1\\}$.

Let $\vec{x}^{(0)}\in F^{(0)}$ be arbitrary. Because $F^{(\vec{x}^{(0)})}$ is
the intersection of all faces containing $\vec{x}$, we have $\vec{x}^{(0)}\in
F^{(\vec{x}^{(0)})}\subseteq F^{(0)}$. By definition of $\gamma$, there is
some $\vec{y}^{(0)}\in F^{(\vec{x}^{(0)})}\cap\Lambda\subseteq
F^{(0)}\cap\Lambda$ such that $\gamma(\vec{x}^{(0)})=\chi(\vec{y}^{(0)})$.
Similarly, there is some $\vec{y}^{(1)}\in F^{(1)}\cap\Lambda$ such that
$\gamma(\vec{x}^{(1)})=\chi(\vec{y}^{(1)})$.

By hypothesis of the coloring $\chi$, because $\vec{y}^{(0)}$ and
$\vec{y}^{(1)}$ belong to opposite faces of the cube (i.e. $F^{(0)}$ and
$F^{(1)}$), we have $\chi(\vec{y}^{(0)})\not=\chi(\vec{y}^{(0)})$ showing that
$\gamma(\vec{x}^{(0)})\not=\gamma(\vec{x}^{(1)})$. ∎

The following claim says that for any point $\vec{p}$, all of the colors (of
$\gamma$) appearing in the $(\varepsilon-\rho^{\prime})$ ball at $\vec{p}$
also appear (as colors of $\chi$) in $\Lambda$ within the $\varepsilon$ ball
at $\vec{p}$. The connection back to $\Lambda$ below is because for any $c\in
C^{\prime}$, we have $\chi^{-1}(c)\subseteq\Lambda$.

######  Claim D.

The following subset containment holds for each point $\vec{p}\in[0,1]^{d}$
(see comment121212 In the former set we express
$c\in\operatorname{range}(\gamma)$ rather than $c\in C^{\prime}$, because it
is possible that $\operatorname{range}(\gamma)\subsetneq C^{\prime}$. The
coloring $\gamma$ was defined as one of many choices, and in the natural
choices we would have $\gamma(\vec{y})=\chi(\vec{y})$ for each
$\vec{y}\in\Lambda$, but we did not require this, so $\gamma$ is not
necessarily an extension of $\chi$, and it is possible that it does not
surject onto $C^{\prime}$. ):

$\\{c\in\operatorname{range}(\gamma):\gamma^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon-\rho^{\prime},\vec{p})\not=\emptyset\\}\quad\subseteq\quad\\{c\in\operatorname{range}(\chi)=C^{\prime}:\chi^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon,\vec{p})\not=\emptyset\\}$

###### Proof of Claim.

If $c$ belongs to the left set, then $\gamma^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon-\rho^{\prime},\vec{p})\not=\emptyset$, so let
$\vec{x}\in\gamma^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon-\rho^{\prime},\vec{p})$. Then
$\gamma(\vec{x})=c$ and using the defining property of $\gamma$ that
$\gamma(\vec{x})\in C^{(\vec{x})}$, we have the following:

$c=\gamma(\vec{x})\in C^{(\vec{x})}=\\{\chi(\vec{y}):\vec{y}\in
F^{(\vec{x})}\cap\Lambda\cap\overline{B}_{\infty}(\rho^{\prime},\vec{x})\\}.$

This means that there is some
$\vec{y}\in\Lambda\cap\overline{B}_{\infty}(\rho^{\prime},\vec{x})$ such that
$\chi(\vec{y})=c$ (i.e. $\vec{y}\in\chi^{-1}(c)$). Also, for this $\vec{y}$,
because $\left\lVert\vec{y}-\vec{x}\right\rVert_{\infty}\leq\rho^{\prime}$ and
$\left\lVert\vec{x}-\vec{p}\right\rVert_{\infty}<\varepsilon-\rho^{\prime}$ we
have by the triangle inequality that $\vec{y}\in
B^{\circ}_{\infty}(\varepsilon,\vec{p})$. Thus, $\vec{y}$ demonstrates that
$\chi^{-1}(c)\cap B^{\circ}_{\infty}(\varepsilon,\vec{p})$ is non-empty which
shows that $c$ belongs to the right set. ∎

Now we can finish off the proof. By the  (Neighborhood KKM-Lebesgue Theorem).
(using the fact that $(\varepsilon-\rho^{\prime})\in(0,\infty)$ along with
sperner-variant-subclaim-non-spanning-coloring), there exists
$\vec{p}\in[0,1]^{d}$ such that
$B^{\circ}_{\infty}(\varepsilon-\rho^{\prime},\vec{p})$ intersects at least
$\left\lceil(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})^{d}\right\rceil$
colors (formally, $\\{c\in\operatorname{range}(\gamma):\gamma^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon-\rho^{\prime},\vec{p})\not=\emptyset\\}$ has
cardinality at least
$\left\lceil(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})^{d}\right\rceil$).
Thus, by sperner-variant-subclaim-containment the set
$\\{c\in\operatorname{range}(\chi)=C^{\prime}:\chi^{-1}(c)\cap
B^{\circ}_{\infty}(\varepsilon,\vec{p})\not=\emptyset\\}$ also has cardinality
at least
$\left\lceil(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})})^{d}\right\rceil$
which is what we set out to prove. (Informally, this latter set is the colors
$c$ for which there is a point in $\Lambda\cap
B^{\circ}_{\infty}(\varepsilon,\vec{p})$ that is mapped to $c$ by the original
coloring $\chi$.)

Finally, if $\varepsilon\in(0,\frac{1}{2}]$, then because we have at this
point that $\varepsilon>\rho^{\prime}$, we in fact have
$\varepsilon-\rho^{\prime}\in(0,\frac{1}{2}]$. Thus, by the same inequalities
used in the proof of the  (Neighborhood KKM-Lebesgue Theorem)., we have
$\left\lceil\left(1+\frac{(\varepsilon-\rho^{\prime})}{1+(\varepsilon-\rho^{\prime})}\right)^{d}\right\rceil\geq\left\lceil(1+\tfrac{2}{3}(\varepsilon-\rho^{\prime}))^{d}\right\rceil$
which completes the proof. ∎

##  4 Discussion

In this section, we will give some discussion of the bound that we achieved in
the  (Neighborhood KKM-Lebesgue Theorem). (and equivalently in the
(Neighborhood Sperner Lemma).) including some limitations on improving that
bound and some desires for future improvements of our result. We begin by
defining the best possible function we could use to replace the expression
“$\left\lceil(1+\frac{\varepsilon}{1+\varepsilon})^{d}\right\rceil$” in the
statement of the  (Neighborhood KKM-Lebesgue Theorem).. Let
$K^{\circ}:\mathbb{N}\times(0,\infty)\to\mathbb{N}$ be defined by

$K^{\circ}(d,\varepsilon)\operatorname{\overset{def}{=}}\max\Bigg{\\{}\kappa\in\mathbb{N}:\;\;\parbox{180.67499pt}{for
every SLKKM coloring of $[0,1]^{d}$, there exists a point
$\vec{p}\in[0,1]^{d}$ such that $B^{\circ}_{\infty}(\varepsilon,\vec{p})$
intersects at least $\kappa$ colors}\Bigg{\\}}$

and define the function $\overline{K}$ similarly but using closed balls
instead of open balls.

A few comments are in order. First, this maximum is well defined because there
exist SLKKM colorings of $[0,1]^{d}$ using $2^{d}$ colors (e.g. color each of
the $2^{d}$ orthants of the cube a unique color dealing with boundaries
between colors arbitrarily) and so the set that the maximum is being taken
over is necessarily a subset of $[2^{d}]$ and thus has a maximum. Second, it
is trivially the case for all $d\in\mathbb{N}$ and $\varepsilon\in(0,\infty)$
that $\overline{K}(d,\varepsilon)\geq K^{\circ}(d,\varepsilon)$ because the
closed $\varepsilon$-ball is a superset of the open $\varepsilon$-ball. Third,
by the same superset reasoning we also know that for each fixed
$d\in\mathbb{N}$, both functions $K^{\circ}$ and $\overline{K}$ are non-
decreasing in $\varepsilon$ (we will refer to both of these properties as
monotonicity throughout the discussion). We can say much more about
$K^{\circ}$ and $\overline{K}$, and the information from the discussion that
follows is summarized in tab:K-bounds.

#### Immediate lower bound:

The first obvious thing we can say is that for all $d\in\mathbb{N}$ and
$\varepsilon\in(0,\infty)$, we know that $K^{\circ}(d,\varepsilon)\geq d+1$
(ditto for $\overline{K}$) which follows straightforwardly from the  (KKM-
Lebesgue Theorem). taking care with the infinite cardinality131313 One can
“collapse” the possibly infinitely many colors into just $2^{d}$ colors to
obtain a new finite SLKKM coloring, and by the  (Neighborhood KKM-Lebesgue
Theorem)., there is a point at the closure of at least $d+1$ of the collapsed
colors, and any open set around this point intersects at least $d+1$ of the
original color sets. See kkm-implies-kkm-lebesgue for example, where this
result shows up as part of the larger proof. . This is a better bound for
small $\varepsilon$ (relative to $d$) than our bound in the  (Neighborhood
KKM-Lebesgue Theorem). because $\lim_{\varepsilon\to
0}\left\lceil(1+\frac{\varepsilon}{1+\varepsilon})^{d}\right\rceil=1<d+1$, so
for sufficiently small $\varepsilon$ it holds that
$\left\lceil(1+\frac{\varepsilon}{1+\varepsilon})^{d}\right\rceil\leq d+1$.

#### Trivial tight bound for large $\boldsymbol{\varepsilon}$:

The second obvious thing we can say is that for any $d\in\mathbb{N}$ and
$\varepsilon>\frac{1}{2}$, we have $K^{\circ}(d,\varepsilon)=2^{d}$. This is
because the open $\ell_{\infty}$ $\varepsilon$-ball placed at the center of
the unit $d$-cube is a superset of the cube itself, so it intersects all
$2^{d}$ corners—no two of which have the same color in an SLKKM coloring—so
$K^{\circ}(d,\varepsilon)\geq 2^{d}$. And (by definition)
$K^{\circ}(d,\varepsilon)\leq 2^{d}$ because there are SLKKM colorings with
only $2^{d}$ colors. Similarly, for any $d\in\mathbb{N}$ and
$\varepsilon\geq\frac{1}{2}$ (note the non-strict inequality this time), we
have $\overline{K}(d,\varepsilon)=2^{d}$.

#### Perspective of this paper:

The third thing that we can say is that for all $d\in\mathbb{N}$ and
$\varepsilon\in(0,\infty)$ we have $\overline{K}(d,\varepsilon)\geq
K^{\circ}(d,\varepsilon)\geq\left\lceil(1+\tfrac{\varepsilon}{1+\varepsilon})^{d}\right\rceil$
by the  (Neighborhood KKM-Lebesgue Theorem).. In other words, the purpose of
this paper is to put some lower bound on $K^{\circ}$ (and consequently on
$\overline{K}$).

#### Non-trivial tight bound for small $\boldsymbol{\varepsilon}$:

The fourth thing we can say is something that we don’t believe is at all
obvious; it turns out that we know the value of $K^{\circ}$ (and
$\overline{K}$) exactly for all dimensions for a specific small regime of
$\varepsilon$ near $0$. Specifically, for any $d\in\mathbb{N}$ and
$\varepsilon\in(0,\frac{1}{2d}]$, we know that
$d+1\geq\overline{K}(d,\varepsilon)\geq K^{\circ}(d,\varepsilon)$; along with
the “first obvious thing” we said, this gives equality with $d+1$. The reason
for this is the following. We demonstrated in [9, Theorem 7.20] that in each
dimension $d$, there is a partition $\mathcal{P}_{d}$ of $\mathbb{R}^{d}$
consisting of translates of the half-open cube $[0,1)^{d}$ with the property
that for every point $\vec{p}\in\mathbb{R}^{d}$, the closed ball
$\overline{B}_{\infty}(\frac{1}{2d},\vec{p})$ intersects at most $d+1$ cubes
in the partition (we called such partitions $(d+1,\frac{1}{2d})$-secluded
partitions). This immediately gives an SLKKM coloring of $[0,1]^{d}$ with the
same property: define the coloring $\chi:[0,1]^{d}\to\mathcal{P}_{d}$ by
mapping each point in $[0,1]^{d}$ to the unique member of $\mathcal{P}_{d}$
which it belongs to. This is an SLKKM coloring because no member of
$\mathcal{P}_{d}$ contains points $\ell_{\infty}$ distance $1$ apart, and so
no points distance $1$ apart are given the same color (i.e. no points on
opposite faces are given the same color). In fact, this coloring uses exactly
$2^{d}$ colors141414 The range of $\chi$ can be shown to have cardinality
exactly $2^{d}$. This is because for any $X\in\mathcal{P}_{d}$ which
intersects $[0,1]^{d}$, it follows by simple analysis that because $X$ is a
translate of $[0,1)^{d}$, it must be that $X$ contains one of the corners of
$[0,1]^{d}$. And since no member of $\mathcal{P}_{d}$ contains two corners of
$[0,1]^{d}$ (because any two corners of $[0,1]^{d}$ are $\ell_{\infty}$
distance $1$ apart, and no two points in a translate of $[0,1)^{d}$ are
distance $1$ apart), the subset of members of $\mathcal{P}_{d}$ which
intersect $[0,1]^{d}$ (i.e. the range of $\chi$) are in bijection with the
$2^{d}$ corners of $[0,1]^{d}$.  and consists of color sets which are
rectangles151515 For each color, the set of points in $[0,1]^{d}$ of that
color is $[0,1]^{d}$ intersected with some translate of $[0,1)^{d}$, and this
intersection of a product of intervals is itself a product of intervals (i.e.
a $d$-dimensional rectangle). . This demonstrates the existence of (finite)
SLKKM colorings for which no closed $\ell_{\infty}$ $\varepsilon$-ball
intersects more than the $d+1$ colors even when taking $\varepsilon$ as large
as $\varepsilon=\frac{1}{2d}$. Once more for clarity: for any $d\in\mathbb{N}$
and $\varepsilon\in(0,\frac{1}{2d}]$ we have that
$\overline{K}(d,\varepsilon)=K^{\circ}(d,\varepsilon)=d+1$.

#### Non-trivial upper bound:

We can generalize the result above by utilizing our newer unit cube partitions
[10, Theorem 1.9] rather than our initial constructions in [9]. Specifically,
for each $d,n\in\mathbb{N}$ there is a partition $\mathcal{P}_{d,n}$ of
$\mathbb{R}^{d}$ by translates of $[0,1)^{d}$ which is
$\left(\frac{1}{2n},(n+1)^{\left\lceil\frac{d}{n}\right\rceil}\right)$-secluded
(i.e. for every $\vec{p}\in\mathbb{R}^{d}$, the closed ball
$\overline{B}_{\infty}(\frac{1}{2n},\vec{p})$ intersects at most
$(n+1)^{\left\lceil\frac{d}{n}\right\rceil}$-many members of the
partition)161616 In [10, Theorem 1.9], replace “$f(d)$” with “$n$.” . As in
the prior paragraph, this immediately gives rise to an SLKKM coloring of
$[0,1]^{d}$ such that for every $\vec{p}\in[0,1]^{d}$, we have that
$\overline{B}_{\infty}(\frac{1}{2n},\vec{p})$ contains points of at most
$(n+1)^{\left\lceil\frac{d}{n}\right\rceil}$ colors. Thus, (along with
monotonicity) we have for all $d,n\in\mathbb{N}$ and
$\varepsilon\in(0,\frac{1}{2n}]$ that
$K^{\circ}(d,\varepsilon)\leq\overline{K}(d,\varepsilon)\leq(n+1)^{\left\lceil\frac{d}{n}\right\rceil}$.
Taking $n=1$, we recover the trivial upper bound of $2^{d}$ when
$\varepsilon\in(0,\frac{1}{2}]$ (which is tight for $\overline{K}$ at
$\frac{1}{2}$), and taking $n=d$ we recover the upper bound of $d+1$ when
$\varepsilon\in(0,\frac{1}{2d}]$ (which we have already said is tight on this
whole interval).

Since we can freely choose $n$, this gives some non-trivial upper bound on
$\overline{K}$ and $K^{\circ}$ for every choice of $d$ and $\varepsilon$. That
is to say that for given $\varepsilon\in(0,\frac{1}{2}]$ and $d\in\mathbb{N}$,
we take any $n\in\mathbb{N}\cap[1,\frac{1}{2\varepsilon}]$ (in particular we
can take the $n$ in this range which minimizes
$(n+1)^{\left\lceil\frac{d}{n}\right\rceil}$) so that
$\varepsilon\in(0,\frac{1}{2n}]$ and thus by the above
$K^{\circ}(d,\varepsilon)\leq\overline{K}(d,\varepsilon)\leq(n+1)^{\left\lceil\frac{d}{n}\right\rceil}$.
Based on the fact that for any $d\in\mathbb{N}$ this bound is tight at the
extremes $\varepsilon\in(0,\frac{1}{2d}]$ and $\varepsilon=\frac{1}{2}$, we
wonder if this bound is nearly tight everywhere else.

We quickly note that we really only need to consider $n\in[d]$ and not
$n\in\mathbb{N}$ because for $n>d$, we have
$(n+1)^{\left\lceil\frac{d}{n}\right\rceil}>d+1$ so this is a worse upper
bound than $d+1$, but for $\varepsilon\in(0,\frac{1}{2n}]$ (the domain of
$\varepsilon$ for which this bound applies) we already know by the “Non-
trivial tight bound for small $\varepsilon$” paragraph that that
$\varepsilon\in(0,\frac{1}{2n}\subseteq(0,\frac{1}{2d}]$ so
$K^{\circ}(d,\varepsilon)\leq\overline{K}(d,\varepsilon)\leq d+1$. Thus, we
get no new information from this bound when $n>d$. We also emphasize that it
is important for $n$ to be an integer in the above bounds as is necessary in
proving [10, Theorem 1.9].

#### Difference between $\boldsymbol{K^{\circ}}$ and
$\boldsymbol{\overline{K}}$:

The final thing we will say about these functions is that $\overline{K}$ and
$K^{\circ}$ are not in general equal, and in fact they differ noticeably when
$\varepsilon=\frac{1}{2}$. We have already stated that
$\overline{K}(d,\frac{1}{2})=2^{d}$ (in the “Trivial tight bound for large
$\varepsilon$” paragraph), and we will now argue that
$K^{\circ}(d,\frac{1}{2})\leq 2^{d-1}+1$. Consider first $d=2$ along with
fig:hamming-colorings; it is obviously impossible for any positioning of the
open $\ell_{\infty}$ $\frac{1}{2}$-ball to intersect all $2^{d}=4$ colors
because it can’t include both of the colors which are single points as those
points are $\ell_{\infty}$ distance $1$ apart. This idea extends into higher
dimensions by using an SLKKM coloring with $2^{d}$ colors which are identified
with the vertices of the cube. Each of the $2^{d-1}$ colors in $\\{0,1\\}^{d}$
with even hamming weight are used only on the corresponding vertex (e.g. in
fig:hamming-colorings these are $\langle 0,0\rangle$ (purple) and $\langle
1,1\rangle$ (blue)). Every other point on the cube is given a color with odd
hamming weight; this is possible because aside from vertices (which are given
their own color), every other point of the cube belongs to a face which is a
superset of an edge of the cube, and every edge contains both an even and odd
hamming weight vertex (by the standard definition of the $d$-dimensional
hypercube graph) so there is at least $1$ odd hamming weight color which can
be used. This results in a KKM-style cover (but not with closed sets) which is
in fact an SLKKM coloring because each point can be given a color of one of
the vertices on the smallest face to which it belongs, and thus points on
opposite faces are not given the same color because opposite faces are
necessarily disjoint. Such colorings have $2^{d-1}$ colors which are single
points, so even the open $\ell_{\infty}$ $\frac{1}{2}$-ball cannot hit more
than one of them because all of the vertices are distance $1$ apart. Thus, the
$\varepsilon=\frac{1}{2}$-ball can hit at most $2^{d-1}+1$ colors (possibly
all of the odd hamming weight colors and one even hamming weight color), so
$K^{\circ}(d,\frac{1}{2})\leq 2^{d-1}+1$. And similarly, for
$\varepsilon<\frac{1}{2}$ we have $\overline{K}(d,\varepsilon)\leq
K^{\circ}(d,\frac{1}{2})\leq 2^{d-1}+1$.

In light of this, we believe it is interesting to ask for each dimension $d$
what the ranges of the functions $\overline{K}$ and $K^{\circ}$ are (as
functions of $\varepsilon$).

######  Question 4.1.

For each $d\in\mathbb{N}$, what is
$\operatorname{range}(\overline{K}(d,\cdot))$ and
$\operatorname{range}(K^{\circ}(d,\cdot))$? In particular, what are the
cardinalities of these ranges?

We know that the range is trivially a subset of the integers between $d+1$ and
$2^{d}$ as already discussed, but now we see that it is in fact a proper
subset because $K^{\circ}(d,\cdot)$ and $\overline{K}(d,\cdot)$ are monotonic,
so the hamming coloring discussion above shows that neither range includes any
values strictly between $2^{d-1}+1$ and $2^{d}$. We wonder if the functions
$K^{\circ}(d,\cdot)$ and $\overline{K}(d,\cdot)$ are constant along these
$d$-many open intervals:

$\left(0,\frac{1}{2d}\right),\quad\left(\frac{1}{2d},\frac{1}{2(d-1)}\right),\quad\left(\frac{1}{2(d-1)},\frac{1}{2(d-2)}\right),\quad\ldots,\quad\left(\frac{1}{8},\frac{1}{6}\right),\quad\left(\frac{1}{6},\frac{1}{4}\right),\quad\left(\frac{1}{4},\frac{1}{2}\right).$

If so, this might align nicely with the upper bounds that we obtained in the
“Non-trivial upper bound” paragraph using [10, Theorem 1.9] which gave an
separate upper bound on each such interval.

We do at least know that $K^{\circ}(d,\cdot)$ is broken into non-trivial
intervals (i.e. intervals which are not singleton sets) because it is left
continuous (justified as follows). For any SLKKM coloring of $[0,1]^{d}$ and
$\varepsilon\in(0,\infty)$, there is a point $\vec{p}\in[0,1]^{d}$ such that
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ contains points of at least
$K^{\circ}(d,\varepsilon)$ different colors by definition. Pick
$K^{\circ}(d,\varepsilon)$-many points—each of a distinct color that is
included (which is a finite number of points because
$K^{\circ}(d,\varepsilon)\leq 2^{d}$). Because each of these finite number of
points is contained in the open ball
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$, then for each
$\varepsilon^{\prime}<\varepsilon$ sufficiently large, we have that
$B^{\circ}_{\infty}(\varepsilon^{\prime},\vec{p})$ contains all of these
points, and so includes at least $K^{\circ}(d,\varepsilon)\leq 2^{d}$ colors.
Thus,
$\lim_{\varepsilon^{\prime}\uparrow\varepsilon}K^{\circ}(d,\varepsilon^{\prime})\geq
K^{\circ}(d,\varepsilon)$ and we get the other inequality by the monotonicity
of $K^{\circ}$ showing that $K^{\circ}$ is right continuous:

$\lim_{\varepsilon^{\prime}\uparrow\varepsilon}K^{\circ}(d,\varepsilon^{\prime})=K^{\circ}(d,\varepsilon).$

Either by using a similar argument, or by noting that for all
$\varepsilon^{\prime}<\varepsilon$ we have
$K^{\circ}(d,\varepsilon^{\prime})\leq\overline{K}(d,\varepsilon^{\prime})\leq
K^{\circ}(d,\varepsilon)$ we have by a squeeze theorem that also

$\lim_{\varepsilon^{\prime}\uparrow\varepsilon}\overline{K}(d,\varepsilon^{\prime})=K^{\circ}(d,\varepsilon).$

Furthermore, on the interior of any interval
$(\varepsilon_{a},\varepsilon_{b}]$ for which $K^{\circ}(d,\cdot)$ is
constant, we also know that $\overline{K}(d,\cdot)$ is constant because for
$\varepsilon\in(\varepsilon_{a},\varepsilon_{b})$ we have
$B^{\circ}_{\infty}(\varepsilon_{a},\vec{0})\subseteq\overline{B}_{\infty}(\varepsilon,\vec{0})\subseteq
B^{\circ}_{\infty}(\varepsilon_{b},\vec{0})$ so
$K^{\circ}(d,\varepsilon_{a})\leq\overline{K}(d,\varepsilon)\leq
K^{\circ}(d,\varepsilon_{b})$.

$\begin{array}[]{|l|l|l|l|}\hline\cr\varepsilon&K^{\circ}(d,\varepsilon)&\overline{K}(d,\varepsilon)&\text{Reason}\\\
\hline\cr\in(0,\infty)&\leq 2^{d}&\leq 2^{d}&\text{Trivial}\\\
\in(\frac{1}{2},\infty)&=2^{d}&=2^{d}&\text{Trivial}\\\
\hline\cr=\frac{1}{2}&\leq 2^{d-1}+1&=2^{d}&\text{Hamming coloring discussion
(c.f. \Autoref{fig:hamming-colorings})}\\\ \hline\cr\in(0,\infty)&\geq
d+1&\geq d+1&\text{\nameref{kkm-lebesgue}}\\\
\in(0,\infty)&\geq(1+\tfrac{\varepsilon}{1+\varepsilon})^{d}&\geq(1+\tfrac{\varepsilon}{1+\varepsilon})^{d}&\text{\nameref{kkm-
lebesgue-variant}}\\\
\in(0,\frac{1}{2}]&\geq(1+\tfrac{2}{3}\varepsilon)^{d}&\geq(1+\tfrac{2}{3}\varepsilon)^{d}&\text{\nameref{kkm-
lebesgue-variant}}\\\
\hline\cr\in(0,\frac{1}{2d}]&=d+1&=d+1&\text{\cite[cite]{[\@@bibref{}{geometry_of_rounding}{}{},
Theorem~{}7.20]} \& \nameref{kkm-lebesgue}}\\\
\in(0,\frac{1}{2n}],n\in\mathbb{N}&\leq(n+1)^{\left\lceil\frac{d}{n}\right\rceil}&\leq(n+1)^{\left\lceil\frac{d}{n}\right\rceil}&\text{\cite[cite]{[\@@bibref{}{FOCS23_submission}{}{},
Theorem~{}1.9]}}\\\ \hline\cr\end{array}$ Table 1: Known information about the
ideal functions $K^{\circ}$ and $\overline{K}$. Figure 3:  An example of a
coloring in which each even hamming weight vertex has a color only used at
that vertex. It is impossible for an $\varepsilon=\frac{1}{2}$ open
$\ell_{\infty}$ ball to contain more than one of the even hamming weight
colors because all vertices are distance $1$ apart.

#### Bounding the constant in the  (Neighborhood KKM-Lebesgue Theorem).:

A consequence of the “Difference between $K^{\circ}$ and $\overline{K}$”
paragraph is that any improvement to the  (Neighborhood KKM-Lebesgue Theorem).
using a bound of the form $(1+c\varepsilon)^{d}$ for some constant $c$ must
have the property that $(1+c\frac{1}{2})^{d}\leq 2^{d-1}+1$ for all $d$.
Solving for $c$ gives $c\leq 2\left(\left(2^{d-1}+1\right)^{1/d}-1\right)$.
Graphing shows that $d=3$ is the integer where this takes the smallest value
and shows that $c\leq 1.42$. This is not an asymptotic claim; we are only
saying that if we want to replace the constant $\frac{2}{3}$ in the
(Neighborhood KKM-Lebesgue Theorem). with some other constant $c$, it must be
that $c\leq 1.42$. In particular, we cannot hope to obtain the bound of
$(1+2\varepsilon)^{d}$ (a bound which we were able to achieve in [10] for
colorings (i.e. partitions) of $\mathbb{R}^{d}$ in which all color sets (i.e.
partition members) had at most unit outer measure or at most unit diameter).

#### Conclusion:

All of this demonstrates that the lower bound of
$(1+\frac{\varepsilon}{1+\varepsilon})^{d}$ or
$(1+\frac{2}{3}\varepsilon)^{d}$ in our  (Neighborhood KKM-Lebesgue Theorem).
is not in general tight. For $\varepsilon$ tending to $0$, this bound predicts
$1$ even though the exact bound is $d+1$ for all
$\varepsilon\in(0,\frac{1}{2d}]$. Furthermore, our bound in the  (Neighborhood
KKM-Lebesgue Theorem). predicts only slightly more than $(1+\frac{1}{3})^{d}$
for $\varepsilon$ slightly bigger than $\frac{1}{2}$ when the tight bound is
$2^{d}$. For these reasons, we suspect that the lower bound of the
(Neighborhood KKM-Lebesgue Theorem). is not tight for any value of
$\varepsilon$, and we hope that future work is able to establish better lower
bounds on $K^{\circ}(d,\varepsilon)$ and $\overline{K}(d,\varepsilon)$. In
addition, we hope that future work can either improve our upper bounds on
these functions or prove that they are nearly tight.

We believe it would be nice if all of this could be done with a single
technique. For example, as summarized in tab:K-bounds, the current lower
bounds on $K^{\circ}$ and $\overline{K}$ for small $\varepsilon$ follow from
the  (Cubical KKM Lemma). or the  (Lebesgue Covering Theorem). (summarized in
the  (KKM-Lebesgue Theorem).) while the current lower bounds on $K^{\circ}$
and $\overline{K}$ for larger $\varepsilon$ given in this paper use very
different techniques than those traditionally used to prove the  (Cubical KKM
Lemma). and the  (Lebesgue Covering Theorem).. So there are two very different
proof techniques to prove two regimes of the current bounds. It would be
particularly satisfying if there was a single technique giving some “nice”
lower bound expression $k^{\circ}(d,\varepsilon)$ for
$K^{\circ}(d,\varepsilon)$ such that

$k^{\circ}(d,\varepsilon)\geq\max\begin{cases}\left\lceil(1+\frac{\varepsilon}{1+\varepsilon})^{d}\right\rceil\\\\[10.00002pt]
d+1\end{cases}$

so that it supersedes both of the two bounds we have used. This would be nice
because the  (KKM-Lebesgue Theorem). would then follow from this result171717
This would mean that for every $\varepsilon$, there is a point $\vec{p}$ where
$B^{\circ}_{\infty}(\varepsilon,\vec{p})$ intersects at least
$k^{\circ}(d,\varepsilon)\geq d+1$ colors. Consider a sequence
$\langle\varepsilon^{(n)}\rangle_{n=1}^{\infty}$ such that
$\lim_{n\to\infty}\varepsilon^{(n)}=0$, and for each $n$, let
$\vec{p}^{(n)}\in[0,1]^{d}$ be a point such that
$B^{\circ}_{\infty}(\varepsilon^{(n)},\vec{p^{(n)}})$ intersects points of at
least $d+1$ colors. By compactness, we may assume that $\vec{p}^{(n)}$
converges (otherwise we just pick a convergent subsequence). Let $\vec{p}$ be
the point of convergence. Then for any $\delta\in(0,\infty)$, it holds that
$B^{\circ}_{\infty}(\delta,\vec{p})$ intersects at least $d+1$ colors because
there is some $N\in\mathbb{N}$ such that for all $n\geq N$ we have
$\left\lVert\vec{p}-\vec{p}^{(n)}\right\rVert_{\infty}<\frac{\delta}{2}$ and
$\varepsilon^{(n)}<\frac{\delta}{2}$ so
$B^{\circ}_{\infty}(\delta,\vec{p})\supseteq
B^{\circ}_{\infty}(\varepsilon^{(n)},\vec{p}^{(n)})$ which intersects at least
$d+1$ colors. It is left to show that $\vec{p}$ is in fact at the closure of
some set of at least $d+1$ colors, and finiteness is critical for this.
Consider a sequence $\langle\delta^{(n)}\rangle_{n=1}^{\infty}$ converging to
$0$ and the sequence $\langle C^{(n)}\rangle_{n=1}^{\infty}$ where $C_{n}$ is
the set of colors intersected by $B^{\circ}_{\infty}(\delta^{(n)},\vec{p})$.
Because only finitely many colors are used by hypothesis of the  (KKM-Lebesgue
Theorem)., there are at most a finite number of distinct terms in $\langle
C^{(n)}\rangle_{n=1}^{\infty}$ as each term is a subset of the colors. Thus,
there is some set of colors $C$ which appears infinitely many times in the
sequence, and since each $C^{(n)}$ has cardinality at least $d+1$, so does
$C$. That is, we have found a sequence of arbitrarily small open balls at
$\vec{p}$ which each intersect all $d+1$ colors in $C$, and so $\vec{p}$ is in
the closure of all colors in $C$. ; equivalently (as shown in subsec:kkm-
lebesgue-coloring-equivalence) the  (Lebesgue Covering Theorem). and the
(Cubical KKM Lemma). would follow from this result and so both the  (Lebesgue
Covering Theorem). and the  (Cubical KKM Lemma). could be viewed as special
cases of a more general result.

##  5 Acknowledgements

Pavan’s work is partially supported by NSF award 2130536. Vander Woude and
Vinodchandran’s work is partially supported by NSF award 2130608. Radcliffe’s
work is partially supported by Simons grant 429383. Part of the work was done
when Pavan and Vinodchandran were visiting the Simons Institute for the Theory
of Computing. Part of the work was done while Dixon was a postdoc at Ben-
Gurion University of the Negev.

## References

  * [1] Jesus A. De Loera, Elisha Peterson, and Francis Edward Su.  A Polytopal Generalization of Sperner’s Lemma.  Journal of Combinatorial Theory, Series A, 100(1):1–26, October 2002.  URL: https://www.sciencedirect.com/science/article/pii/S0097316502932747, doi:10.1006/jcta.2002.3274.
  * [2] R. J. Gardner.  The Brunn-Minkowski inequality.  Bulletin of the American Mathematical Society, 39(03):355–406, April 2002.  URL: http://www.ams.org/journal-getitem?pii=S0273-0979-02-00941-2, doi:10.1090/S0273-0979-02-00941-2.
  * [3] Witold Hurewicz and Henry Wallman.  Dimension Theory.  Princeton University Press, 1948.  URL: http://archive.org/details/in.ernet.dli.2015.84609.
  * [4] Hidetoshi Komiya.  A simple proof of K-K-M-S theorem.  Economic Theory, 4(3):463–466, May 1994.  doi:10.1007/BF01215383.
  * [5] H. W. Kuhn.  Some combinatorial lemmas in topology.  IBM Journal of Research and Development, 4(5):518–524, 1960.  doi:10.1147/rd.45.0518.
  * [6] Henri Lebesgue.  Sur la non-applicabilité de deux domaines appartenant respectivement à des espaces à n et n+p dimensions.  Mathematische Annalen, 70(2):166–168, June 1911.  doi:10.1007/BF01461155.
  * [7] Wacław Sierpiński.  Sur la question de la mesurabilité de la base de M. Hamel.  Fundamenta Mathematicae, 1:105–111, 1920.  Publisher: Instytut Matematyczny Polskiej Akademii Nauk.  URL: https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/fundamenta-mathematicae/all/1/1/92383/sur-la-question-de-la-mesurabilite-de-la-base-de-m-hamel, doi:10.4064/fm-1-1-105-111.
  * [8] Gerard van der Laan, Dolf Talman, and Zaifu Yang.  Intersection theorems on polytopes.  Mathematical Programming, 84(1):25–38, January 1999.  URL: http://link.springer.com/10.1007/s10107980024a, doi:10.1007/s10107980024a.
  * [9] Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran.  Geometry of rounding, 2022.  URL: https://arxiv.org/abs/2211.02694.
  * [10] Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran.  Geometry of rounding: Near optimal bounds and a new neighborhood sperner’s lemma, 2023.  URL: https://arxiv.org/abs/2304.04837.
  * [11] Laurence A Wolsey.  Cubical sperner lemmas as applications of generalized complementary pivoting.  Journal of Combinatorial Theory, Series A, 23(1):78–87, July 1977\.  URL: https://www.sciencedirect.com/science/article/pii/0097316577900814, doi:10.1016/0097-3165(77)90081-4.

##  Appendix A Skipped Proofs

###  A.1 Equivalence of the KKM Lemma, Lebesgue Covering Theorem, and Color
Variant

######  Lemma A.1 (KKM/Lebesgue $\Longrightarrow$ KKM).

The  (KKM-Lebesgue Theorem). (*kkm-lebesgue) implies the  (Cubical KKM Lemma).
(*true-kkm-lemma).

###### Proof.

Let $\mathcal{C}=\\{C_{\vec{v}}\\}_{\vec{v}\in\\{0,1\\}^{d}}$ be a KKM cover
of $[0,1]^{d}$. For each $\vec{x}\in[0,1]^{d}$, let $F_{\vec{x}}$ denote the
smallest face of the cube containing $\vec{x}$ (i.e. $F_{\vec{x}}$ is the
intersection of all faces containing $\vec{x}$). By the defining property of a
KKM cover, we have $F_{\vec{x}}\subseteq\bigcup_{\vec{v}\in
F_{\vec{x}}\cap\\{0,1\\}^{d}}C_{\vec{v}}$, so in particular there exists some
$\vec{v}\in F_{\vec{x}}\cap\\{0,1\\}^{d}$ with $\vec{x}\in C_{\vec{v}}$.
Define the function $\chi$ as follows where $\min_{\mathrm{lex}}$ denotes the
minimum element in a subset of $\\{0,1\\}^{d}$ under the lexicographic
ordering:

$\displaystyle\chi$ $\displaystyle:[0,1]^{d}\to\\{0,1\\}^{d}$
$\displaystyle\chi(\vec{x})$
$\displaystyle=\min_{\mathrm{lex}}\\{\vec{v}\in\\{0,1\\}^{d}\cap
F_{\vec{x}}:\vec{x}\in C_{\vec{v}}\\}$

We have already demonstrated that the the set in the definition is not empty,
so $\chi$ is well-defined.

We claim that $\chi$ is a finite SLKKM coloring of $[0,1]^{d}$. The finiteness
is trivial because the codomain of $\chi$ is finite, so we need only show it
is an SLKKM coloring. Suppose $F^{(0)}$ and $F^{(1)}$ are opposite faces of
the cube (i.e. there is some coordinate $j\in[d]$ such that
$\pi_{j}(F^{(0)})=\\{0\\}$ and $\pi_{j}(F^{(1)})=\\{1\\}$) and let
$\vec{x}^{(0)}\in F^{(0)}$ and $\vec{x}^{(1)}\in F^{(1)}$. Because
$\pi_{j}(F^{(0)})\cap\pi_{j}(F^{(1)})=\emptyset$, it follows that $F^{(0)}\cap
F^{(1)}=\emptyset$, so $F^{(0)}$ and $F^{(1)}$ are disjoint sets.

Because $\vec{x}^{(0)}\in F^{(0)}$ and $F_{\vec{x}^{(0)}}$ is by definition
the intersection of all faces containing $\vec{x}$, we have
$F_{\vec{x}^{(0)}}\subseteq F^{(0)}$ (and similarly replacing “$0$” with
“$1$”) so that also $F^{(0)}$ and $F^{(1)}$ are disjoint. By definition of
$\chi$ we have $\chi(\vec{x}^{(0)})\in F^{(0)}$ and $\chi(\vec{x}^{(1)})\in
F^{(1)}$ showing that $\chi(\vec{x}^{(0)})\not=\chi(\vec{x}^{(1)})$, so $\chi$
is an SLKKM coloring.

By the  (KKM-Lebesgue Theorem)., there exists $\vec{p}\in[0,1]^{d}$ such that
$\left\lvert\\{\vec{v}\in\\{0,1\\}^{d}:\vec{p}\in\overline{\chi^{-1}(\vec{v})}\\}\right\rvert\geq
d+1$. Fix such a $\vec{p}$ for the remainder of the proof. For each
$\vec{v}\in\\{0,1\\}^{d}$, observe that $\chi^{-1}(\vec{v})\subseteq
C_{\vec{v}}$ because for any $\vec{x}\in\chi^{-1}(\vec{v})$ we have
$\chi(\vec{x})=\vec{v}$, so by definition of $\chi$ we have $\vec{x}\in
C_{\vec{v}}$. Because closures maintain subset containment and because
$C_{\vec{v}}$ is a closed set by hypothesis of the  (Cubical KKM Lemma)., we
have
$\overline{\chi^{-1}(\vec{v})}\subseteq\overline{C_{\vec{v}}}=C_{\vec{v}}$. It
then follows immediately that

$\\{\vec{v}\in\\{0,1\\}^{d}:\vec{p}\in\chi^{-1}(\vec{v})\\}\subseteq\\{\vec{v}\in\\{0,1\\}^{d}:\vec{p}\in
C_{\vec{v}}\\}$

and since the former has cardinality at least $d+1$, so does the latter which
proves the  (Cubical KKM Lemma).. ∎

######  Lemma A.2 (KKM/Lebesgue $\Longrightarrow$ Lebesgue).

The  (KKM-Lebesgue Theorem). (*kkm-lebesgue) implies the  (Lebesgue Covering
Theorem). (*true-lebesgue-covering-theorem).

###### Proof.

Let $N\in\mathbb{N}$ and $\mathcal{C}=\\{C_{n}\\}_{n\in[N]}$ be a Lebesgue
cover of $[0,1]^{d}$. Because this is a cover, every point of $[0,1]^{d}$
belongs to some set, so define $\chi$ as follows:

$\displaystyle\chi$ $\displaystyle:[0,1]^{d}\to[N]$
$\displaystyle\chi(\vec{x})$ $\displaystyle=\min\\{n\in[N]:\vec{x}\in
C_{n}\\}.$

This is trivially a finite SLKKM coloring of $[0,1]^{d}$ because the codomain
of $\chi$ is finite and for $\vec{x}^{(0)}$ and $\vec{x}^{(1)}$ on opposite
faces, there is no $n\in[N]$ for which both $\vec{x}^{(0)}\in C_{n}$ and
$\vec{x}^{(1)}\in C_{n}$ and thus $\\{n\in[N]:\vec{x}^{(0)}\in C_{n}\\}$ and
$\\{n\in[N]:\vec{x}^{(1)}\in C_{n}\\}$ are disjoint, so
$\chi(\vec{x}^{(0)})\not=\chi(\vec{x}^{(1)})$.

By the  (KKM-Lebesgue Theorem)., there exists $\vec{p}\in[0,1]^{d}$ such that
$\left\lvert\\{n\in[N]:\vec{p}\in\overline{\chi^{-1}(n)}\\}\right\rvert\geq
d+1$. Fix such a $\vec{p}$ for the remainder of the proof. For each $n\in[N]$,
observe that $\chi^{-1}(n)\subseteq C_{n}$ because for any
$\vec{x}\in\chi^{-1}(n)$ we have $\chi(\vec{x})=n$, so by definition of $\chi$
we have $\vec{x}\in C_{n}$. Because closures maintain subset containment and
because $C_{n}$ is a closed set by hypothesis of the  (Lebesgue Covering
Theorem)., we have $\overline{\chi^{-1}(n)}\subseteq\overline{C_{n}}=C_{n}$.
It then follows immediately that

$\\{n\in[N]:\vec{p}\in\chi^{-1}(n)\\}\subseteq\\{n\in[N]:\vec{p}\in C_{n}\\}$

and since the former has cardinality at least $d+1$, so does the latter which
proves the  (Lebesgue Covering Theorem).. ∎

######  Lemma A.3 (Lebesgue $\Longrightarrow$ KKM/Lebesgue).

The  (Lebesgue Covering Theorem). (*true-lebesgue-covering-theorem) implies
the  (KKM-Lebesgue Theorem). (*kkm-lebesgue).

This proof is probably the trickiest of the four. In order to use the
hypothesis of the  (Lebesgue Covering Theorem). (*true-lebesgue-covering-
theorem), we can’t just close the sets in an SLKKM coloring because the
closures might intersect opposite faces. Thus, we first have to extend the
coloring, and we do so as we do in the proof of the main result of the paper
(the  (Neighborhood KKM-Lebesgue Theorem). (*kkm-lebesgue-variant)).

###### Proof.

For this proof, we assume that the cube is $[-\frac{1}{2},\frac{1}{2}]^{d}$
instead of $[0,1]^{d}$. Let $C$ be a finite set and
$\chi:[-\frac{1}{2},\frac{1}{2}]^{d}\to C$ a finite SLKKM coloring of
$[-\frac{1}{2},\frac{1}{2}]^{d}$. Let $\varepsilon\in(0,\infty)$ be any fixed
value throughout the entirety of the proof. Let $f$ and $\gamma=\chi\circ f$
as in the proof of the  (Neighborhood KKM-Lebesgue Theorem). (*kkm-lebesgue-
variant) so that
$\gamma:[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}\to C$ is an
extension of the coloring $\chi$ to the larger cube
$\gamma:[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ (see also
subfig:1_non_spanning_coloring and subfig:2_extended_coloring) with the
property that for each color $c\in C$, there exists an orientation
$\vec{v}^{(c)}\in\\{-1,1\\}^{d}$ so that the set
$Y_{c}\operatorname{\overset{def}{=}}\gamma^{-1}(c)$ of points of color $c$
(according to $\gamma$) is a subset of
$\prod_{i=1}^{d}v^{(c)}_{i}\cdot(-\frac{1}{2},\frac{1}{2}+\varepsilon]$ (see
kkm-lebesgue-variant-subclaim-1 in the proof of the  (Neighborhood KKM-
Lebesgue Theorem). (*kkm-lebesgue-variant)). Because closures maintain subset
containment we have

$\overline{\gamma^{-1}(c)}=\overline{Y_{c}}\subseteq\overline{\prod_{i=1}^{d}v^{(c)}_{i}\cdot(-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon]}=\prod_{i=1}^{d}v^{(c)}_{i}\cdot[-\tfrac{1}{2},\tfrac{1}{2}+\varepsilon].$

This demonstrates that for each color $c\in C$, the set $\gamma^{-1}(c)$ of
points given color $c$ does not include points on opposite faces of the cube
$[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ (because if it did,
then there would be some coordinate $j\in[d]$ such that
$\pi_{j}(\gamma^{-1}(c))\supseteq\\{-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon\\}$,
but the containment above shows this is not the case). Thus,
$\mathcal{C}=\\{\gamma^{-1}(c)\\}_{c\in\mathcal{C}}$ is a Lebesgue cover of
the cube $[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ (we could
rescale it to $[0,1]^{d}$ and re-index the cover with $[N]$ for $N=\left\lvert
C\right\rvert$ to be really formal, but we won’t).

By the  (Lebesgue Covering Theorem)., there exists
$\vec{q}\in[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}$ such that
$\left\lvert\\{c\in\mathcal{C}:\vec{q}\in\overline{\gamma^{-1}(c)}\\}\right\rvert\geq
d+1$. Fix such a $\vec{q}$ for the remainder of the proof and let
$\vec{p}=f(\vec{q})$ (recalling that
$f:[-\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon]^{d}\to[-\frac{1}{2},\frac{1}{2}=^{d}$
is as in the proof of the  (Neighborhood KKM-Lebesgue Theorem). (*kkm-
lebesgue-variant)).

######  Claim A.

For each $c\in C$, if $\vec{q}\in\overline{\gamma^{-1}(c)}$, then
$\vec{p}\in\overline{\chi^{-1}(c)}$.

###### Proof of Claim.

Let $c\in C$ be arbitrary. If $\vec{q}\in\overline{\gamma^{-1}(c)}$, then
there is a sequence $\langle\vec{q}^{(j)}\rangle_{j=1}^{\infty}$ of points in
$\gamma^{-1}(c)$ converging to $\vec{q}$. Because for each $j\in\mathbb{N}$ we
have $\vec{q}^{(j)}\in\gamma^{-1}(c)$, we have $\gamma(\vec{q}^{(j)})=c$.
Then, by the definition of $\gamma$, we have

$c=\gamma(\vec{q}^{(j)})=\chi(f(\vec{q}^{(j)}))$

showing that $f(\vec{q}^{(j)})\in\chi^{-1}(c)$. Since $f$ is a continuous
function181818 It is argued implicitly in kkm-lebesgue-variant-subclaim-4 in
the proof of the  (Neighborhood KKM-Lebesgue Theorem). (*kkm-lebesgue-variant)
that $f$ is Lipschitz with Lipschitz constant $1$. Alternatively, this could
be analyzed directly. , then $\langle f(\vec{q}^{(j)})\rangle_{j=1}^{\infty}$
converges to $f(\vec{q})=\vec{p}$ demonstrating that
$\vec{p}\in\overline{\chi^{-1}(c)}$. ∎

It then follows immediately that

$\\{c\in C:\vec{p}\in\overline{\gamma^{-1}(c)}\\}\subseteq\\{c\in
C:\vec{p}\in\overline{\chi^{-1}(c)}\\}$

and since the former has cardinality at least $d+1$ (established prior to the
claim), so does the latter which proves the  (KKM-Lebesgue Theorem).. ∎

######  Lemma A.4 (KKM $\Longrightarrow$ KKM/Lebesgue).

The  (Cubical KKM Lemma). (*true-kkm-lemma) implies the  (KKM-Lebesgue
Theorem). (*kkm-lebesgue).

In the proof we essentially condense an SLKKM coloring to have codomain of
cardinality $2^{d}$—one color associated to each vertex—and then close each
color set to apply the  (Cubical KKM Lemma). (*true-kkm-lemma).

###### Proof.

Let $C$ be a finite set and $\chi:[0,1]^{d}\to C$ a finite SLKKM coloring.
Because $\chi$ does not map points on opposite faces to the same color, this
means for each color $c\in C$ and coordinate $i\in[d]$ that the set of points
given color $c$ (i.e. $\chi^{-1}(c)$) does not contain a point with $i$th
coordinate $0$ and also a point with $i$th coordinate $1$ (i.e.
$\pi_{i}(\chi^{-1}(c))\not\supseteq\\{0,1\\}$).

For each $i\in[d]$, define $f_{i}:C\to\\{0,1\\}$ by

$f_{i}(c)=\begin{cases}0&0\in\pi_{i}(\chi^{-1}(c))\\\
1&1\in\pi_{i}(\chi^{-1}(c))\\\ 0&\text{otherwise}\end{cases}.$

The function $f_{i}$ is well-defined because the first two cases are mutually
exclusive. Then define $f:C\to\\{0,1\\}^{d}$ by $f(c)=\langle
f_{i}(c)\rangle_{i=1}^{d}$, and define the (coloring) function
$\zeta:[0,1]^{d}\to\\{0,1\\}^{d}$ as the composition $f\circ\chi$.

For each $\vec{v}\in\\{0,1\\}^{d}$, let
$C_{\vec{v}}=\overline{\zeta^{-1}(\vec{v})}$, and let
$\mathcal{C}=\\{C_{\vec{v}}\\}_{\vec{v}\in\\{0,1\\}^{d}}$. We claim that
$\mathcal{C}$ is a KKM cover of $[0,1]^{d}$ which we prove by the following
claim.

######  Claim A.

For each face $F$ of $[0,1]^{d}$, we have $F\subseteq\bigcup_{\vec{v}\in
F\cap\\{0,1\\}^{d}}C_{\vec{v}}$.

###### Proof of Claim.

Let $F$ be an arbitrary face of $[0,1]^{d}$; this means that
$F=\prod_{i=1}^{d}F_{i}$ where each $F_{i}$ is either $\\{0\\}$, $\\{1\\}$, or
$[0,1]$. Let $\vec{x}\in F$ be arbitrary noting that this implies for each
coordinate $i\in[d]$ that $x_{i}\in F_{i}$. Let $c=\chi(\vec{x})$ (so
$\vec{x}\in\chi^{-1}(c))$.

We first show for each coordinate $i\in[d]$ that $f_{i}(c)\in F_{i}$ and do so
in three cases.

  1. 1.

If $x_{i}=0$, then $0=x_{i}\in\pi_{i}(\chi^{-1}(c))$, so by definition of
$f_{i}$ we have $f_{i}(c)=0$ showing that $f_{i}(c)=0=x_{i}\in F_{i}$.

  2. 2.

If $x_{i}=1$, then $1=x_{i}\in\pi_{i}(\chi^{-1}(c))$, so by definition of
$f_{i}$ we have $f_{i}(c)=1$ showing that $f_{i}(c)=1=x_{i}\in F_{i}$.

  3. 3.

Otherwise $x_{i}\in(0,1)$, so because $x_{i}\in F_{i}$ we cannot have
$F_{i}=\\{0\\}$ or $F_{i}=\\{1\\}$ and so it must be that $F_{i}=[0,1]$. Thus,
$f_{i}(c)\in\\{0,1\\}\subseteq F_{i}$.

Now let $\vec{v}^{(0)}=\zeta(\vec{x})$ (so
$\vec{x}\in\zeta^{-1}(\vec{v}^{(0)})$) and observe the following:

$\vec{v}^{(0)}=\zeta(\vec{x})=f(\chi(\vec{x}))=f(c)=\langle
f_{i}(c)\rangle_{i=1}^{d}\in\prod_{i=1}^{d}F_{i}=F.$

Thus $\vec{v}^{(0)}\in F$, and also vacuously
$\vec{v}^{(0)}=\zeta(\vec{x})\in\\{0,1\\}^{d}$. This shows that

$\vec{x}\in\zeta^{-1}(\vec{v}^{(0)})\subseteq\overline{\zeta^{-1}(\vec{v}^{(0)})}=C_{\vec{v}^{(0)}}\subseteq\bigcup_{\vec{v}\in
F\cap\\{0,1\\}^{d}}C_{\vec{v}}.$

Since $\vec{x}\in F$ was arbitrary, we have $F\subseteq\bigcup_{\vec{v}\in
F\cap\\{0,1\\}^{d}}C_{\vec{v}}$ as claimed. ∎

Because $\mathcal{C}$ is a KKM cover, by the  (Cubical KKM Lemma)., there
exists $\vec{p}\in[0,1]^{d}$ such that the set
$V^{\prime}\operatorname{\overset{def}{=}}\\{\vec{v}\in\\{0,1\\}^{d}:\vec{p}\in
C_{\vec{v}}\\}$ has cardinality at least $d+1$. Fix such a $\vec{p}$ for the
remainder of the proof.

Note that for each $\vec{v}\in V$, we have

$\zeta^{-1}(\vec{v})=(f\circ\chi)^{-1}(\vec{v})=\chi^{-1}(f^{-1}(\vec{v}))=\bigcup_{c\in
f^{-1}(\vec{v})}\chi^{-1}(c).$ (1)

Now, for each $\vec{v}\in V^{\prime}$, because $\vec{p}$ is in the closure of
$\zeta^{-1}(\vec{v})$, any open set containing $\vec{p}$ intersects
$\zeta^{-1}(\vec{v})=\bigcup_{c\in f^{-1}(\vec{v})}\chi^{-1}(c)$ and thus
intersects $\chi^{-1}(c)$ for some $c\in f^{-1}(\vec{v})$. Let $g(\vec{v})$
denote one such color191919 We don’t need the full axiom of choice here
because $C$ has finite cardinality. .

Because $f^{-1}(\vec{v})$ and $f^{-1}(\vec{v}\,^{\prime})$ are trivially
disjoint for $\vec{v}\not=\vec{v}\,^{\prime}$, this means $g(\vec{v})$ and
$g(\vec{v}\,^{\prime})$ are distinct colors so $g:V^{\prime}\to C$ is an
injection which means there are at least $d+1$ colors in $C$ that are
intersected by any open set containing $\vec{p}$.

Because $\left\lvert C\right\rvert$ is finite, then for each $\vec{v}\in V$,
$f^{-1}(\vec{v})\subseteq C$ is finite, then we can use the fact the the
closure of a finite union is equal to the finite union of the closures to
extend this to

$\displaystyle\vec{p}$ $\displaystyle\in\bigcap_{\vec{v}\in
V^{\prime}}\overline{\zeta^{-1}(\vec{v})}$ $\displaystyle=\bigcap_{\vec{v}\in
V^{\prime}}\overline{\bigcup_{c\in f^{-1}(\vec{v})}\chi^{-1}(c)}$
$\displaystyle=\bigcap_{\vec{v}\in V^{\prime}}\bigcup_{c\in
f^{-1}(\vec{v})}\overline{\chi^{-1}(c)}$ ($f^{-1}(\vec{v})$ is finite)

and thus, for each $\vec{v}\in V^{\prime}$, $\vec{p}$ belongs to the closure
of $\chi^{-1}(c)$ for some $c\in f^{-1}(\vec{v})$. By the same argument there
are at least $d+1$ such colors in $C$. That is, $\left\lvert\\{c\in
C:\vec{p}\in\overline{\chi^{-1}(c)}\\}\right\rvert\geq d+1$ which proves the
(KKM-Lebesgue Theorem).. ∎

###  A.2 Background for the  (Neighborhood KKM-Lebesgue Theorem).

###### Proof.

Let $n=\left\lceil\alpha\right\rceil$. This implies that $\alpha>n-1$
(otherwise $\alpha\leq n-1$ so $\left\lceil\alpha\right\rceil\leq n-1$). Thus
$(n-1,\alpha)$ is non-empty and we can take any $\gamma\in(n-1,\alpha)$. Then
$n-1<\gamma\leq\left\lceil\gamma\right\rceil\leq\left\lceil\alpha\right\rceil=n$
showing that $\left\lceil\gamma\right\rceil=n$ as well. ∎

###### Proof.

We will show that $(x^{1/d}+\alpha)^{d}-x(1+\alpha)^{d}\geq 0$ for these
parameters. Let For $d$, $\alpha$ as above, let $f:[0,1]\to\mathbb{R}$ be
defined by $f(x)=(x^{1/d}+\alpha)^{d}-x(1+\alpha)^{d}$. Observe that
$f(0)=\alpha^{d}\geq 0$ and $f(1)=(1+\alpha)^{d}-(1+\alpha)^{d}=0$. We will
now prove that $f$ is convex on the domain202020 Actually we could have
defined the domain of $f$ to be $[0,\infty)$ and we show that $f$ is convex on
that domain. However, we only have need of the interval $[0,1]$ because that
is where we know that $f$ is non-negative.  $[0,1]$. This will be sufficient
to prove the claim because $f$ is also non-negative at $0$ and at $1$.

We show that $f$ is convex on $[0,1]$ by considering its second derivative on
$(0,1]$. We start with the first derivative with respect to $x$.

$\displaystyle\frac{d}{dx}f(x)$
$\displaystyle=\frac{d}{dx}\left[(x^{1/d}+\alpha)^{d}-x(1+\alpha)^{d}\right]$
$\displaystyle=d(x^{1/d}+\alpha)^{d-1}\cdot\frac{1}{d}x^{(1/d)-1}-(1+\alpha)^{d}$
$\displaystyle=(x^{1/d}+\alpha)^{d-1}x^{(1/d)-1}-(1+\alpha)^{d}$

where we use the standard convention that $0^{0}=1$. Then

$\displaystyle\frac{d^{2}}{dx^{2}}f(x)$
$\displaystyle=\frac{d}{dx}\left[(x^{1/d}+\alpha)^{d-1}x^{1/d-1}-(1+\alpha)^{d}\right]$
$\displaystyle=(x^{1/d}+\alpha)^{d-1}\cdot\left(\frac{1}{d}-1\right)x^{1/d-2}+x^{1/d-1}\cdot(d-1)(x^{1/d}+\alpha)^{d-2}\frac{1}{d}x^{1/d-1}$
$\displaystyle=(x^{1/d}+\alpha)(x^{1/d}+\alpha)^{d-2}\left(-\frac{d-1}{d}\right)\left(x^{1/d-2}\right)+(x)\left(x^{1/d-2}\right)\left(\frac{d-1}{d}\right)\left(x^{1/d}+\alpha\right)^{d-2}\left(x^{1/d-1}\right)$
$\displaystyle=\frac{(x^{1/d}+\alpha)^{d-2}(d-1)\left(x^{1/d-2}\right)}{d}\left[-(x^{1/d}+\alpha)+(x)\left(x^{1/d-1}\right)\right]$
$\displaystyle=\frac{(x^{1/d}+\alpha)^{d-2}(d-1)\left(x^{1/d-2}\right)}{d}\left[-(x^{1/d}+\alpha)+\left(x^{1/d}\right)\right]$
$\displaystyle=\frac{-\alpha(x^{1/d}+\alpha)^{d-2}(d-1)\left(x^{1/d-2}\right)}{d}$
$\displaystyle=\frac{-\alpha(x^{1/d}+\alpha)^{d}(d-1)\left(x^{1/d}\right)}{d(x^{1/d}+\alpha)^{2}x^{2}}.$

Note that because $\alpha\geq 0$ and $d\geq 1$, we have for $x\in(0,\infty]$
that the denominator is positive and the numerator is non-positive showing
that $\frac{d^{2}}{dx^{2}}f(x)\leq 0$ so $f$ is convex on $(0,\infty)$ and by
continuity on $[0,\infty)$. Because $f(x)$ is convex on $[0,1]$ and non-
negative at $x=0$ and $x=1$, it is non-negative on all of $[0,1]$. ∎

In order to prove outer-measure-brunn-minkowsi-bound-l-infty we need some
simple background results.

The following fact says that the Minkowski sum of a set $X$ and an open ball
at the origin can be viewed as a union of open balls positioned at each point
of $X$. This is useful not only conceptually but because it guarantees that
this Minkowski sum is open and thus measurable.

######  Fact A.5.

For any normed vector space, given a set $X$ and $\varepsilon\in(0,\infty)$,
then

$X+B^{\circ}(\varepsilon,\vec{0})=\bigcup_{\vec{x}\in
X}B^{\circ}(\varepsilon,\vec{x}).$

The same can be said replacing open balls with closed balls.

###### Proof.

We show this only for the open balls. Switching all open balls in the proof
with closed ones gives the proof for closed balls.

($\subseteq$) A generic element of $X+B^{\circ}(\varepsilon,\vec{0})$ is
$\vec{x}+\vec{b}$ for some $\vec{x}\in X$ and $\vec{b}\in
B^{\circ}(\varepsilon,\vec{0})$ which means
$\vec{x}+\vec{b}\in\vec{x}+B^{\circ}(\varepsilon,\vec{0})=B^{\circ}(\varepsilon,\vec{x})\subseteq\bigcup_{\vec{x}\in
X}B^{\circ}(\varepsilon,\vec{x})$.

($\supseteq$) Given $\vec{y}\in\bigcup_{\vec{x}\in
X}B^{\circ}(\varepsilon,\vec{x})$ there is some particular $\vec{x}\in X$ such
that $y\in
B^{\circ}(\varepsilon,\vec{x})=\vec{x}+B^{\circ}(\varepsilon,\vec{0})$ which
means $\vec{y}=\vec{x}+\vec{b}$ for some $\vec{b}\in
B^{\circ}(\varepsilon,\vec{0})$, and since $\vec{x}\in X$, we have $\vec{y}\in
X+B^{\circ}(\varepsilon,\vec{0})$. ∎

The next fact (sum-of-balls) says that we can decompose a ball into a
Minkowski sum of two smaller balls. We will use this along with associativity
of the Minkowski sum to deal swiftly with issues of non-measurable sets.

######  Fact A.6.

For any normed vector space, and any $\alpha,\beta\in(0,\infty)$, it holds
that
$B^{\circ}(\alpha,\vec{0})+B^{\circ}(\beta,\vec{0})=B^{\circ}(\alpha+\beta,\vec{0})$.

###### Proof.

($\subseteq$) A generic element of
$B^{\circ}(\alpha,\vec{0})+B^{\circ}(\beta,\vec{0})$ is $\vec{a}+\vec{b}$ for
$\vec{a}\in B^{\circ}(\alpha,\vec{0})$ and $\vec{b}\in
B^{\circ}(\beta,\vec{0})$. Then $\left\lVert\vec{a}\right\rVert<\alpha$ and
$\left\lVert\vec{b}\right\rVert<\beta$, so
$\left\lVert\vec{a}+\vec{b}\right\rVert<\alpha+\beta$ showing
$\vec{a}+\vec{b}\in B^{\circ}(\alpha+\beta,\vec{0})$.

($\supseteq$) Let $\vec{x}\in B^{\circ}(\alpha+\beta,\vec{0})$ which implies
$\left\lVert\vec{x}\right\rVert<\alpha+\beta$. If
$\left\lVert\vec{x}\right\rVert<\alpha$, then $\vec{x}\in
B^{\circ}(\alpha,\vec{0})$ and $\vec{0}\in B^{\circ}(\beta,\vec{0})$, so
$\vec{x}=\vec{x}+\vec{0}\in
B^{\circ}(\alpha,\vec{0})+B^{\circ}(\beta,\vec{0})$. Similarly, if
$\left\lVert\vec{x}\right\rVert<\beta$, then $\vec{x}=\vec{0}+\vec{x}\in
B^{\circ}(\alpha,\vec{0})+B^{\circ}(\beta,\vec{0})$. In either case we would
be done, so we may now assume that
$\left\lVert\vec{x}\right\rVert\geq\alpha,\beta$. Let
$\varepsilon=\alpha+\beta-\left\lVert\vec{x}\right\rVert\in(0,\infty)$. Since
$\left\lVert\vec{x}\right\rVert\geq\alpha$, we have $\varepsilon\leq\beta$,
and because $\left\lVert\vec{x}\right\rVert\geq\beta$, we have
$\varepsilon\leq\alpha$. This shows $\frac{\varepsilon}{2}<\alpha,\beta$. Let
$\vec{a}=(\alpha-\frac{\varepsilon}{2})\frac{\vec{x}}{\left\lVert\vec{x}\right\rVert}$
and
$\vec{b}=(\beta-\frac{\varepsilon}{2})\frac{\vec{x}}{\left\lVert\vec{x}\right\rVert}$
noting that
$\left\lVert\vec{a}\right\rVert=\alpha-\frac{\varepsilon}{2}\in(0,\alpha)$ and
$\left\lVert\vec{b}\right\rVert=\beta-\frac{\varepsilon}{2}\in(0,\beta)$.
Also, note that
$\vec{a}+\vec{b}=(\alpha-\frac{\varepsilon}{2}+\beta-\frac{\varepsilon}{2})\frac{\vec{x}}{\left\lVert\vec{x}\right\rVert}=\left\lVert\vec{x}\right\rVert\frac{\vec{x}}{\left\lVert\vec{x}\right\rVert}=\vec{x}$
which shows $\vec{x}\in B^{\circ}(\alpha,\vec{0})+B^{\circ}(\beta,\vec{0})$. ∎

The final fact (antisymmetry-containment-pre-claim-minkowski-sum), while also
very simple, is the key change of perspective that allowed us to prove the
main result. It says that if we are checking if a member $X$ in our partition
intersects an $\varepsilon$-ball located at $\vec{p}$ (in order to see how
many such members there are), we can instead enlarge $X$ by taking its
Minkowski sum with the origin-centered $\varepsilon$-ball, and check if this
enlarged member contains the point $\vec{p}$.

######  Fact A.7.

For any normed vector space, for any set $X$ and vector $\vec{p}$, the
following are equivalent:

  1. 1.

$\overline{B}(\varepsilon,\vec{p})\cap X\not=\emptyset$

  2. 2.

$\vec{p}\in X+\overline{B}(\varepsilon,\vec{0})$

The same can be said replacing both closed balls with open balls.

###### Proof.

We show this only for the closed balls. Switching all closed balls in the
proof with open ones gives the proof for open balls.

($\Longrightarrow$) If $\overline{B}(\varepsilon,\vec{p})\cap
X\not=\emptyset$, then there exists
$\vec{y}\in\overline{B}(\varepsilon,\vec{p})\cap X$, and since
$\vec{y}\in\overline{B}(\varepsilon,\vec{p})$ we have
$\left\lVert\vec{y}-\vec{p}\right\rVert\leq\varepsilon$ so
$\vec{p}\in\overline{B}(\varepsilon,\vec{y})=\vec{y}+\overline{B}(\varepsilon,\vec{0})$,
and since $\vec{y}\in X$, $\vec{y}+\overline{B}(\varepsilon,\vec{0})\subseteq
X+\overline{B}(\varepsilon,\vec{0})$ showing that $\vec{p}\in
X+\overline{B}(\varepsilon,\vec{0})$.

($\Longleftarrow$) If $\vec{p}\in X+\overline{B}(\varepsilon,\vec{0})$ then
there exists $\vec{x}\in X$ and $\vec{b}\in\overline{B}(\varepsilon,\vec{0})$
such that $\vec{p}=\vec{x}+\vec{b}$. Thus $\vec{p}-\vec{x}=\vec{b}$, so
$\left\lVert\vec{p}-\vec{x}\right\rVert=\lVert\vec{b}\rVert\leq\varepsilon$,
so $\vec{x}\in\overline{B}(\varepsilon,\vec{p})$. Since $\vec{x}$ belongs to
both $X$ and $\overline{B}(\varepsilon,\vec{p})$, their intersection is non-
empty. ∎

With this background, we can state the  (Generalized Brunn-Minkowski
Inequality). and prove outer-measure-brunn-minkowsi-bound-l-infty. The
(Generalized Brunn-Minkowski Inequality). gives a bound on the volume of
Minkowski sums. It is common in measure theory for $d$th roots of
$d$-dimensional volumes to show up and they serve as a type of characteristic
length scale. With this interpretation, the  (Generalized Brunn-Minkowski
Inequality). says that the characteristic length scale of a Minkowski sum is
no less than the sum of characteristic length scales of the parts.

######  Theorem A.8 (Generalized Brunn-Minkowski Inequality).

Let $d\in\mathbb{N}$ and $A,B\subseteq\mathbb{R}^{d}$ be non-empty and
Lebesgue measurable such that $A+B$ is also Lebesgue measurable. Then

$m(A+B)^{\frac{1}{d}}\geq m(A)^{\frac{1}{d}}+m(B)^{\frac{1}{d}}.$

This version of the statement can be obtained from [2, Equation 11]; in that
survey, Gardner states this theorem with a requirement that the sets be
bounded, but in the following paragraph notes that this is not necessary and
the requirement is only stated for convenience of the presentation in that
survey. In the theorem, the requirement that $A+B$ is Lebesgue measurable is
not a triviality; Gardner discusses that there exist known Lebesgue measurable
sets $A$ and $B$ such that the Minkowski sum $A+B$ is not Lebesgue measurable
as shown in [7]. The next result gives us a way to circumvent this issue in
our application even if the members of our partition are not measurable by
taking $B$ to be an open set so that the sum $A+B$ is open (and thus
measurable), and using the outer measure of $A$ so that we don’t need the
assumption that $A$ is measurable.

Now we can prove the result which immediate implies outer-measure-brunn-
minkowsi-bound-l-infty when we instantiate it with the $\ell_{\infty}$ norm
specifically.

######  Lemma A.9.

Let $d\in\mathbb{N}$ and let $\mathbb{R}^{d}$ be equipped with any norm
$\left\lVert\cdot\right\rVert$. Let $Y\subseteq\mathbb{R}^{d}$, and
$\varepsilon\in(0,\infty)$. Then
$Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})$
is open (and thus Borel measurable), and
$m(Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0}))\geq\left(m_{out}(Y)^{\frac{1}{d}}+\varepsilon\cdot(v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d})^{\frac{1}{d}}\right)^{d}$.

###### Proof.

By minkowski-bubble-union,
$Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})=\bigcup_{\vec{y}\in
Y}B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{y})$
which is a union of open sets, so is itself open and thus Borel measurable.
Now, for any $\varepsilon^{\prime}\in(0,\varepsilon)$, observe that by sum-of-
balls,
$B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})=B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})$
and thus, this sum is measurable because it is an open ball. Using this
equality and the associativity of the Minkowski sum, we have

$Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})=Y+\left[B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})\right]=\left[Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})\right]+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0}).$

Thus, we have the following inequalities:

$\displaystyle
m\left(Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})\right)$
$\displaystyle=m\left(\left[Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})\right]+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})\right)$
(Above)
$\displaystyle\geq\left(m\left(Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})\right)^{\frac{1}{d}}+m\left(B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})\right)^{\frac{1}{d}}\right)^{d}$
The above comes from the  (Generalized Brunn-Minkowski Inequality).
(*generalized-brunn-minkowski-inequality) noting that as demonstrated above,
both sets
$Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon-\varepsilon^{\prime},\vec{0})$
and
$B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})$
are open and thus measurable. We continue.
$\displaystyle\geq\left(m_{out}\left(Y\right)^{\frac{1}{d}}+m\left(B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})\right)^{\frac{1}{d}}\right)^{d}$
The above inequality comes from the definition of the outer measure of $Y$
being the infimum of the measures of all measurable supersets of $Y$. Since
$Y\subseteq
Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon^{\prime},\vec{0})$,
we get the inequality above. Continuing, we have the following:
$\displaystyle=\left(m_{out}\left(Y\right)^{\frac{1}{d}}+m\left(\varepsilon^{\prime}\cdot
B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(1,\vec{0})\right)^{\frac{1}{d}}\right)^{d}$
(Scaling of norm-based balls)
$\displaystyle=\left(m_{out}\left(Y\right)^{\frac{1}{d}}+\left[(\varepsilon^{\prime})^{d}\cdot
m\left(B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(1,\vec{0})\right)\right]^{\frac{1}{d}}\right)^{d}$
(Scaling for Lebesgue measure)
$\displaystyle=\left(m_{out}\left(Y\right)^{\frac{1}{d}}+\varepsilon^{\prime}\cdot(v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d})^{\frac{1}{d}}\right)^{d}$
(Algebra and
$v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d}\operatorname{\overset{def}{=}}m\left(B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(1,\vec{0})\right)$)

Since the inequality above holds for all
$\varepsilon^{\prime}\in(0,\varepsilon)$, it must also hold in the limit
(keeping $d$ and $Y$ fixed):

$m\left(Y+B^{\circ}_{{\scriptscriptstyle\left\lVert\cdot\right\rVert}}(\varepsilon,\vec{0})\right)\geq\lim_{\varepsilon^{\prime}\to\varepsilon}\left[\left(m_{out}\left(Y\right)^{\frac{1}{d}}+\varepsilon^{\prime}\cdot(v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d})^{\frac{1}{d}}\right)^{d}\right]=\left(m_{out}\left(Y\right)^{\frac{1}{d}}+\varepsilon\cdot(v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert},d})^{\frac{1}{d}}\right)^{d}$

which concludes the proof. ∎

###### Proof.

This follows immediately from outer-measure-brunn-minkowsi-bound noting that
for the $\ell_{\infty}$ norm,
$v_{{\scriptscriptstyle\left\lVert\cdot\right\rVert_{\infty}},d}=2^{d}$. ∎

##  Appendix B Proof of the Folklore Proof of the Theorem 1.3 (Neighborhood
KKM-Lebesgue Theorem).

In this appendix, we provide a proof of the known Proof of the Theorem 1.3
(Neighborhood KKM-Lebesgue Theorem). restated below.

*

To prove it, we build up the proof via three results: exact-measure-of-
multiplicity handles a general measure space where each point is covered
exactly the same number of times and shows what the total measure of the
covering sets must be. upper-bound-measure-of-multiplicity uses this as a
lemma to prove what the total measure of the covering sets must be even if
points are not all covered the same number of times. lower-bound-cover-number
changes the perspective and focuses on how many times some point must be
covered given the total measure of the covering sets. Finally, *lower-bound-
cover-number-Rd (Proof of the Theorem 1.3 (Neighborhood KKM-Lebesgue
Theorem).) follows as an immediate corollary for $\mathbb{R}^{d}$
specifically.

Throughout this section, we use the word “countable” to mean finite or
countably infinite.

######  Fact B.1 (Interchange of Countable Sums with Non-negative Terms).

If $I,J$ are countable sets, and $a_{i,j}\geq 0$ for all $(i,j)\in I\times J$,
then

$\sum_{i\in I}\sum_{j\in J}a_{i,j}=\sum_{j\in J}\sum_{i\in I}a_{i,j}$

###### Proof.

This can be proved directly via basic analysis methods if $I$ and $J$ are
assumed to be $\mathbb{N}$ and the definition of the infinite sum as a limit
of finite sums is used. Alternatively, viewing the summation as an integral
over a countable measure space, this can be viewed as an immediate corollary
to Tonelli’s theorem. ∎

######  Lemma B.2 (Exact Measure of Multiplicity).

Let $n\in\mathbb{N}$. Let $X$ be a measurable set in some measure space (the
measure being denoted by $\mu$) and $\mathcal{A}$ a countable family of
measurable subsets of $X$ such that for each $x\in X$, $x$ belongs to exactly
$n$ members of $\mathcal{A}$. Then

$\sum_{A\in\mathcal{A}}\mu(A)=n\cdot\mu(X).$

###### Proof.

We note that if $n=0$, then the statement is trivially true because
$\mathcal{A}$ is either empty or contains just the empty set, and in either
case $\sum_{A\in\mathcal{A}}\mu(A)=0=0\cdot\mu(X)$ if we use the standard
convention that the empty sum is $0$.

For any $\mathcal{F}\subseteq\mathcal{A}$, let
$G_{\mathcal{F}}=\bigcap_{A\in\mathcal{F}}A$ noting that this is a countable
intersection of measurable sets, so it is measurable (mnemonically, the $G$
represents an intersection as it does in the notation for $G_{\delta}$ sets).

Let $\binom{\mathcal{A}}{n}$ denote all subsets of $\mathcal{A}$ of size $n$
noting that because $\mathcal{A}$ is countable, so is
$\binom{\mathcal{A}}{n}$. Observe that for distinct
$\mathcal{F},\mathcal{F}^{\prime}\in\binom{\mathcal{A}}{n}$, the sets
$G_{\mathcal{F}}$ and $G_{\mathcal{F}^{\prime}}$ are disjoint because

$G_{\mathcal{F}}\cap
G_{\mathcal{F}^{\prime}}=\left(\bigcap_{A\in\mathcal{F}}A\right)\cap\left(\bigcap_{A\in\mathcal{F}^{\prime}}A\right)=\bigcap_{A\in\mathcal{F}\cup\mathcal{F}^{\prime}}A$

and since $\mathcal{F}$ and $\mathcal{F}^{\prime}$ are distinct and each
contain $n$ items,
$\left\lvert\mathcal{F}\cup\mathcal{F}^{\prime}\right\rvert\geq n+1$, and by
assumption no point in $X$ belongs to $n+1$ members, so
$\bigcap_{A\in\mathcal{F}\cup\mathcal{F}^{\prime}}A=\emptyset$. Furthermore,
for each $x\in X$, since $x$ belongs to exactly $n$ members
$A_{1},\ldots,A_{n}$ of $\mathcal{A}$, taking
$\mathcal{F}=\\{A_{1},\ldots,A_{n}\\}$ we have $x\in G_{\mathcal{F}}$ which
shows that $\\{G_{\mathcal{F}}\colon\mathcal{F}\in\binom{\mathcal{A}}{n}\\}$
is a partition of $X$ into countably many measurable sets (allowing that some
$G_{\mathcal{F}}$ might be empty).

The last observation we need is that for any
$\mathcal{F}\in\binom{\mathcal{A}}{n}$ and any $A\in\mathcal{A}$, it holds
that if $A\in\mathcal{F}$, then $A\supseteq G_{\mathcal{F}}$ and if
$A\not\in\mathcal{F}$ then $A\cap G_{\mathcal{F}}=\emptyset$. To see this,
note that for any $x\in G_{\mathcal{F}}$, $x$ belongs to each of the $n$
members of $\mathcal{F}\subseteq\mathcal{A}$, and since by assumption $x$
belongs to exactly $n$ members of $\mathcal{A}$, it does not belong to any
other members of $\mathcal{A}$.

Now we have the following chain of equalities:

$\displaystyle\sum_{A\in\mathcal{A}}\mu(A)$
$\displaystyle=\sum_{A\in\mathcal{A}}\mu(A\cap X)$ ($A\subseteq X$ so $A\cap
X=A$)
$\displaystyle=\sum_{A\in\mathcal{A}}\mu\left(A\cap\left[\bigsqcup_{\mathcal{F}\in\binom{\mathcal{A}}{n}}G_{\mathcal{F}}\right]\right)$
(Set equality; the $G_{\mathcal{F}}$ partition $X$)
$\displaystyle=\sum_{A\in\mathcal{A}}\mu\left(\bigsqcup_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\left[A\cap
G_{\mathcal{F}}\right]\right)$ (Set equality)
$\displaystyle=\sum_{A\in\mathcal{A}}\left[\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\mu\left(A\cap
G_{\mathcal{F}}\right)\right]$ (Countable additivity of measures)
$\displaystyle=\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\left[\sum_{A\in\mathcal{A}}\mu\left(A\cap
G_{\mathcal{F}}\right)\right]$ (Interchange sums by interchange-of-countable-
sums)
$\displaystyle=\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\left[\sum_{A\in\mathcal{A}}\begin{cases}\mu\left(A\cap
G_{\mathcal{F}}\right)=\mu\left(G_{\mathcal{F}}\right)&A\in\mathcal{F}\\\
\mu\left(A\cap
G_{\mathcal{F}}\right)=\mu(\emptyset)=0&A\not\in\mathcal{F}\end{cases}\right]$
(Previous paragraph)
$\displaystyle=\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\left[\sum_{A\in\mathcal{F}}\mu\left(G_{\mathcal{F}}\right)\right]$
(Remove $0$ terms from summation)
$\displaystyle=\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\left[n\cdot\mu\left(G_{\mathcal{F}}\right)\right]$
($\left\lvert\mathcal{F}\right\rvert=n$)
$\displaystyle=n\sum_{\mathcal{F}\in\binom{\mathcal{A}}{n}}\mu\left(G_{\mathcal{F}}\right)$
(Linearity of summation)
$\displaystyle=n\cdot\mu\left(\bigsqcup_{\mathcal{F}\in\binom{\mathcal{A}}{n}}G_{\mathcal{F}}\right)$
(Countable additivity of measures) $\displaystyle=n\cdot\mu\left(X\right)$
(Set equality; the $G_{\mathcal{F}}$ partition $X$)

This proves the result. ∎

######  Lemma B.3 (Upper Bound Measure of Multiplicity).

Let $n\in\mathbb{N}$. Let $X$ be a measurable set in some measure space (the
measure being denoted by $\mu$) and $\mathcal{A}$ a countable family of
measurable subsets of $X$ such that for each $x\in X$, $x$ belongs to at most
$n$ members of $\mathcal{A}$. Then

$\sum_{A\in\mathcal{A}}\mu(A)\leq n\cdot\mu(X).$

###### Proof.

As in the last proof, for any $\mathcal{F}\subseteq\mathcal{A}$, let
$G_{\mathcal{F}}=\bigcap_{A\in\mathcal{F}}A$ noting that this is a countable
intersection of measurable sets, so it is measurable (mnemonically, the $G$
represents an intersection as it does in the notation for $G_{\delta}$ sets).
And for any $k\in[n]\cup\\{0\\}$, let $\binom{\mathcal{A}}{k}$ denote all
subsets of $\mathcal{A}$ of size $k$ noting that because $\mathcal{A}$ is
countable, so is $\binom{\mathcal{A}}{k}$.

For each $k\in[n]\cup\\{0\\}$, let

$\displaystyle S_{k}$ $\displaystyle=\\{x\in X\colon\text{$x$ belongs to {\em
exactly} $k$ members of $\mathcal{A}$}\\}$ $\displaystyle S_{k}^{\prime}$
$\displaystyle=\\{x\in X\colon\text{$x$ belongs to {\em at least} $k$ members
of $\mathcal{A}$}\\}$

We will show that $S_{k}$ and $S_{k}^{\prime}$ are measurable.

To show that the $S_{k}^{\prime}$ are measurable, note that for any
$k\in[n]\cup\\{0\\}$, $S_{k}^{\prime}$ can be expressed as
$S_{k}^{\prime}=\bigcup_{\mathcal{F}\in\binom{\mathcal{A}}{k}}G_{\mathcal{F}}$.
This is because for any $x\in X$, if $x$ belongs to at least $k$ members of
$\mathcal{A}$, then there is a subset $\mathcal{F}\subseteq\mathcal{A}$ with
$\left\lvert\mathcal{F}\right\rvert=k$ such that
$x\in\bigcap_{A\in\mathcal{F}}A=G_{\mathcal{F}}$. Conversely, if
$x\in\bigcap_{A\in\mathcal{F}}A=G_{\mathcal{F}}$, then there is some
$\mathcal{F}\in\binom{\mathcal{A}}{k}$ (i.e. some
$\mathcal{F}\subseteq\mathcal{A}$ with $\left\lvert\mathcal{F}\right\rvert=k$)
such that $x\in G_{\mathcal{F}}=\bigcap_{A\in\mathcal{F}}A$, so $x$ belongs to
at least $k$ members of $\mathcal{A}$. Thus, since $\mathcal{A}$ is countable,
so is $\binom{\mathcal{A}}{k}$ (for each $k$) implying that each
$S_{k}^{\prime}$ is a countable union of measurable sets, so is itself
measurable.

To show the measurability of each $S_{k}$, first consider $k=n$. Observe that
$S_{n}=S_{n}^{\prime}$ because by assumption each $x\in X$ belongs to at most
$n$ members of $\mathcal{A}$, so it belongs to exactly $n$ members if and only
if it belongs to at least $n$ members. Thus, $S_{n}$ is also measurable.

Now for $k\in[n-1]\cup\\{0\\}$ observe that $S_{k}=S_{k}^{\prime}\setminus
S_{k+1}^{\prime}$ because some $x\in X$ belongs to exactly $k$ members of
$\mathcal{A}$ if and only if it belongs to at least $k$ members and does not
belong to at least $k+1$ members of $\mathcal{A}$. Thus, for
$k\in[n-1]\cup\\{0\\}$, $S_{k}$ is the set difference of two measurable sets,
so is itself measurable.

Finally, note that $\\{S_{k}\colon k\in[n]\cup\\{0\\}\\}$ is a partition of
$X$ (allowing the possibility that some $S_{k}$ are empty) because every point
of $x$ belongs to some number of members of $\mathcal{A}$, and that number is
(by assumption) between $0$ and $n$ inclusive.

Now we have the following chain of inequalities:

$\displaystyle\sum_{A\in\mathcal{A}}\mu(A)$
$\displaystyle=\sum_{A\in\mathcal{A}}\mu(A\cap X)$ ($A\subseteq X$ so $A\cap
X=A$)
$\displaystyle=\sum_{A\in\mathcal{A}}\mu\left(A\cap\left[\bigsqcup_{k\in[n]\cup\\{0\\}}S_{k}\right]\right)$
(Set equality; the $S_{k}$ partition $X$)
$\displaystyle=\sum_{A\in\mathcal{A}}\mu\left(\bigsqcup_{k\in[n]\cup\\{0\\}}\left[A\cap
S_{k}\right]\right)$ (Set equality)
$\displaystyle=\sum_{A\in\mathcal{A}}\left[\sum_{k\in[n]\cup\\{0\\}}\mu\left(A\cap
S_{k}\right)\right]$ (Countable additivity of measures)
$\displaystyle=\sum_{k\in[n]\cup\\{0\\}}\left[\sum_{A\in\mathcal{A}}\mu\left(A\cap
S_{k}\right)\right]$ (Interchange sums by interchange-of-countable-sums)
$\displaystyle=\sum_{k\in[n]\cup\\{0\\}}\left[k\cdot\mu\left(S_{k}\right)\right]$
(By exact-measure-of-multiplicity; see details below)
$\displaystyle=\sum_{k\in[n]}\left[k\cdot\mu\left(S_{k}\right)\right]$ ($k=0$
term is $0$)
$\displaystyle\leq\sum_{k\in[n]}\left[n\cdot\mu\left(S_{k}\right)\right]$
($k\leq n$) $\displaystyle=n\sum_{k\in[n]}\left[\mu\left(S_{k}\right)\right]$
(Linearity of summation)