$\def\conf{\mathtt{conf}} \def\cov{\mathtt{cov}} \def\Int{\mathbb{Z}} \def\Real{\Bbb{R}} \def\Comp{\mathbb{C}} \def\ZN{\Int_N} \def\attr{{\mathcal{A}}} \def\Rd{{\Real}^d} \def\cN{{\mathbf N}} \def\OO{{\mathcal O}} \def\DD{{\mathcal D}} \def\HH{{\mathcal H}} \def\NN{{\mathcal N}} \def\VV{{\mathcal V}} \def\domain{{\mathcal{B}}} \def\dom{{\mathcal{B}}} \def\ii{{\mathbf i}} \def\T{{\mathbb T}} \def\S{{\mathbb S}} \def\mod{{\mathit mod}} \def\Cycle{{\mathbf \sigma}} \def\prob{{\mathbb P}} \def\ex{{\mathbb E}} \def\codim{{\mathit{codim}}} \def\paths{{\mathcal P}} \def\sens{{\mathcal S}} \def\measurements{{\mathcal E}} \def\indep{{\mathcal I}} \def\one{\mathbb{I}} \def\dim{\mathtt{dim}} \def\nset{\mathbf{n}} \def\mset{\mathbf{m}} \def\Nat{\mathbb{N}} \def\types{\mathfrak{F}} \def\ideal{\mathcal{I}} \def\bz{\bar{z}} \def\bn{\bar{n}} \def\xtuple{\bar{x}} \def\arrange{\mathcal{A}} \def\fld{\Bbbk} \def\attr{\mathfrak{A}} \def\cdc{,\ldots,} $

on spaces of coverings

yuliy baryshnikov

university of illinois at urbana-champaign Mathematics and ECE

supported by onr


Spaces of coverings appear (if implicitly) in many applied problems. Usually, one covers a metric space with balls.
Here is a typical problem (tennis ball problem):

place randomly spherical caps of radius $r$ on the unit sphere. What is the probability that $n$ such caps fully cover the space?

