Consider a $d$-dimensional discrete space with infinitely many cells. The Location of a cell is denoted by $x=(i_1,i_2,\dots,i_d)$ with $i_k \in \mathbb N$. Now I can define a function $\omega(x)$ that can take the values $0$ and $1$. If a cell is occupied by a "solid Body" then $\omega$ takes value $1$. If there is nothing on a cell with coordinate $y$ then it holds $\omega(y)=0$. With These conventions arbitrary discrete manifolds with "holes" can be constructed.

Now I have the topological invariant "Number of holes in the manifold" and I am tring to find a Connection between the function $\omega$ and the number of holes of arbitrary Dimension $N$. I am assuming that the "solid Body" (more mathematically: manifold) is distributed over the whole space and has no boundary. If $y$ is a cell which is empty and $y+z$ (the neighboring cell) is also empty with $z$ is a vector with one entry $1$ and Zeros elsewhere then cell $y$ belongs to the same hole as $y+z$. Is it possible to find an Expression $N(\omega)$?


I am trying to Count the number of holes by summing over the whole discrete space. Assuming that the holes are only single isolated point defects it holds clearly: $N= \sum_{i_1,\dots,i_d=0}^\infty (1-\omega(i_1,\dots,i_d))$. If there are more General holes then I think I can use also the Summation. However it must be distinguished whether an empty cell has also empty neighbor cells. The product $(1-\omega(y))(1-\omega(y+z))$ is $1$ if $y$ AND $y+z$ are empty cells and $0$ otherwise. These products (and also higher products for more General distinguishing whether multiple cells are ALL empty) must be involved in the sum over the whole disrete space. Also I think that prefactors must be introduced to absorb cells that are counted multiple times (e.g. $\frac{1}{2}$ absorbs cells that are counted twice). But here I am stuck. Any hints would be greatly appreciated.

  • $\begingroup$ Are you assuming that $\omega(x)=0$ for only finitely many $x$? (Otherwise there could be infinitely many "holes".) Also you start out with dimension $d$ (number of coordinates of each point $x$) and later ask about the number of holes of dimension $N.$ Is the dimension of a hole just another term for the number of cells in that hole? $\endgroup$ – coffeemath Apr 4 '15 at 11:33
  • $\begingroup$ I am assuming finitely many holes (I have assumed infinit because the manifold should have no boundary). The Dimension $d$ means that one has a grid in $d$ spatial dimensions; a $d$-dimensional space is subdivided into $d$-dimensional lattices. $\endgroup$ – kryomaxim Apr 4 '15 at 11:36

The key for solving this Problem is the inclusion-exclusion principle.

Considering a hole in the discrete grid, one can pick a cell of the hole. If the neighbor cells are also in the hole, the neighbors of the neighbor cell can be examined. Here also neighboring cells can belong to the hole. This procedure can be iterated arbitraryly.

Abbreviation: $\sigma(x) = 1- \omega(x)$.

As a simple example one can consider holes that are built up of 2 cells in Maximum. Then, the Expression obtained by the inclusion-exclusion rule $|A \cup B|=|A|+|B|-|A \cap B|$ can be expressed as: $\sigma(y)+\sigma(y+z)-\sigma(y)\sigma(y+z) = \sum_{x \in Hole}(\sigma(x)-\frac{1}{2} \sigma(x)\sigma(x+z(x)))$ ($z$ is the neighborhood function). For only a single cell hole this Expression is also true since $\sigma(y)\sigma(y+z)=0$. The factor $\frac{1}{2}$ arises because the same Expression appears twice when Summation is performed.

Now the General case can be derived analogously by the inclusion-exclusion formula:

$|\cup_{i=1}^n A_i| = \sum_{i=1}^n (-1)^{i+1}|A_{\tau(1)} \cap A_{\tau(2)} \cap \dots \cap A_{\tau(i)}|$.

All caps are equivalent to the Logical Operator AND. By regarding nested neighborhoods, the above formula can be used. Hence:

$\sigma(y) + \sigma(y+z(y)) + \dots + \sigma(y+z(...(z(y)))) - higher-orders$.

Also there can be introduced Summation over the whole hole and symmetry factors for the higher orders.

Am I on the right way? (I will highly appreciate every comments!)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.