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 delta -functional.>

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This concept is at the core of a new bounding technique for graph covering problems and has furnished the best known bounds for the problem of perfect hashing. The basis of the technique is the sub-additivity of graph entropy with respect to the union of graphs. The tightness of the bounds depends on whether or not we have equality rather than just sub-additivity. As a first step in this analysis, we are investigating whether for a given graph G the entropies of G and $\bar G$ add up to the entropy of the complete graph on the same vertex set, i.e., the entropy of the underlying probability distribution. We shall prove that for a bipartite graph G and an arbitrary probability distribution P on its vertex set the entropies of G and $\bar G$ add up to the entropy of P. Related problems will be discussed. The results have interesting connections with the Ford–Fulkerson theory of network flows.

A probabilistic problem that arises for conflict resolution in random-access communication is treated. An earlier conjecture is disproved and a technique for finding lower bounds on the number of graphs of given structure needed to cover all edges of a given graph is developed.>

For a joint distribution{\rm dist}(X,Y), the functionT(t)=\min \{ H(Y|U): I(U \wedge Y|X)=O, H(X|U)\geq t\}is an important characteristic. It equals the asymptotic minimum of(1/n)H(Y^{n})for random pairs of sequences(X^{n}, Y^{n}), where\frac{1}{n} \sum ^{n}_{i=1}{\rm dist} X_{i} \sim {\rm dist} X, {\rm dist} Y^{n}|X^{n} = ({\rm dist} Y|X)^{n}, \frac{1}{n}H(X^{n})\geq t.We show that if, for(X^{n}, Y^{n})as given, the rate pair[(1/n)H(X^{n}),(1/n)H(Y^{n})]approaches the nonlinear part of the curve(t,T(t)), then the sequenceX^{n}is virtually memoryless. Using this, we determine some extremal sections of the rate region of entropy characterization problems and find a nontrivial invariant for weak asymptotic isomorphy of discrete memoryless correlated sources.

The blowing-up lemma says that if the probability with respect to a product measure of a setA\subseteq {\cal X}^{n} ({\cal X}finite,nlarge) is not exponentially small, then itsl_{n}-neighborhood has probability almost one for somel_{n} = O(n). Here an information-theoretic proof of the blowing-up lemma, generalizing it to continuous alphabets, is given.

How much separate information about two random binary sequences is needed in order to tell with small probability of error in which positions the two sequences differ? If the sequences are the outputs of two correlated memoryless binary sources, then in some cases the rate of this information may be substantially less than the joint entropy of the two sources. This result is implied by the solution of the source coding problem with two separately encoded side information sources for a special class of source distributions.

A coding theorem for the discrete memoryless broadcast channel is proved for the case where no common message is to he transmitted. The theorem is a generalization of the results of Cover and van der Meulen on this problem. The result is tight for broadcast channels having one deterministic component

A broadcast channel with one sender and two receivers is considered. Three independent messages are to be transmitted over this channel: one common message which is meant for both receivers, and one private message for each of them. The coding theorem and strong converse for this communication situation is proved for the case when one of the private messages has rate zero.

A technique is presented to determine the region of achievable rates for some source and channel networks. This technique is applied to the solution of a source:network problem that seems to be the simplest illustration of a new typical difficulty in coding for source networks: namely, when the same encoding of a source is required to meet the conflicting demands of 1) supplying side-information to the decoder of another source, and 2) providing direct-information to its own decoder in company with other side-information.

For discrete memoryless sources with a single-letter fidelity criterion, we study the probability of the event that the distortion exceeds a leveld, if for large block length the best code of given rateR > R(d)is used. Lower and upper exponential bounds are obtained, giving the asymptotically exact exponent, except possibly for a countable set ofRvalues.