DIMACS TR: 93-35

Entropy spiltting hypergraphs

Author: Gabor Simonyi


Hypergraph entropy is an information theoretic functional on a hypergraph with a probability distribution on its vertex set. It is sub-additive with respect to the union of hypergraphs. In case of simple graphs, exact additivity for the entropy of a graph and its complement with respect to every probability distribution on the vertex set gives a characterization of perfect graphs. Here we investigate uniform hypergraphs with an analoguous behaviour of their entropy. The main result is the characterization of 3-uniform hypergraphs having this entropy splitting property. It is also shown that for k>3 no non-trivial k-uniform hypergraph has this property.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-35.ps
DIMACS Home Page