Abstract
We show that the inequality H(A|B, X) + H(A|B, Y) ≤ H(A|B) for jointly distributed random variables A, B, X, Y, which does not hold in general case, holds under some natural condition on the support of the probability distribution of A, B, X, Y. This result generalizes a version of the conditional Ingleton inequality: if for some distribution I(X : Y|A) = H(A|X, Y) = 0, then I(A : B) ≤ I (A : B|X) + I(A : B|Y)+I(X : Y). We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K colors so that each two edges sharing a vertex have different colors and for each pair (left vertex x, right vertex y) there is at most one color a such both x and y are incident to edges with color a; assume further that the degree of each left vertex is at least L and the degree of each right vertex is at least R. Then K LR. The second application is a new method to prove lower bounds for biclique cover of bipartite graphs.