An invariant for hypergraphs

DOI10.1007/BF02007730MaRDI QIDQ2565200zbMATH OpenFDO

Authors Tony T. Lee, Jianfang Wang

Publication date 25 June 1997

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02007730

zbMATH Keywords

data basesear removalEuler characteristicGraham reductionhypergraphintersection closureinvariantLee numberMöbius functionsemilattice

Mathematics Subject Classification ID

Hypergraphs (05C65)

Review text

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.

Recommendations

• Connections in acyclic hypergraphs
• On acyclic and cyclic hypergraphs
• The Euler formula of cyclomatic numbers of hypergraphs
• The cyclicity of a hypergraph

Cites work

• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• On the Desirability of Acyclic Database Schemes
• On the foundations of combinatorial theory I. Theory of M�bius Functions

Cited in

(10)

• Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
• Paths and cycles of hypergraphs
• Counting acyclic hypergraphs
• Homology cycles and dependent cycles of hypergraphs
• Enumeration of maximum acyclic hypergraphs
• Invariant subgraph properties in pseudo-modular graphs
• On axioms constituting the foundation of hypergraph theory
• no-homomorphism conditions for hypergraphs
• Hamiltonian decomposition of complete bipartite r-hypergraphs
• On the discovery of the cycle-axiom of hypergraphs

This page was built for publication: An invariant for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565200)