Skip to Main content Skip to Navigation
Journal articles

A Conditional Information Inequality and Its Combinatorial Applications

Andrei Romashchenko 1 Tarik Kaced 1 Nikolai Vereshchagin 2
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata
Contributor : Andrei Romashchenko <>
Submitted on : Wednesday, May 16, 2018 - 9:33:21 PM
Last modification on : Tuesday, January 19, 2021 - 1:07:20 PM

Links full text




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



Record views