For a topological space $X$, its (colored) configuration space is the collection of $n$-tuples of distinct points in $X$, or, equivalently, \[\color{lightgray}{ \conf(X,n)=X^n-\bigcup_{i\neq j}\Delta_{ij}, }\] the $n$-th Cartesian power of $X$ with the union of the diagonals $\Delta_{ij}=\{x_i=x_j\}$ removed.

These spaces (and their uncolored relatives, ${\conf(X,n)/S_n}$), introduced by Fadell and Neuwirth, have numerous applications, in
partcular in quantum mechanics, Hamiltonian systems etc.

An archetypal example is the configuration space of $\Real^2$ - it has a long resume of wonderful properties, inter alia

- It is a $K(\pi,1)$ space for $\pi$ a colored braid group;
- its cohomology ring is generated by $1$-dimensional classes $\omega_{ij}$ and has quadratic relations (Arnol'd's relations);
- its Poincare polynomial is nice: \[ \sum \beta_k t^k=(1+t)\cdot\ldots\cdot(1+(n-1)t). \]

This space is also very important in theoretical robotics and beyond...

In this talk we will be dealing with exotic relatives of the classical configuration spaces, exemplified by *no-k-equal* spaces, introduced and studied by
Bjőrner and Lovasz.

We will be using $\nset=\{1,2,\ldots,n\}$.

No-k-equal space $\conf_k(X,n)$ of $X$ is the $n$-th Cartesian power of $X$ with its $k$-diagonals removed, \[ \conf_k(X,n)=X^n-\bigcup_{|I|=k}\Delta_I, \] where $I\subset \nset, I=\{i_1 < i_2 < \ldots < i_k \}$, and $\Delta_I=\{x_{i_1}=x_{i_2}=\ldots=x_{i_k}\}$.

One consider even more involved spaces.
We consider a finite collection $\types$ of types of points (particles). The interactions are encoded by a subset
$I\subset \Nat^\types$ of particle populations at a point which are allowed to co-locate
(that is
$$
\bn=(n_1,\ldots,n_{|\types|})\in I
$$
means that the having $n_f$ points of type $f\in \types$ at the same point $x$ is allowed).

We will concentrate on the case when $I$ is an ideal: for any
$\bn'\preceq\bn\in I$, one has $\bn'\in I$.

One typical example: particles of two types that are not allowed to coincide: \[ \conf_{11}(X, m,n)=X^m\times X^n-\bigcup_{i\in\nset, j\in\mset} \Delta_{ij}. \] Here we have $m$ points $(x_1,\ldots,x_m)\in X^m$ of type 1, $(x_1,\ldots,x_m)$, and $n$ points $(y_1,\ldots,y_n)\in X^n$ of the type 2, and the forbidden diagonals are \[ \Delta_{ij}=\{x_i=y_j\}\subset X^m\times X^n. \] (These configuration spaces were used by Segal, McDuff and others to study the space of harmonic maps of $S^2$ into spheres.)

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

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

If $X=\Real^d$, the spaces $\conf_k(X,n)$ are understood pretty well: they are examples of

A (central) subspace arrangement (over a filed $\fld$) is a union of linear subspaces in $V=\fld^n$, \[ \arrange=\bigcup_\alpha L_\alpha. \] The variety $V-\arrange$ is called the manifold of $\arrange$.We will denote the manifold of no-k-equal arrangement, over $\fld=\Real$ as $M^\Real_{n.k}$ (i.e. $\conf_k(\Real^1)$ in our nomenclature).

