The capacity of uniform hypergraphs can be defined as a natural generalization of the Shannon capacity of graphs. Corresponding to every uniform hypergraph there is a discrete memoryless channel in which the zero error capacity, in the case of the smallest list size for which it is positive, equals the capacity of the hypergraph, and vice versa. Also, the problem of perfect hashing can be considered as a hypergraph capacity problem. Upper bounds are derived for the capacity of uniform hypergraphs, using a technique developed earlier for perfect hashing based on the concepts of graph entropy and hypergraph entropy. These are subadditive functionals on probabilistic graphs and hypergraphs (i.e., graphs and hypergraphs within a probability distribution given on their vertex sets). A modified version of this technique is given, replacing graph entropy by another subadditive functional on probabilistic graphs. This functional can be considered as a probabilistic refinement of Lovasz's θg5-functional.
ON THE CAPACITY OF UNIFORM HYPERGRAPHS / Korner, Janos; Katalin, Marton. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - STAMPA. - 36:1(1990), pp. 153-156. [10.1109/18.50381]
ON THE CAPACITY OF UNIFORM HYPERGRAPHS
KORNER, JANOS;
1990
Abstract
The capacity of uniform hypergraphs can be defined as a natural generalization of the Shannon capacity of graphs. Corresponding to every uniform hypergraph there is a discrete memoryless channel in which the zero error capacity, in the case of the smallest list size for which it is positive, equals the capacity of the hypergraph, and vice versa. Also, the problem of perfect hashing can be considered as a hypergraph capacity problem. Upper bounds are derived for the capacity of uniform hypergraphs, using a technique developed earlier for perfect hashing based on the concepts of graph entropy and hypergraph entropy. These are subadditive functionals on probabilistic graphs and hypergraphs (i.e., graphs and hypergraphs within a probability distribution given on their vertex sets). A modified version of this technique is given, replacing graph entropy by another subadditive functional on probabilistic graphs. This functional can be considered as a probabilistic refinement of Lovasz's θg5-functional.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.