A Conditional Information Inequality and Its Combinatorial Applications - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles IEEE Transactions on Information Theory Year : 2018

A Conditional Information Inequality and Its Combinatorial Applications

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.

Dates and versions

lirmm-01793775 , version 1 (16-05-2018)

Identifiers

Cite

Andrei Romashchenko, Tarik Kaced, Nikolai Vereshchagin. A Conditional Information Inequality and Its Combinatorial Applications. IEEE Transactions on Information Theory, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩. ⟨lirmm-01793775⟩
153 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More