Homology and Hypergraph Acyclicity: A Combinatorial Invariant For Hypergraphs

Abstract

The natural associations from finite hypergraphs and simple graphs to finite simplicial complexes are used to produce new hypergraph and graph invariants. This correspondence shows that alpha-acyclic hypergraphs and chordal graphs map to homologically acyclic complexes. A new degree of hypergraph acyclicity (h-acyclicity where the h keys homology) is introduced. It is shown that alpha-acyclic yields h-acyclic, and an example is given to show that this implication is not reversible. Application of these results to database design is discussed and a conjecture characterizing h-acyclic database schemes is stated.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1991
Accession Number
ADA241584

Entities

People

  • A. D. Parks
  • S. L. Lipscomb

Organizations

  • Naval Surface Warfare Center

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Availability
  • Classification
  • Databases
  • Families (Human)
  • Information Science
  • Naval Warfare
  • Numbers
  • Real Numbers
  • Relational Databases
  • Reversible
  • Security
  • Sequences
  • Standards
  • Surface Warfare
  • Universities
  • Warfare

Readers

  • Graph Algorithms and Convex Optimization.