SCIENCE@home

Conditional Information Inequalities and Combinatorial Applications

Tarik Kaced,Andrei E. Romashchenko,N. Vereshchagin

Published 2015 in arXiv.org

ABSTRACT

We show that the inequality $H(A \mid B,X) + H(A \mid B,Y) \le H(A\mid 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 \mid A) = H(A\mid X,Y)=0$, then $I(A : B) \le I(A : B \mid X) + I(A: B \mid Y) + I(X : Y)$. We present two applications of our result. The first one is the following easy-to-formulate combinatorial theorem: assume that the edges of a bipartite graph are partitioned into $K$ matchings such that for each pair (left vertex $x$, right vertex $y$) there is at most one matching in the partition involving both $x$ and $y$; 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\ge LR$. The second application is a new method to prove lower bounds for biclique coverings of bipartite graphs.

PUBLICATION RECORD

  • Publication year

    2015

  • Venue

    arXiv.org

  • Publication date

    2015-01-20

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1501.04867
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-18 of 18 references · Page 1 of 1

CITED BY