DIMACS TR: 93-35
Entropy spiltting hypergraphs
Author: Gabor Simonyi
ABSTRACT
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