An invariant for hypergraphs (Q2565200)

Let \((V,\xi)\) be a hypergraph and \(\xi^*\) be the intersection closure of \(\xi\). Then \(\xi^*\) is a semilattice \(\text{L}(\xi)\) under the partial order relation \(x\leq y\) if and only if \(x\subseteq y\), for \(x\), \(y\in\xi^*\). For \(x\in\text{L}(\xi)\) let \(\text{FL}(x)=\{y:y\in \text{L}(\xi)\) and \(x\leq y\}\) be called the filter of \(\text{L}(\xi)\) generated by \(x\). Let \(c^+(x)\) be the number of components of \(\text{FL}(x)-x\) and \[ \ell(\xi)= 1+\sum_{x\in\text{L}(\xi)} (c^+(x)-1). \] The authors call this number, introduced by one of them in investigating the entropy theory of data bases, the Lee number, and prove that it is an invariant, in the sense that isomorphic hypergraphs have the same Lee number. An edge \(E_1\) of \(\xi\) is called an ear if there is another edge \(E_2\) such that the vertices of \(E_1-E_2\) belong to no edge of \(\xi\), other than \(E_1\). Removal of \(E_1\) from \(\xi\) is called an ear removal. The Graham reduction of \(\xi\) is the hypergraph obtained by repeated ear removals from it till no more ear removal is possible. A hypergraph is said to be acyclic if its Graham reduction is empty. The authors prove that \(\ell(\xi)\) is invariant under ear removal and deduce that \(\xi\) is acyclic if and only if \(\ell(\xi)=0\). The relation of the Lee number to the Möbius function and the Euler characteristic of the semilattice is discussed and the applicability to the design of data bases is hinted.