Minimal networks for sensor counting problem using discrete Euler calculus (Q2364357)

The paper is devoted to applications of the theory of integration with respect to Euler characteristics of finite partially ordered sets developed in [\textit{K. Tanaka}, Topology Appl. 204, 185--197 (2016; Zbl 1353.55013)]. \textit{Y. Baryshnikov} and \textit{R. Ghrist} proposed a method for enumerating targets lying on a sensor field using topological Euler integration in [SIAM J. Appl. Math. 70, No. 3, 825--844 (2009, Zbl 1190.90041)]. The paper under review proposes a method to reduce points in acyclic sensor networks enumerating targets using the integral theory with respect to Euler characteristic. \par Section 1 is devoted to the introduction and contains a history and summary of the main results. Section 2 contains the fundamental notions and properties of discrete Euler calculus. Let $(P,\leq)$ be a finite poset. A \textit{filter} $Q$ is a subposet of $P$ satisfying the implication: if $x\in Q$ and $y\in P$ with $x\leq y$, then $y\in Q$. Denote by $\mathcal{F}_P$ the set of all filters of $P$. For a filter $Q\subseteq P$, the \textit{incidence function} $\delta_Q: P\to \mathbb{Z}{Z}$ is defined by $\delta_Q(x)=1$ if $x\in Q$, and $\delta_Q(x)=0$ otherwise. \par Any function $f: P\to \mathbb{Z}{Z}$ can be written as a finite linear form $f= \sum_i a_i\delta_{Q_i}$ for some $a_i\in \mathbb{Z}{Z}$ and $Q_i\in\mathcal{F}_P$. The \textit{Euler calculus} or \textit{Euler integration} of $f$ is defined by $\int_P f d\chi= \sum_i a_i\chi(Q_i)$. (This does not depend on the choice of filter linear forms of $f$.) \par An \textit{acyclic sensor network} $(P,T,h)$ consists of a finite poset $(P,\leq)$, a subset $T$ of the set of all simplices in a Hasse diagram of $P$ considered as a one-dimensional simplicial complex, and a counting function $h: P\to {\mathbb{Z}{Z}}$. Elements $t\in T$ are called \textit{targets}. The function $h$ is obtained by the sensors detecting the targets. Denote by $T^{\sharp}$ the number of targets. \par Let $(P, T, h)$ be an acyclic sensor network. The number of targets is equal to the Euler calculus of the counting function: $\int_P h d\chi= T^{\sharp}$ (Theorem 2.1). \par In Section 3, the notion of a beat point of finite $T_0$-spaces is generalized. \par Let $P$ be a finite poset. Denote $P_{>x}= \{y\in P~ |~ y>x\}$. A point $x\in P$ is called a \textit{ $\chi$-point} if $\chi(P_{>x})=1$. The \textit{ $\chi$-minimal model} $P_{\chi}$ is a subposet of $P$ formed by removing all $\chi$-points one by one. The $\chi$-minimal model is uniquely determined (Corollary 3.1). \par Section 4 is devoted to the reduction of points in an acyclic network. \par For a map $f: P\to Q$ between finite posets and a function $h: Q\to \mathbb{Z}{Z}$, the \textit{ pullback} $f^*h$ is a function on $P$ defined by the composition $h\circ f$. \par An order-preserving map $f: P\to Q$ is \textit{$\chi$-distinguished} if the inverse image $f^{-1}(Q_{\geq x})$ has Euler characteristic 1 for all $x\in Q$. \par If $f: P\to Q$ is a $\chi$-distinguished map, then $\int_Q h d\chi = \int_P (f^*h) d\chi$ for any function $h$ on $Q$ (Theorem 4.1). If there exists a $\chi$-distinguished map between $P$ and $Q$, then $\chi(P)= \chi(Q)$ (Corollary 4.2). For any function $h$ on a finite poset $P$ we have $\int_{P}h d\chi= \int_{P_{\chi}}h|_{P_{\chi}} d\chi$ (Corollary 4.3). Let $h,h'$ be two functions on a finite poset $P$. If $h|_{P_{\chi}}= h'|_{P_{\chi}}$, then $\int_{P}h d\chi= \int_{P}h' d\chi$ (Theorem 4.2). So, even if the counting function returns wrong values on $\chi$-points, we can calculate the correct number of targets using the Euler calculus.