For the $\conf_k(\Real,n)=M^\Real_{n,k}$ space, we denote $\mathtt{(J_0) [I_1] (J_1)...[I_{m}](J_m)}$ (here $J_o,I_1,J_1,\ldots$ form a partition of $\nset$ with all $I_l$ of size $(k-1)$) the cell given by \[ \begin{array}{cl} x_{j} \geq & \mathrm{for}\quad j\in J_0\\ \geq x_{i_1}=\ldots=x_{i_{k-1}}\geq &\mathrm{for}\quad j\in I_1\\ \vdots & \\ \geq x_{j'}& \mathrm{for}\quad j'\in J_m\\ \end{array} \] We call the classes dual to the cells $\mathtt{(J)[I](J')}$ elementary.

The ring $H_*(M^\Real_{n,k})$ is the free commutative algebra generated by the elementary classes (of degree $(k-2)$) factored by \[\begin{align*} \ideal_1=&\langle\sum_{j\in J}(-1)^j\mathtt{(J-j)[I+j](J')}+\\ &\sum_{j'\in J'}(-1)^{j'}\mathtt{(J)[I+i'](J'-j')}\rangle \end{align*} \] and the quadratic ideal $\ideal_2$ generated by products of elementary cells having empty intersections.

Define a tidy cell $\mathtt{(J_0)[I_1](J_1)...}$ as such that the largest index in $I_k\cup J_k$ is in $J_k$ (in particular, all $J_k, k\geq 1$ are non-empty).Then $H^{m(k-2)}(M^\Real_{n,k})$ is spanned by the tidy cells with $m$ $\mathtt{[I]}$ blocks.

This allows one to deduce the exponential generating function for the Poincare polynomials of $M^\Real_{n,k}$:

\[ \sum_n P_n(t)\frac{z^n}{n!} =\frac{e^z}{1 +(-t)^{k-2}(e^z q_k(z) - 1)}, \] where \[ P_n(t))=\sum_m \beta_{m}(M^\Real_{n,k}) t^m \] and $q_k(z)=1-z+z^2/2!-\ldots \pm z^{k-1}/(z-1)!$.

One can see how much the Euler characteristics deviates from the total Betti number. Say, $\chi(M^\Real_{n,5})/n!\approx C_\chi(n) \times (1.9445443655968941..)^{-n}$, while $\beta(M^\Real_{n,5})/n!\approx C_\beta\times (1.889327221941516..)^{-n}$.

In general, to understand the cohomology structure even for the usual configuration spaces, even for manifolds is highly nonotrival
(Totaro described cohomologies for smooth complex projective varieties, though).

We would like to deal with arbitrary compact definable sets in some o-minimal structure (esiest is to think about semi-algebraic or semi-linear sets).

We however will aim at an easier task of understanding of Euler characteristic of the configuration spaces. Triangulation theorem allows us to assume that $X$ has a stratification satisfying local conicity condition, \[ X=\amalg_\sigma X_\sigma\]

Again, we consider a finite collection $\types$ of types of points (particles). The interactions are encoded by a subset $I\subset \Nat^\types$ of particle populations at a point so that $I=\bn\in\Nat^\types$ is a subset of all collections of type populations that can be colocated; To each ideal we associate the corresponding (exponential) generating function $$ \psi_I(\bz)=\sum_{\bn\in I} \frac{\bz^\bn}{\bn!} $$

$$\begin{align*} \psi_I=&1+x+y+x^2/2+xy +y^2/2+ \\ &+x^3/6+ y^3/6+x^4/24+x^5/120+x^6/720.\\ \end{align*} $$

In the assumptions above, for a compact definable $X$ equipped with a conic stratification, $X=\amalg_\sigma X_\sigma$, we have:

The exponential generating function for the Euler characteristics of the $I$-configuration spaces is given by $$\begin{align*} \sum_\bn& \chi(\conf_I(X,\bn)) \frac{\bz^n}{\bn!}=\\ &\prod_\sigma \psi_I(\bz\check{\one}(X_\sigma))^{(-1)^{\dim(X_\sigma)}\chi(X_\sigma^c)}. \\ \end{align*}$$

- the product in the right hand side is taken over all strata $X_\sigma$ of $X$;
- the compactification $X^c_\sigma$ are homeomorphic to the complement in $X$ to small tubular neighborhoods of adjacent strata, $$ X^c_\sigma=X_\sigma-\cup_{\sigma'\prec \sigma} N^\circ X_{\sigma'}; $$
- the constructible function $\check{\one}$ is Verdier dual to the constant function $\one = 1|_X$, or, equivalently, the (definable) Euler characteristics of a small ball around the point.

In particular, if $X$ is a manifold, the RHS reduces to $$ \psi_I((-1)^{\dim(X)}\bz)^{\chi(X)}. $$

The case of standard configuration spaces for simplicial complexes was considered by S. Gal (major motivation for this work). His formula $$ \sum_n \chi(\conf(X,n))\frac{z^n}{n!}= \prod_\sigma (1 + (−1)^{\dim(X_\sigma)}(1 − \chi(L_\sigma))z)^{(−1)\dim(X_\sigma)} $$ (where $L_\sigma$ is the normal link of the simplex $\sigma$) corresponds to $\psi_I=1+z$ for the ideal of the standard configuration spaces.

For three colors, $\chi(\conf(S^2,(m,n,p)))=0$ if $m,n,p>0$.

- Applications in robotics and CS generate a need in industrial grade computations of topological invariants for configuration spaces;
- Quite often, this can be done very explicitly;
- There are some interesting leads to follow - computing Betti numbers for no-k-equal spaces on graphs, rendering the theory in terms species of definable structures etc.