An invariant for hypergraphs (Q2565200)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An invariant for hypergraphs |
scientific article |
Statements
An invariant for hypergraphs (English)
0 references
25 June 1997
0 references
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.
0 references
hypergraph
0 references
intersection closure
0 references
semilattice
0 references
data bases
0 references
Lee number
0 references
invariant
0 references
ear removal
0 references
Graham reduction
0 references
Möbius function
0 references
Euler characteristic
0 references