%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{20}
\addbibresource{fpsac.bib}%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

% \newtheorem{thm}{Theorem}
% \newtheorem{lem}{Lemma}


%% define your title in the usual way
\title{Euler Characteristics of Exotic Configuration Spaces}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Yuliy Baryshnikov\thanks{\href{mailto:ymb@illinois.edu}{ymb@illinois.edu}. Partially supported by NSF grant DMS--1622370.}\addressmark{1,2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL, USA\\ \addressmark{2}Department of Mathematics, Kyushu University, Fukuoka, Japan}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Exponential generating function for Euler characteristics of configuration spaces have remarkably simple representation in terms of the local geometry of the underlying spaces. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Euler characteristics, configuration spaces, stratified spaces}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\input{abbs.tex}

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Configuration spaces -- the spaces of tuples of distinct,
distinguishable points in a topological space -- are important in
numerous applications, from dynamical systems to computer
science. The topology of such configuration spaces is relatively well
understood for manifolds, but for spaces with singularities, the
recorded knowledge is still quite limited.

In this note we will generalize several existing results dealing with the Euler
characteristics of certain (generalized) configuration spaces.

\subsection{Precursors}
We start with quoting some of those results.

\subsubsection{Configuration spaces of simplicial complexes}
Let $\spc$ be (the geometric realization of) a finite simplicial complex
\[
\spc=\amalg_\alpha \smpl_\alpha,
\]
where $\smpl_\alpha$ are the (relative)-open simplices of the triangulation.

For a finite set $\nset=\{1,\ldots,n\}$ of size \(n\), denote by $\conf(\spc,\nset)$ the conventional configuration space of $n$ distinct points, that is
\[
\conf(\spc,\nset):=\spc^\nset-\cup_{k\neq l}\Delta_{kl},
\]
where $\Delta_{kl}=\{\xx=(x_1,\ldots,x_n)\in\spc^\nset:x_k=x_l \}$ are the {\em big} diagonals in $\spc^\nset$.

For this setup, \cite{gal_euler_2001} proves the following 
\begin{thm}[S.~Gal]
The {\em exponential generating function} for the sequence of Euler characteristics of the configuration spaces of $\spc$ is given by
\be
\sum_{n\geq 0} \chi(\conf(\spc,\nset))\frac{z^n}{n!}=\prod_\alpha \left(1+(-1)^{d(\alpha)} (1-\chi(L(\alpha))) z\right)^{(-1)^{d(\alpha)}},
\ee
where the product is taken over all simplices of $\spc$, $d(\alpha)$ is the dimension, and $L(\alpha)$ is the {\em link} of the simplex $\smpl_\alpha$.
\end{thm}
(Here the link of a simplex $\smpl_\alpha$ is (the geometric realization of) the simplicial complex formed by all simplices of $\spc$ properly containing $\alpha$, or, equivalently, is the base of the cone obtained by the intersection of piece-wise linearly embedded $\spc$ with a small ball in a linear subspace transversally intersecting $\alpha$ at a single point,  around that point.)

\subsubsection{No-$k$-equal spaces}
Exponential generating function for Euler characteristics appeared also in the following setting.

Take  the real line as $\spc=\Real^1$, and consider the {\em no-$k$-equal} configuration spaces,
\be
\conf_k(\Real^1,\nset)=\Real^n-\cup_{I=(i_1<\ldots<i_k)}\Delta_I,
\ee
where $\Delta_I=\{x_{i_1}=x_{i_2}=\ldots=x_{i_k}\}$, are $k$-diagonals (of codimension $(k-1)$), and the union is taken over all such diagonals. In other words, the no-$k$-equal configuration space is obtained by forbidding all configurations of \(n\) points in \(\Real\) that have $k$ or more points coinciding.

These spaces appeared as an useful testing ground for topological lower bounds of complexity of linear decision trees, and were investigated intensely since their introduction (mostly from the viewpoint of the linear subspace arrangements theory).

