A Conditional Information Inequality and Its Combinatorial Applications
| Autor: | Nikolai K. Vereshchagin, Andrei Romashchenko, Tarik Kaced |
|---|---|
| Přispěvatelé: | Systèmes complexes, automates et pavages (ESCAPE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Department of Mathematical Logic and Theory of Algorithms, Lomonosov Moscow State University (MSU) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Information inequality Entropy Shannon entropy [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT] 020206 networking & telecommunications Biclique cover 02 engineering and technology Library and Information Sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Complete bipartite graph Computer Science Applications Combinatorics Edge coloring 0202 electrical engineering electronic engineering information engineering Bipartite graph Probability distribution 020201 artificial intelligence & image processing Conditional information inequalities Random variable Information Systems Mathematics |
| Zdroj: | IEEE Transactions on Information Theory IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩ |
| ISSN: | 0018-9448 |
| Popis: | We show that the inequality $H(A | B,X) + H(A | B,Y) \leqslant 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 \mskip 5mu {:} \mskip 5mu Y | A) = H(A | X,Y)=0$ , then $I(A \mskip 5mu {:} \mskip 5mu B) \leqslant I(A \mskip 5mu {:} \mskip 5mu B | X) + I(A \mskip 5mu {:} \mskip 5mu B | Y) + I(X \mskip 5mu {:} \mskip 5mu 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 \geqslant LR$ . The second application is a new method to prove lower bounds for biclique cover of bipartite graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|