Discrete Euler integration over functions on finite categories (Q272871): Difference between revisions

The theory of integration with respect to Euler characteristics of finite categories is provided. This is applied to enumerating the targets lying on a poset by sensors. Baryshnikov and Ghrist proved in [\textit{Y. Baryshnikov} et al., SIAM J. Appl. Math. 70, No. 3, 825--844 (2009; Zbl 1190.90041)] that the cardinality of the targets lying on a field can be obtained from the topological Euler integration of the counting function. In the paper, a discrete analogue of this result is obtained. Theorem 2.6. Let both \(A\) and \(B\) be either filters or ideals of a finite category \(C\). If each of \(A\), \(B\), and \(A\cap B\) has a Euler characteristic, then we have \(\chi(A\cup B)=\chi(A)+\chi(B)-\chi(A\cap B)\). In Section 3, \textit{constructive functions} \(f: C\to \mathbb{Q}\) on a finite category \(C\) are defined and \textit{measurable} finite categories are introduced. The definition of Euler integration of constructive functions on a measurable category is given. A number of results about the Euler integration on measurable categories is obtained (Theorem 3.12, Theorem 3.19). Section 4 is devoted to the application of discrete Euler integration to sensor network theory. Let \((P,\leq)\) be a partially ordered set. Its Hasse diagram is considered as a one-dimensional simplicial complex where \(0\)-simplices are elements \(p\in P\) and \(1\)-simplices are pairs \(p<q\) for which \(\{r\in P\mid p<r<q\}=\emptyset\). A \textit{network with sensors} is given by a finite partially ordered set \((P,\leq)\) and a subset \(T\) of the set of all simplices in its Hasse diagram. Elements \(t\in T\) are called \textit{targets}. A target \(t\in T\) is said to be \textit{below} a node \(r\in P\) if \(t\in P\) and \(t\leq r\) or \(t=(p<q)\) and \(q\leq r\). It is denoted by \(t\leq r\). Each \(p\in P\) has a \textit{sensor}. The sensors return the counting function \(h: P\to \mathbb{N}\cup \{0\}\) given by the cardinality of targets lying below it: \(h(p)=\{t\in T\mid t\leq p\}^{\sharp}\). Theorem 4.1. Given the counting function \(h: P\to \mathbb{N}\cup \{0\}\) for a collection of targets \(T\) in a network \(P\), we have \(T^{\sharp}=\int\limits_{P}h d\chi\).