One of the results of \cite{bjorner_linear_1994} can be formulated as follows:
\begin{thm}[A.~Bj\"orner, L.~Lovasz]
The exponential generating function for the Euler characteristics of no-$k$-equal spaces $\conf_k(\Real^1,\nset)$ is given by
\be\label{eq:BL}
\sum_{n\geq 0} \chi(\conf_k(\Real^1,\nset))\frac{z^n}{n!}=\frac{1}{1-z+z^2/2-\ldots + (-z)^{k-1}/(k-1)!}.
\ee
\end{thm}

\subsection{Colored configuration spaces}
The main result of this paper generalizes both theorems above. We work with {\em colored} configuration spaces.

\subsubsection{Colors and Ideals}
Fix a finite set $\clrs$ of {\em colors} of size $c$. The vectors in $\Nat^\clrs$ will be referred to as {\em color counts}.  

A subset of color counts $\ideal\in \Nat^\clrs$ is an {\em ideal} if for any $\mm=(m_1,\ldots,m_c)\in I$ and $\mm'\leq\mm$ (this notation shorthands for $m'_1\leq m_1,\ldots, m'_c\leq m_c$), the point $\mm'$ also lies in $\ideal$. We will be assuming that all the basis vectors of $\Nat^\clrs$ are in $\ideal$.

We will be considering finite collections of distinct colored points in $\spc$ numbered by the elements of \(\nset\).
If $I\subset\nset$, we will denote the corresponding color counts of points in $I$ as $\col(I)$.

\subsubsection{Ideals and Their Configuration Spaces}
Fix an ideal $\ideal$ (of permissible collisions).

\begin{dfn}
  For a collection $\nset$ of colored points, the configuration space $\conf_\ideal(\spc,\nset)$ is defined as
\be
\conf_\ideal(\spc,\nset)=\spc^\nset-\bigcup_{I: \col(I)\not\in\ideal}\Delta_I.
\ee
% (Clearly, these configuration spaces depend only on the color counts, hence the notation.)

As the configuration spaces for the collections of points with the same color count are natuarally equivalent, we will denote them sometimes as $\conf_\ideal(\spc,\nn)$, with $\nn=\col(\nset)$,
\end{dfn}

In words, the configuration space $\conf_\ideal$ prevents any collection of points in the configuration from coinciding if their color counts are outside of the ideal $\ideal$ of permissible collisions.

\begin{exm}
If $c=1$, and $\ideal=\{1\}$, we have the conventional configuration spaces. If $\ideal=\{1,2,\ldots,k-1\}$, we have the no-$k$-equal configuration spaces.

The bi-colored ($c=2$) ideal with $\ideal=\{(m,0), (0,m), m=0,1,\ldots\}$ forbids any points of different colors to collide, but allows that for any number of points of the same color (the ``apartheid'' ideal).
\end{exm}

\begin{dfn}
The {\em counting function} of the ideal $\ideal$ is
\be
\Phi_\ideal(\zz)=\sum_{\mm\in\ideal} \frac{\zz^\mm}{\mm!};
\ee
here $\zz=(z_1,\ldots,z_c); \zz^\mm=\prod_{k=1}^c z_k^{m_k}$ and $\mm!=\prod (m_k!)$.
\end{dfn}

\begin{exm}
For no-$k$-equal configuration space, $\Phi_\ideal(z)=1+z+z^2/2+\ldots+z^{k-1}/(k-1)!$.

For the ``apartheid ideal'', $\Phi_\ideal(z_1,z_2)=\exp(z_1)+\exp(z_2)-1$.
\end{exm}

\subsection{Main result}

To formulate our main result we need a few more definitions.

\subsubsection{Constructible Functions}
Let $\spc$ be a compact subanalytic set in $\Real^D$, with (finite) Whitney stratification		
\be\label{eq:main}
\spc=\amalg_\alpha \spc_\alpha.
\ee

We will refer to the functions constant on the strata of $\spc$ as {\em constructible} (for a background on constructible functions, see \cite{schapira_operations_1991}).

\subsubsection{Constructible Euler Characteristic}
\begin{dfn}
If $\spc$ is a subanalytic triangulated set in $\Real^D$, we will refer to the alternating sum of the numbers of simplices of each dimension as its {\em constructible Euler characteristic}, denoted $\chic(\spc)$. Equivalently, $\chic$ is the Euler characteristic computed as alternated sum of ranks of Borel-Moore cohomologies.
\end{dfn}

It is well known that $\chic$ is independent of the choice of triangulation, is therefore additive on subanalytic sets (i.e. $\chic(A)=\chic(A-B)+\chic(B)$ for subanalytic $B\subset A$), and matches the standard (homotopy-invariant) Euler characteristic on {\em compact} subanalytic sets. 

One can define the integral of a constructible function with compact support with respect to $\chic$ as 
\[
\int fd\chic=\sum_{s} s\chic(f^{-1}(s)),
\]
where the sum is taken over the (finite) range of \(f\), or, equivalently, as the evaluation of the direct image of the integrand under the mapping of $\spc$ to a point  -- see, e.g. \cite{gusein-zade_integration_2010}.

\begin{dfn}
For a constructible function $f$, its {\em dual} $f^\circ{}$ is defined as 
$$
{f}^\circ(x)=\int_\spc \one_{B(x,\eps)} f d\chic,
$$ 
where $\one_{B(x,\eps)}$ is the indicator function of the open Euclidean ball of radius $\eps>0$ around $x$ in $\Real^D$, and the integral is with respect to Euler characteristic (the integral stabilizes when $\eps$ is small enough, and thus is well-defined) .
\end{dfn}


For such a subanalytic space $\spc$ we set $\one=\one_\spc$ to be the indicator function of $\spc$. This is a constructible function, and its dual, 
\be
{\one}^\circ(x)=\chi(\spc\cap B_\epsilon(x))
\ee 
can be mundanely interpreted as the (constructible) Euler characteristic of the open ball of small enough radius $\epsilon$ around a point $x$ intersected with $\spc$ (again, this Euler characteristics stabilizes for small $\epsilon$). 
This, again, is a constructible function, i.e. is constant along the strata of $\spc$.
It is easy to see that \({\one}^\circ\) is supported by $\spc$.


\subsubsection{Main Result}
We have the following formula for the (standard, homotopy-invariant) Euler characteristic of the generalized configuration spaces:
\begin{thm}\label{thm:main}
The exponential generating function for the Euler characteristic of $\ideal$-configuration spaces is given by
\be
\sum_\mm \chi(\conf_\ideal(\spc,\mm))\frac{\zz^\mm}{\mm!}=\prod_\alpha\Phi_\ideal(\one^\circ{}(\alpha)\zz)^{(-1)^{d(\alpha)}\chi(\alpha)},
\ee
where the product is taken over all strata of $\spc$, $\one^\circ{}(\alpha)$ is the common value $\one^\circ{}(x)$ for the points of the stratum $\alpha$, $d(\alpha)$ is the dimension, and $\chi(\alpha)$ is the Euler characteristic of the stratum $\spc_\alpha$.
\end{thm}

Equivalently,

\begin{cor}\label{thm:main}
\be
\sum_\mm \chi(\conf_\ideal(\spc,\mm))\frac{\zz^\mm}{\mm!}=\prod_\alpha\Phi_\ideal(\one^\circ{}(\alpha)\zz)^{\chic(\alpha)},
\ee
where $\chic(\alpha)$ is the {\em constructible} Euler characteristic of the stratum $\spc_\alpha$.
\end{cor}

\subsection{Plan}
We start with a few examples of applications of the main result. In \cref{sec:proof} we will present an outline of the proof, drawing on the combinatorial and geometric results excised for space reasons. The full proof is available for now in a preprint form  \cite{ymb_page}.
%results addressed in \cref{sec:comb} and geometric results presented in \cref{sec:geo}.

\section{Examples}
\subsection{Gal's formula}
If $\spc$ is a triangulated space, embedded into some Euclidean space so that it is linear on each simplex. We consider $\spc$ as stratified by these simplices. For a point in a simplex of dimension $d$, the intersection of an open small ball with $\spc$ is homeomorphic to $\Real^d\times K$, where $K$ is the open cone with the base $L(x)$, the link of $\spc$ at $x$. Hence, 
\be
\dualone(x)=(-1)^d(1-\chi(L(x))).
\ee
For ``conventional'' configuration spaces, $\ideal=\{0,1\}$, and $\Phi_\ideal(z)=1+z$.
Substituting these identities into \eqref{eq:main} leads to
\be
\sum_n \chi(\conf(\spc,\nset)\frac{z^n}{n!}=\prod_\alpha (1+(-1)^{d(\alpha)}(1-\chi(L(\alpha)))z)^{(-1)^{d(\alpha)}},
\ee
i.e. Gal's formula.

\subsection{No-$k$-equal configuration spaces}
For no-$k$-equal spaces, the counting function is $\Phi_\ideal(z)=1+z+\ldots+z^{k-1}/(k-1)!=:e_k(z)$.

If $\spc$ is a $d$-dimensional disk, $\dualone=(-1)^d$ in the interior of the disk, and $0$ on the boundary. This implies
\be
\sum_n \chi(\conf_k(\Real^d,\nset))\frac{z^n}{n!}=e_k((-1)^dz)^{(-1)^d},
\ee
recovering, in particular, the formula \eqref{eq:BL}.

\subsection{Graphs}
If $\spc$ is a graph, i.e. geometric realization of a one-dimensional simplicial complex, one has, for any $\Phi_\ideal$,
\be
\sum_\nn \chi(\conf_\ideal(\spc,\nn))\frac{\zz^\nn}{\nn!}=\frac{\prod_{\alpha\in V(\spc)}\Phi_\ideal((1-v(\alpha))\zz)}{\Phi_\ideal^{|E(\spc)|}(-\zz)},
\ee
where the product is taken over the vertices $\alpha$, and $v(\alpha)$ stands for the degree of $\alpha$; $E$ is the set of the edges in the graph. (For conventional configuration spaces on graphs, see e.g. \cite{ghrist_configuration_2010}.)

We remark, in particular, that the leaf vertices do not contribute, and each degree $2$ vertex cancels one edge (as it should, to maintain the invariance of \(\conf_\ideal\) with respect to homeomorphisms).

\subsection{Manifolds}
If $\spc$ is a compact manifold of dimension $d$, one has but one stratum, and
\be\label{eq:mfld}
\sum_\nn \chi(\conf_\ideal(\spc,\nn))\frac{\zz^\nn}{\nn!}=\Phi_\ideal((-1)^d\zz)^{(-1)^d\chi(\spc)}.
\ee
In particular, for finite ideals $\ideal$ and even-dimensional manifolds, $\chi(\conf_\ideal(\spc,\nn))=0$ for large enough $\nn$ (and is \(\equiv 0\) for odd-dimensional manifolds).

\subsection{Bicolored spaces}
Consider now an example of configuration spaces with infinite ideals: the bi-colored apartheid ideal, with $\Phi_\ideal=\exp(z_1)+\exp(z_2)-1$. Using equation \eqref{eq:mfld}, we obtain
\be
\sum_{n_1,n_2} \chi(\conf_\ideal(S^2,(n_1,n_2)))\frac{z_1^{n_1}z_2^{n_2}}{n_1!n_2!}=(\exp(z_1)+\exp(z_2)-1)^2.
\ee
In particular, all Euler characteristics $\chi(\conf_\ideal(S^2,(n_1,n_2)))=2$ if $n_1,n_2\geq 1$.



\section{Proving the Main Result}\label{sec:proof}
\subsection{Setting the Stage}
Fix a finite set $\nset$ with colors attached to each of the points in $\nset$; set $\nn=\col(\nset)=(n_1,\ldots,n_c)$ to be the vector of color counts of $\nset$.

\subsubsection{Partitions}
We will denote the set of partitions of $\nset$ as $\prt(\nset)$. (A partition is an unordered collection of disjoint subsets of $\nset$ exhausting it.) 

Partitions of $\nset$, or, more generally, of any finite set $S$, are partially ordered by refinement: here we write $\sigma\prec \pi$ if $\sigma$ is a refinement of $\pi$, or $\pi$ is a coarsening of $\sigma$, that is if each bloc of $\sigma$ is contained entirely within a block of $\pi$.

The minimal (with respect to this refinement order) partition of $S$, consisting of singletons, will be denoted as $\zeros_S$, or just $\zeros$, when the context is clear.

The {\em join} of a family of partitions is the minimal common coarsening of the partitions in the family. 

The maximal element for the poset $\prt(S)$, denoted as $\ones_S$ is the partition with one block, $(S)$.

\subsubsection{Diagonals}
For each partition $\pi=(\pi_1)(\pi_2)\ldots(\pi_k)$ of $\nset$ into $k$ blocks, we will form the diagonal 
\be
\diag(\pi)=\{\xx: x_k=x_l \mbox{ if } k,l \mbox{ are in the same block of }\pi\}.
\ee
(Clearly, the diagonals form a lattice isomorphic to the lattice of partitions of $\nset$ with reversed order.)

\begin{dfn}
We define the collection $\fprt_\ideal(\nset)$ of {\em forbidden partitions} $\pi$ as such that for at least one block, the color count of this block is not in $\ideal$.
\end{dfn}

Then, by definition,
\be\label{eq:exclude}
\conf_\ideal(\spc,\nn)=\spc^\nset-\diag_{\fprt_\ideal},
\, \mathrm{where}\quad  \diag_{\fprt_\ideal}=\bigcup_{\pi\in\fprt_\ideal(\nset)} \diag(\pi).
\ee

\subsubsection{Enabling Additivity}
One certainly can find the (constructible) Euler characteristic of $\conf_\ideal$ using \eqref{eq:exclude} via additivity and some form of inclusion-exclusion principle. However this constructible $\chic$ is not equal to $\chi$ as $\conf_\ideal$ is not compact.

To circumvent this problem, we replace the diagonals in  \eqref{eq:exclude} by their appropriately chosen open vicinities (``fattenings'') in $\spc^\nset$. If the compact constructible complement to those vicinities is homotopy equivalent to the corresponding configuration space, we can use additivity of $\chic$ to compute $\chi(\conf_\ideal)$.

\subsubsection{Combinatorics and Geometry}
The combinatorial component of the computation is rather standard, and amounts to the manipulations of M\"obius function for the poset of partitions of colored sets of points. These computations allow one to reduce the problem to finding the constructible Euler characteristics of fattenings of diagonals. 
%The relevant results are proven in \cref{sec:comb}.

%\subsubsection{Geometry and the Rest} 
The geometric part of the proof involves definitions of the fattenings of the diagonals and computations of their Euler characteristics. Details are contained in the full version of this paper; here we will just formulate the relevant results.
%\cref{sec:geo}. Combining all the elements together leads to some formal power series manipulations which is shown below.


\subsection{Proof of the Main Theorem}
We start with straightening the geometry of \(\spc\).

\subsubsection{Cubical embedding}\label{sss:cube}
Namely, it will be convenient to {\em cubulate} the space $\spc$. Let $\cube=[0,1]\) be the unit interval.

\begin{prp}\label{prp:cube}
There exists a refinement of the stratification of $\spc$ which is homeomorphic to a subcomplex of the natural cubical complex of the unit cube $\cube^D$ in some Euclidean space.
\end{prp}
%The proof is given in \cref{sec:geo}.\qed

From now on, we will assume that $\spc$ is a cubical subcomplex of $I^D$, equipped with the metric induced from the $\sup$ norm on $\Real^D$.

\subsubsection{Deformation Retract}
For \(\xx\in\spc^\nset\), we define the partition \(\pi(\xx,\eps)\) as the partition into the classes of equivalence defined by
the transitive closure of the relation 
\[
x_k\sim x_l\Leftrightarrow |x_k-x_l| < \eps.
\] 

\begin{dfn}
We define ($\eps$-)fattening of \(\Ne(\pi)\) as the set of configurations \(\xx\in\spc^\nset: \pi\preceq \pi(\xx,\eps)\), and 
\[
\Ne(\ideal):=\bigcup_{\pi\in\fprt_\ideal(\nset)} \Ne(\pi).
\]
\end{dfn}

Clearly, $\Ne(\ideal)$ is an open vicinity of $\diag_{\fprt_\ideal}$.

Consequently,
\be\label{eq:ex_close}
\conf^\eps_\ideal(\spc,\nset)=\spc^\nset-\Ne(\ideal)
\ee
is a compact subset of $\conf_\ideal(\spc,\nset)$.

\begin{prp}\label{prp:retract}
Under the assumptions of \cref{sss:cube},
$\conf^\eps_\ideal(\spc,\nset)$ is a deformation retract of $\conf_\ideal(\spc,\nset)$.
\end{prp}
%The proof is given in \cref{sec:geo}.\qed

\subsubsection{Inclusion-Exclusion Formulae}

\begin{prp}\label{prp:c}
There exists a function $c_\ideal$ of partitions of $\nset$ such that
\be\label{eq:c}
\sum_{\sigma\preccurlyeq\pi} c_\ideal(\sigma)=\left\{ \begin{array}{rl}0 &\mathrm{if\ } \pi\in\fprt_\ideal(\nset),\\
1&\mathrm{otherwise}\end{array}\right.
\ee
For single blocks, this function depends only on the color content $c_\ideal(\nset)=c_\ideal(\col(\nset))$, and is multiplicative, in the sense that 
\be
c_\ideal((\pi_1)\ldots(\pi_k))=\prod_l c_\ideal(\col(\pi_l)).
\ee
\end{prp}
%The proof is in \cref{sec:comb}.\qed

\begin{lem}\label{lem:join}
For sufficiently small \(\eps\), the intersection lattice generated by the sets $\diag^\epsilon(\pi),\pi\in\prt(\nset)$ is isomorphic to the partition lattice on $\nset$: for any family of partitions $\{\pi_\lambda\}, \lambda=1,\ldots,\Lambda$, the fattening of their join $\pi=\pi_1\join\ldots\join\pi_\Lambda$ equals the intersection of the fattenings of the partitions in the family:
\be
\diag^{\epsilon}(\pi)=\bigcap \diag_\epsilon(\pi_k).
\ee
\end{lem}
\begin{proof}
This follows directly from the definition of fattenings $\diag^\eps(\pi)$.
\end{proof}
We remark that this implies that $\diag^{\epsilon}(\pi)\subset \diag^{\epsilon}(\pi')$ for any refinement $\pi'$ or $\pi$.

\cref{prp:c} and \cref{lem:join} allow us to represent the (topological) Euler characteristics in terms of the (constructible) Euler characteristics of the diagonal fattenings.

\begin{prp}\label{prp:decomp}
\be
\chi(\conf_\ideal(\spc,\nn))=\sum_{\pi\in\prt(\nn)}c_\ideal(\pi)\chic(\diag^{\epsilon}(\pi)).
\ee
\end{prp}
\begin{proof}
For $x\in \spc^\nset$ denote by $\pi(x)$ the coarsest partition $\pi$ for which $x\in N^\epsilon(\pi)$ (it exists by \cref{lem:join}). Then 
\be\label{eq:sum}
\sum_{\sigma\in\prt(\nn)}c_\ideal(\sigma)\one_{\diag^{\epsilon}(\sigma)}(x)=\sum_{\sigma\preceq \pi(x)}c_\ideal(\sigma)
\ee
which is $1$ exactly when $x\in \spc^\nset-\bigcup_{\pi\in\fprt_\ideal(\nset)} \diag^{\epsilon}(\pi)$. Invoking the additivity of the constructible Euler characteristics completes the proof.
\end{proof}

\subsubsection{Computations}
We will need also the multiplicativity of the Euler characteristics of $\diag^\eps(\pi)$:
\begin{lem}\label{lem:mult}
If $(\pi_1)\ldots(\pi_p)$ are the blocks of the partition \(\pi\), then
\[
\chic(\diag^\eps(\pi))=\prod_l \chic(\diag^\eps(\pi_l)).
\]
(Here the notation $\diag^\eps(\pi_l)$ is used to denote the fattening of the main diagonal in $\spc^{\pi_i}$ - remark that it depends only on the size of the block $\pi_l$.)
\end{lem}

\begin{proof}The fact that a subset $I=(k_1,\ldots,k_p)$ of $\nset$ belongs to a part of $\pi(\xx,\eps)$ depends only on the points $x_{k_1},\ldots,x_{k_p}$ implies that the set $\diag_\eps(\pi)$ is a product of its projections to $\spc^{\pi_k}$, over all parts of $\pi=(\pi_1)\cdots(\pi_p)$.
\end{proof}

\subsubsection{Partitions and Exponents}
The following Lemma is standard:
\begin{lem}\label{lem:exp}
Let $\kappa:\Nat^\clrs\to\Comp$ be an arbitrary valuation such that $\kappa(\zeros)=0$. Then
\[
\exp\left(\sum_\mm\frac{\zz^\mm}{\mm!} \kappa(\mm)\right)=\sum_\nn\frac{\zz^\nn}{\nn!}\sum_{\substack{\pi\in\prt(\nn)\\\pi=(\pi_1)\ldots(\pi_k)}}\prod_{l=1}^k\kappa(\nn(\pi_l)). 
\]
\end{lem}


\begin{proof}
See discussion of partitional composites of structures in \cite{bergeron1998combinatorial}.\end{proof}


Using \cref{prp:decomp}  we can transform the exponential generating function as
\be
F(\zz)=\sum_{\nn} \frac{\zz^\nn}{\nn!} \chi(\conf_{\ideal}(\spc,\nn))=\sum_{\nn} \frac{\zz^\nn}{\nn!}
\sum_{\substack{\pi\in\prt(\nn)\\\pi=(\pi_1)\ldots(\pi_k)}}\prod_{l=1}^k c_\ideal(\nn(\pi_l)) \chic(\diag^\eps(\pi_l)).
\ee

\begin{lem}%
\be\label{eq:kappa}
F(\zz)=\exp\left(\sum_{\mm>\zeros} \frac{\zz^\mm}{\mm!}c_\ideal(\mm) \chic(\diag^\eps(|\mm|))\right).
\ee

\end{lem}

\begin{proof}
Denoting
\[
\kappa(\mm):=c_\ideal(\mm) \chic(\diag^\eps(|\mm|)),
\]
and using \cref{lem:exp} as
\[
\exp\left(\sum_{\mm>\zeros}\frac{\zz^\mm}{\mm!} \kappa(\mm)\right)=\sum_\nn\frac{\zz^\nn}{\nn!}\sum_{\substack{\pi\in\prt(\nn)\\\pi=(\pi_1)\ldots(\pi_k)}}\prod_{l=1}^k\kappa(\nn(\pi_l))
\]
we arrive at the claim.
\end{proof}
\subsubsection{Euler Characteristic of Fattenings}
In view of \cref{lem:mult}, let us turn to $\chi(\Ne(S))$, where $S\subset\nset$ has size $|S|=:s$.

\begin{prp}\label{prp:ec}
The constructible Euler characteristic of $\Ne(S)$ is 
\[
\chic(\Ne(S))=\sum_{\mathrm{faces\ } \fc \mathrm{\ of\ }\spc}(-1)^\dim(\fc)\chic(B_\fc)^s=\sum_{\mathrm{faces\ } \fc \mathrm{\ of\ }\spc}\chic(\fc)\chic(B_\fc)^s,
\]
where the sum is taken over all open cubes $\fc$ of the cubulation of $\spc$, and $B_\fc$ is the intersection of small enough ball centered at a point of $\fc$ with $\spc$.
\end{prp}
\begin{cor}\label{cor:ec}
The Euler characteristic of $\Ne(S)$ is 
\be\label{eq:strata}
\chi(\Ne(S))=\sum_{\mathrm{strata\ } \spc_\beta \mathrm{\ of\ }\spc}(-1)^\dim(\spc_\beta)\dualone(\spc_\beta)^s,
\ee
where the sum is taken over all strata of $\spc$.
\end{cor}

\begin{proof}
Follows from \cref{prp:ec} and the immediate fact that along a stratum, the constructible Euler characteristic of the intersection of a small ball with the subanalytic space \(\spc\) does not depend on the simplex of a triangulation compatible with the stratification.
\end{proof}

\subsubsection{Final Strokes}
Substituting \eqref{eq:strata} into \eqref{eq:kappa} we obtain
\be
\sum_\mm \frac{\zz^\mm}{\mm!}\kappa(\mm)=\sum_\mm c_\ideal(\mm)\frac{\zz^\mm}{\mm!}\left(\sum_{\mathrm{strata\ } \spc_\beta}(-1)^\dim(\spc_\beta)\dualone(\spc_\beta)^{|\mm|}\right),
\ee
which after swapping the order of summations becomes
\be
\sum_{\mathrm{strata\ } \spc_\beta}(-1)^\dim(\spc_\beta)\left(\sum_\mm c_\ideal(\mm)\frac{(\dualone(\spc_\beta)\zz)^\mm}{\mm!}\right).
\ee

\begin{prp}\label{prp:log}
Under the assumptions on the ideal $\ideal$,
\be\label{eq:log}
\sum_{\mm>\zeros} c_\ideal(\mm)\frac{\zz^\mm}{\mm!}=\log\left(1+\sum_{\nn\in\ideal}\frac{\zz^\nn}{\nn!}\right).
\ee
\end{prp}
% The proof is given in \cref{sec:comb}.\qed

\begin{proof}[Finishing the proof of the Main Theorem:]
Plugging \eqref{eq:log} into \eqref{eq:kappa}, we obtain \cref{thm:main}.
\end{proof}

\iffalse

\section{Combinatorics}\label{sec:comb}


\subsection{Posets and M\"obius functions}


\subsubsection{M\"obius Inversion}
\begin{proof}[Proof of \cref{prp:c}]
The existence of the function $c_\ideal$ satisfying the conditions \eqref{eq:c} is immediate, as the conditions imposed on it are ``upper-triangular''. More explicitly, one can express $c_\ideal$ in terms of the M\"obius function of the poset of partitions:
\be
c_\ideal(\pi)=\sum_{\sigma\preceq \pi} \mu(\sigma,\pi) d_\ideal(\sigma),
\ee
where $\mu$ is the M\"obius function of the poset $\prt$, and $d_\ideal$ is the right hand side of \eqref{eq:c}, i.e. the indicator function that each block of $\pi$ has color counts in $\ideal$.

For $\pi=(\pi_1)\cdots(\pi_p)$, the poset of partitions refining $\pi$ is a direct product of the partitions of the blocks $\pi_k$ of $\pi$, and so the M\"obius function factors. Also, as follows from the definition, the indicator function that the partition $\pi$ is admissible is the product of indicator functions that each block is admissible. Therefore, $c_\ideal$ itself factors.
\end{proof}

Last combinatorial proof:
\begin{proof}[Proof of \cref{prp:log}:]
This, again, follows from \cref{lem:exp}: indeed, it implies that
\be
\exp\left(\sum_{\mm>\zeros} c_\ideal(\mm)\frac{\zz^\mm}{\mm!}\right)=\sum_\nn \frac{\zz^\nn}{\nn!} \sum_{\pi\in\prt(\nn)} c_\ideal(\pi),
\ee
the exponential generating function of sums
\[
\sum_{\pi\in\prt(\nn)} c_\ideal(\pi)
\]
over all partitions $\pi$ of a set of color counts $\nn$. This, by definition is $1$ exactly when $\nn\in\ideal$ or $\nn=\zeros$.
\end{proof}

%%%%%%%%%%%%%%%%% 9.11.3pm

\section{Geometry}\label{sec:geo}
\subsection{Simplifying the Space}
\subsubsection{Cubulations}
\begin{proof}[Proof of \cref{prp:cube}:]
Fix a finite triangulation of $\spc$ (existing for any subanalytic set, see, e.g. \cite{lojasiewicz_triangulation_1964}), and realize $\spc$ as a subcomplex of the unit simplex $\Sigma=\{\sum_j x_j=1,x_j\geq 0, j=1,\ldots,D\}\subset\Real^D$ in \(D\)-dimensional Euclidean space. Consider the mapping $s:\Sigma\to \cube^D$ given by
\be
s:\yy=(y_1,\ldots,y_D)\mapsto (\max_k y_k)^{-1}\yy.
\ee
It is bijective on its image, takes each simplicial face of $\Sigma$ into a union of faces of $\cube^D$, and respects adjacencies.
\end{proof}


To prove the deformation retraction of \cref{prp:retract} we will use a dynamical system on the $n$-dimensional cube $\cube^\nset$.
\begin{lem}\label{lem:flow}
There exists a smooth vector field $v(\zz)$ on $\cube^\nset=\{(z_1,\ldots,z_\nset), 0\leq k\leq 1, k=1,\ldots, \nset\}$ such that 
\begin{itemize}
\item the order of coordinates $\{z_k\}$ on the interval is preserved by the flow;
\item consequently, the diagonals $\{z_k=z_l\}$ are preserved by the flow;
\item the facets $\{z_k=0\}$ and $\{z_k=1\}$ of \(\cube^\nset\) are preserved by the flow;
\item the distances between the coordinates are increasing, unless they are at least $1/(n+1)$; 
\end{itemize}
\end{lem}
\begin{proof}
There are many options. The easiest to construct is the vector field defined on the simplices into which $\cube^\nset$ is partitioned by the big diagonals \(z_j=z_k\), i.e. the simplices consisting of vectors whose coordinates $z_k, k=1,\ldots,n$ are ordered in a particular way. Such a simplex can be coordinatized by the lengths of consecutive intervals $y_k:=z_{(k+1)}-z_{(k)}$ between the reordered coordinates $z_{(1)}\leq\ldots\leq z_{(n)}$, where $\{z_{(1)},\ldots,z_{(n)}\}=\{z_1,\ldots,z_n\}$ is a non-decreasing reordering of the coordinates (we also add $z_{(0)}:=0;  z_{(n+1)}:=1$).

To define the vector field on each of such $n$-dimensional simplices, we set
\be
\dot{y}_k=y_k\left(\sum_0^n y_l^2-y_k\right).
\ee
One can verify immediately that the flow preserves the simplex $\{y_k\geq 0; \sum_k y_k=1\}$, thus defining a vector field on the and that all the properties above are satisfied.
\end{proof}

\begin{proof}[Proof of \cref{prp:retract}] It is enough to construct a flow on $(\cube^D)^\nset$ which preserves $\spc^\nset$, and such that any trajectory starting at a point of the configuration space $\conf_\ideal(\spc,\nset)$ reaches the complement of $\Ne(\ideal)$. 

We represent $(\cube^D)^\nset$ as $(\cube^\nset)^D$ and apply the flows $v$ separately to each of the coordinate cubes \(\cube^\nset\), so that the evolutions of \(n\)-tuples of \(j\)-th coordinates of points in $\nset$ are independent and given by the vector field \(v\) constructed in \cref{lem:flow}. 

The trajectories of this flow will increase the nonzero gaps between the coordinates until they reach at least $1/(n+1)$.

If $\eps<1/(n+1)$, then the trajectories of a point outside a particular diagonal $\diag(\pi)$ will be eventually leave the vicinity $\Ne(\pi)$, with the exit point depending continuously on the initial point. This, clearly, proves the claim.  
\end{proof}

\subsection{Euler Characteristics of the Vicinities of Diagonals}
We will need a few intermediate constructions.

For $\xx\in\spc$, we denote by $\fc(x)$ the face of $\spc$ (which, again, we consider as a subcomplex of \(\cube^D\)) whose interior contains $x$.
 
\subsubsection{Vicinities of Faces of $\cube^D$}
By \cref{lem:mult}, to compute $\chic(\Ne(\pi))$, it is enough to prove \cref{prp:ec} computing the (constructible) Euler characteristics of 
the $\eps$-fattening of main diagonal in $\spc^S$ for finite subsets of $\nset$. 

For a face $\sigma$ of the cube $\cube^D$, we will denote by $\Se$ the $\sqrt{\eps}$-vicinity (in $\sup$-norm)
of that face in the cube. (We choose this size to go to $0$ with $\eps$, but to be asymptotically much larger than the size of the fattening of the diagonal we deal with.)

It is immediate that for $\eps<1/2$,
\be\label{eq:close}
\bigcap_k (\fc_k)_\eps=\left(\bigcap_k \fc_k\right)_\eps.
\ee

We denote by
\[
\bSe:=\Se-\cup_{\fc'\prec\fc} \fc'_\eps
\]
the rectified vicinity of the face $\fc$; clearly $\bSe$ is a product of (closed) $\sqrt{\eps}$-offset of $\fc$ times the $\sqrt{\eps}$-vicinity in the normal to $\fc$ subspace.
Obviously, the constructible sets $\bSe$ form a partition of $\cube^D$.

\subsubsection{Centers of Mass and their Sn appoints}

Let $S\in \nset$ be a nonempty subset. For a tuple of points $\xx=(x_1,\ldots,x_S)\in\spc^S\subset(\cube^D)^S$, define 
\[
m(\xx)=\frac1S\sum_{k=1}^S x_k\in\cube^D
\]
to be their their center of gravity.

We will call the (unique) face $\fc$ such that $m(\xx)\in\bSe$ the {\em snap point} of $\xx$, and denote it as $\fc(\xx)$.

\begin{lem} For$\eps$ small enough,
if $\fc(\xx)$ is the snap point of $\xx=(x_1,\ldots,x_s)\in\Ne(S)$, then all faces $\fc_k:=\fc(x_k)$ are adjacent to $\fc(\xx): \fc(\xx)\preceq \fc_k, k=1,\ldots,s$.
\end{lem}
\begin{proof} This follows immediately from \eqref{eq:close}.
\end{proof}

In particular, the snap point of $\xx\in\Ne(S)$ is in $\spc$, and we obtain partition of $\Ne(S)$ by the constructible sets
\be
\Ne(S)=\amalg_{\fc\in\spc} \SE, 
\ee
where
\be
\SE=\{\xx:\fc(\xx)=\fc\}.
\ee

Now we are ready to finish
\begin{proof}[the Proof of \cref{prp:ec}]
For $\xx\in\Ne(S)$, we denote by $\mu(\xx)$ the orthogonal projection of $m(\xx)$ to the snap point $\fc$ of $\xx$. Clearly, $\mu(\xx)\in \bSe$. Thus the constructible set $\SE$ is fibered over $bSe\cup\fc$. The fiber over a point $x\in \bSe$,
\be
K^\eps_x:=\{\xx\in\Ne: \mu(\xx)=x\}
\ee
is a constructible set. The tangent cone to $K^\eps_x$ splits into the subspace of $(T_x\fc)^S$ consisting of tangent vectors adding up to $0$, and $S$-th Cartesian power of the tangent cone $L_\fc$ to the intersection of normal space to $\fc$ with $\spc$. (Clearly, this tangent cone depends only on the face $\fc$, not on a specific point in its interior.)

Each ray along a vector in that tangent cone intersects $K^\eps_x$ over a half-open interval, and therefore 
\be
\chic(K_x^\eps)=(-1)^{\dim{fc}(s-1)} \chic(L_\fc)^s=(-1)^{\dim(\fc)} \chic(B_\fc)^s,
\ee
where $B_\fc$ is the constructible Euler characteristic of the intersection of a small ball centered a point in the interior of $\fc$ with $\spc$.

Now it remains to integrate the Euler characteristics of $K_s^\eps$ over all possible $x\in\bSe$ and apply the Fubini theorem.
This proves the claim.
\end{proof}
\fi

\acknowledgements{I am thankful to M. Farber who told me about S. Gal's result.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
