On the capacity of uniform hypergraphs
Authors:
- J. KornerJKJ. Korner
- K. MartonKMK. Marton
- 1 January 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 36 (1) , 153-156
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-functionalKeywords
This publication has 6 references indexed in Scilit:
- New Bounds for Perfect Hashing via Information TheoryEuropean Journal of Combinatorics, 1988
- Fredman–Komlós bounds and information theorySIAM Journal on Algebraic Discrete Methods, 1986
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- On Some Problems of Lovász Concerning the Shannon Capacity of a GraphIEEE Transactions on Information Theory, 1979
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956