This result (and most of other results in the area deal with the volume of the space of coverings. Here we concentrate on the topology.

Let us start with a formal definition. Let $X$ and $Y$ be two topological spaces, $X$ compact, and $R\subset X\times Y$ is a closed subset (relation).

The $n$-covering space (denoted as $\cov_n(X,Y;R)$, or just $\cov_n$) is the subset of $X^n$ given by

\[ \cov_n(X,Y)=\{(x_1,\ldots,x_n): \cup_k R_{x_k}=Y\} \] (here $R_x=\{y\in Y: (x,y)\in R\}$).

The primary example: coverings of a metric space by $r$ balls (also known as $r$-nets). Here $R=\{d(x,y)\leq r\}$, and $Y,X\subset Z$, some ambient metric space. We will denote in this case the space of coverings as $\cov_n(r)$.

One important tool to analyse the spaces of coverings is the tautological function. We will present the definition for the covering by the balls, but the same approach works in general.

For $\xtuple=(x_1,\ldots,x_n)\in X^n$, set \[ \tau(\xtuple)=\max_{y\in Y}\min_k d(x_k,y), \] the tautological function of the tuple $\xtuple$.
The role of $\tau$ is simple: the space $\cov_n(r)$ is the sublevel of $\tau$: \[\cov_n(r)=\{\xtuple:\tau(\xtuple)\leq r\}. \]

This, clearly, opens the door for applications of Morse theory.

For the coverings by balls in Euclidean space, the criticality of a tuple $\xtuple$ implies existence of the "stress graph".

Assume that $X=\Real^d$; $Y\subset \Real^d$ is a semialgebraic set, and $Y=\amalg_s Y_s$ is its Whitney stratification; the relation is given by $|x-y|^2\leq r^2$. We will refer this to as the geometric covering problem.

Stress graph is a bipartite graph with $n$ white vertices at $x_1\cdc x_n\in X$, some number of black vertices $y_1\cdc y_m\in Y$ and an array of positive coefficients $\mu_{k,l}\geq 0$ such that
  • for any $1\leq k\leq n$, $\sum_l \mu_{k,l}(x_k-y_l) =0;$ and
  • for any $1\leq l\leq m$, $\sum_k \mu_{k,l}(x_k-y_l)$ is orthogonal to $T_{y_l}Y_s$, where $Y_s$ is the stratum containing $y_l$.
  • for all $k,l$, \[ |x_k-y_l|=r. \]

A key necessary condition for $\xtuple$ to be a critical point of $\tau$ in the geometric covering problem is the existence of a critical graph:

If $\xtuple$ is critical, then a stress graph exists.


Topology of configuration spaces is relevant outside of physics. One particular class of examples comes from theoretical computer sciences via the Yao-Bjorner-Lovasz theory.
An algebraic decision tree is a computational model, based on "universal covering" of a flowchart. At each node, a polynomial of the input variables is computed. Leaves are marked by answers.

The total Betti number leads to lower bounds of the volume (depth) of the algebraic decision trees:

The depth of the algebraic decision trees deciding membership in a semi-algebraic set $C\subset \Real^d$ is bounded from below by \begin{equation} \Omega\left(\log \beta(C)\right) \end{equation} (the constants depending on the degrees of the polynomials $P_j$ and on the dimension $d$).

An alternative (weaker) estimate is through the Euler characteristics of $C$.

Another application comes from the control theory, where one is concerned with the dynamical systems \[ \dot{x}=f(x,u), \] with the speed of $x$ depending on $x$ itself and on controls $u\in U$. Assume some compact submanifold $\attr$ (a point, a periodic trajectory,...) with a tangent vector field $v$ is given.
Feedback stabilization to $\attr$ is a (piece-wise continuous) function $k:M\to U$ such that the dynamics defined by \[ \dot{x}=f(x,k(x)) \] coincides with $v$ on $\attr$ and has $\attr$ as an attractor.

It is immediate that feedback stabilization fails to exist, unless $\attr\sim_h M$.
The flow defined by $f(x,k(x))$ is necessarily discontinuous on some set (call it a cut corresponding to $k$).
How large or small a cut can be? One can show that the homology of the cut is defined by the mismatch of the homologies of $M$ and $\attr$.

covering an interval

Consider the simplest possible space of coverings: coverings of an interval by other intervals. We start with a simple example: $n=3$.

  • If $2r<1/3$, the space of coverings is, clearly, empty.
  • If $1/3\leq 2r\lt 1/2$, then the covering space is equivalent to a union of six points.
  • If $1/2\leq 2r\lt 1$, it is homotopic to a circle, and
  • If $1\leq 2r$, it is contractible.

In fact, this is a general phenomenon. Recall, that

An $n$-permutahedron $P_n$ is the the convex hull of a generic point in $\Real^n$, an $(n-1)$-dimensional polytope.
Define $k=n-\lceil 1/(2r)\rceil$, the slack of the covering of the unit interval by the intervals of length $2r$.
Theorem. The covering space of the unit interval by $n$ intervals of length $2r$ is homotopy equivalent of the $k$-skeleton of $P_n$.
Equivalently, $\cov_n(r)$ is homotopy equivalent to the complement of the (reduced) subspace arrangement in $\Real^{n-1}$ consisting of intersections of diagonal hyperplanes of codimension $(k+1)$ (the corresponding poset is the sublattice of the partition lattice with at least $(n-k)$ parts).

Proof of this theorem is quite simple: one constructs a flow of diffeomorphisms on $X^n$ having the properties

  • the tautological function $\tau$ decreases along the flow;
  • the $k$-skeleton is invariant under the flow, and
  • barycenters of the facets of $P_n$ are fixpoints of the flow.

Together, these properties imply the theorem.

Of course, the barycenters of the facets of $P_n$ also correspond to the critical points of the tautological function.

It is instructive to address the decision problem of $n\mathtt{-COVERAGE}$:

  • Input: sequence or reals $r; x_1,\ldots,x_n \in I=[0,1]$
  • Output: $\mathtt{YES}$ if intervals of length $2r$ centered at $x_l$ cover $I$; $\mathtt{NO}$ otherwise.

If the slack is fixed, and $n$ grows, the optimal algorithm takes $O(n\log{n})$ steps (realized by pre-sorting). If $(n-k)$ is small, an $O(n)$ algorithm exists.

Covering a planar domain

Consider a planar semialgebraic domain $\domain$. We are interested in the covering of the domain by the disks of radius $r$. Denote the space of such coverings as $\cov_n(r)$. Our goal is to understand the topology of this space of coverings.


Our main result here is the following:

The total Betti number $$ \beta(n;r):=\sum_{l}\beta_l(\cov_n(r)) $$ normalized by $n!$ is bounded by an exponent of $n$: $$ \beta(n;r)/n!=O(C^n) $$ for some $C>0$.

In other words, $n!$ term is the leading term in the asymptotic growth of $\beta(n;r)$.

The proof of this result consists of several steps.

The first is the standard Morse theory argument: the total Betti number of $\cov_n(r)$ is bounded by the sum of the local relative Betti numbers over all critical points (or, rather, connected components of the critical set) of $\tau$.

Here, the total Betti number of a critical set component (with the crtitical value $t_*=\tau(\xtuple)$) is the sum of the ranks of relative homology groups $$ H_l(\{\tau \leq t_*\}\cap U_\xtuple,\{\tau \lt t_*\}\cap U_\xtuple) $$ for some small open vicinity $U\ni\xtuple$, and a point $\xtuple\in X^n$ is non-critical if $\tau$ can be topologically trivialized near it.

Next step is to estimate the number of critical points.

The critical points correspond to the stress graphs, and the stress graphs plans for the geometric covering problem on the plane are planar, with the cells bounded by the edges of the graph convex.

One can show that the total number of the $y$ vertices in the stress graph is bounded by $3n$.

Now, it is known that the number of non-equivalent planar graphs on $N$ ordered vertices is asymptotic to $A_1 N! C_1^N$ for some $C>0$.

This implies that the total number of inequivalent planar graphs with $n$ ordered and $O(n)$ unordered vertices has the same asymptotics, $O(N!C_2^N)$.

For a given planar graph, to be realized as a stress graph (with the boundary vertices marked by the strata of the boundary of the domain $\dom$), the positions of the vertices have to satisfy a system of $O(n)$ polynomial equations, resulting in the bound $O(N!C_3^N)$ on the total number of critical values of the tautological function $\tau$.

Lastly, in the vicinity $U$ of a component of the critical set of $\tau$ with the critical value $t_*$, the total rank of local relative homology $H_*(\{\tau\leq t_*\}\cap U, \{\tau\lt t\}\cap U)$ is again bounded by an exponential in $n$, whence we obtain the result.

concluding remarks

Yet another example of covering spaces: planar grid domains covered by $l_\infty$ balls with excess 1 (i.e. the number of balls exceeds the minimal needed by 1).

One can check that this space of coverings has homotopy type of 1-dimensional complex. H. Wang found a general formula for the Euler characteristic of this space.

  • spaces of coverings are natural objects to consider, at least in metric spaces, and have numerous applications;
  • seem to exhibit the stat-mechanical scaling of the normalized total Betti number;
  • are one of new applied configuration spaces emerging as objects of study in various contexts lately.

thank you!