1

A Conditional Information Inequality and its
Combinatorial Applications
Tarik Kaced, Andrei Romashchenko, and Nikolay Vereshchagin

arXiv:1501.04867v4 [cs.IT] 13 Sep 2017

Abstract
We show that the inequality H(A|B, X) + H(A|B, Y ) 6 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) 6 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.
Keywords
Shannon entropy, conditional information inequalities, non Shannon type information inequalities, biclique cover, edge coloring

I. I NTRODUCTION
The most general and fundamental properties of Shannon’s entropy can be expressed in the language of linear inequalities.
The usual universal information inequalities (the linear inequalities that hold for Shannon’s entropies of jointly distributed tuples
of random variables for every distribution) have many equivalent characterizations and interpretations in very different areas
— these inequalities can be equivalently reformulated in the settings of Kolmogorov complexity and group theory; they give
characterizations of the network coding capacity rates, of the cardinalities of projections of finite sets, etc., see the surveys in [11],
[22]. The parallel and interplay between different “incarnations” of information inequalities lead to their better understanding
and to more efficient applications of this technique. However, there exists a class of less common information inequalities that
still lack a satisfactory explanation and have no clear combinatorial interpretation. These are the conditional linear information
inequalities, which hold only for distributions that satisfy some constraints. The first nontrivial example of a conditional linear
information inequality was proven in the seminal paper [6]; see a survey of other similar results in [24]. Until now, these
inequalities looked like artifacts without practical or theoretical application. In this paper, we argue that some conditional
inequalities can be naturally interpreted in purely combinatorial terms. We propose a new “conditional information inequality,”
discuss its combinatorial meaning, and show how it can be employed in purely combinatorial proofs.
Let A, X, Y be jointly distributed discrete random variables. In this paper, we consider the inequality
H(A|X) + H(A|Y ) 6

H(A),

(1)

where H(·) stands for Shannon’s entropy. For some A, X, Y this inequality is false, e.g., for constant X, Y and non-constant
A. We provide a natural condition on the distribution of A, X, Y implying inequality (1). Then we provide two combinatorial
applications of the resulting conditional inequality and show that it implies the conditional inequality from [21].
More specifically we consider the following condition:
for each quadruple a, a0 , x, y, if the probabilities of all four events
[A = a, X = x], [A = a, Y = y], [A = a0 , X = x], [A = a0 , Y = y]
are positive, then a = a0 .

(2)

Theorem 1. The inequality (1) holds for all random variables A, X, Y satisfying (2).
We first prove this theorem and then show its combinatorial applications.

While working on the paper the authors were in part supported by RFBR grants 14-01-93107, 16-01-00362, by an ANR-15-CE40-0016-01 grant RaCAF, and
by the Russian Academic Excellence Project ‘5-100’.
Tarik Kaced is with Université de Paris-Est Créteil, LACL, UPEC, France
Andrei Romashchenko is with LIRMM, CNRS & Univ. Montpellier
Nikolay Vereshchagin is with National Research University Higher School of Economics

2

II. N OTATION
To simplify formulas, we use the following notation for the marginal distributions (conditional and unconditional): p(a) denotes
Pr[A = a], p(a, x) = Pr[A = a, X = x], p(a|x) = Pr[A = a|X = x], p(a, y) = Pr[A = a, Y = y], and so on.
If X is a random variable and E is an event in the same probabilistic space (and Pr[E] > 0), we denote by X|E the conditional
distribution of X, i.e., the restriction of X on the subspace corresponding to the event E. For example, for jointly distributed
random variables (X, Y ) we denote by X|(Y = y) the conditional distribution of X under the assumption Y = y.
III. T HE PROOF OF T HEOREM 1
We apply the method of [6], [8]. The crucial property of inequality (1) is that no term contains both X and Y . The inequality (1)
can be re-written in terms of unconditional entropies as follows:
H(A, X) + H(A, Y ) 6 H(X) + H(Y ) + H(A).
Thus it means that the average value of the logarithm of the ratio
p(x)p(y)p(a)
p(a, x)p(a, y)

(3)

is less than or equal to 0. The average is computed with respect to the distribution p(a, x, y). Computing the average, we take
into account only the triples (a, x, y) with positive probability. For such triples, both the numerator and denominator of ratio (3)
are positive and hence its logarithm is well defined.
Now consider a new distribution p0 where
(
p(a,x)p(a,y)
if p(a) > 0,
0
p(a)
p (a, x, y) =
0
otherwise.
Random variables distributed according to p0 can be generated by the following process: First generate a using the original
distribution of A, then generate independently x using the conditional distribution x|a and y using the conditional distribution
y|a.
Notice that p0 (a, x, y) is positive if so is p(a, x, y) but not the other way around. However, ratio (3) is still well defined and
positive for all triples a, x, y with positive p0 (a, x, y). Therefore we can compute the average value of the logarithm of (3) using
the distribution p0 in place of p. Moreover, changing the distribution does not affect the average. Indeed, the logarithm of (3)
is the sum of logarithms of its factors. Thus it suffices to show that the average of the logarithm of each factor is not affected
when p is replaced by p0 . Let us prove this, say, for the factor 1/p(a, x).
This factor does not depend on y. Therefore the average of its logarithm does not depend on how p(a, x) is split among
p(a, x, y) for different values y: we just sum up log 1/p(a, x) over all a, x with weights p(a, x). As p(a, x) = p0 (a, x), summing
with weights p0 (a, x) will yield the same result.
By Jensen’s inequality1 the average value of the logarithm of the ratio (3) with respect to the distribution p0 is at most


X
log
p(x)p(y) .
a,x,y:p0 (a,x,y)>0

The condition (2) guarantees that for each x, y there is at most one a with p(a, x) > 0, p(a, y) > 0 and hence


X

X
log
p(x)p(y) 6 log
p(x)p(y) = log 1 = 0.
a,x,y:p0 (a,x,y)>0

x,y

IV. C OMBINATORIAL APPLICATIONS OF T HEOREM 1
A. A lower bound for the number of colors in edge colorings of bipartite graphs
An edge coloring of a graph is an assignment of colors to its edges so that each two edges sharing a node have different
colors. Finding the edge coloring number (the minimum possible number of colors in an edge coloring) of a given graph is
a classic problem of graph theory. The study of edge coloring is motivated by theoretical aspects of graph theory as well as
by numerous applications in information theory and computer science (mostly by different types of scheduling problems, see a
survey in [23]).
Vizing’s theorem [1] claims that the edge coloring number of a graph is either its maximum degree d or d + 1; for bipartite
graphs the number of colors is always d. From Theorem 1 we can derive a much stronger lower bound for edge colorings of
bipartite graphs satisfying the following constraint:

1 We need Jensen’s inequality for the logarithmic function: let p , . . . , p be positive numbers that sum up to 1; then p log x + · · · + p log x
n
n
n 6
1
1
1
log(p1 x1 + · · · + pn xn ).

3

Definition 1. Call an edge coloring of a bipartite graph rich if for each pair
hleft vertex x, right vertex yi
there is at most one color a touching both x and y (the latter means that there is an edge with color a incident to x and an
edge, maybe a different one, with color a incident to y).
From Theorem 1 we can derive the following bound for rich colorings of bipartite graphs:
Corollary 1. Assume that the degree of each left vertex in a given bipartite graph is at least L and the degree of each right
vertex is at least R. Then the number of colors in every rich edge coloring of the graph is at least LR.
Proof: Consider the uniform distribution on the set of edges of the graph. Denote by (A, X, Y ) the following triple of
jointly distributed random variables:
X = [the left end of the edge],
Y = [the right end of the edge],
A = [the color of the edge].
As the coloring is rich, the triple (A, X, Y ) satisfies (2): if both events [A = a, X = x] and [A = a, Y = y] have positive
probabilities, then both x and y are touched by a, and hence such a is unique. Therefore by Theorem 1 we have H(A|X) +
H(A|Y ) 6 H(A).
By construction, the distribution on the edges is uniform. Hence, for each vertex x, the conditional distribution of edges
incident to this x is also uniform. All edges incident to one and the same vertex must have different colors. So for every
fixed vertex x, all colors touching this x are equiprobable. In other words, conditional on X = x, the value of A is uniformly
distributed on the set of colors touching x. Thus, H(A|X) > log L. Similarly, we have H(A|Y ) > log R. By Theorem 1 we
have H(A) > log L + log R. It follows that the range of A is at least LR.
Remark 1. In fact this proof gives a stronger result. Let us call by the left and the right degrees of an edge (in a bipartite graph)
the degrees of its left and right ends. Denote by L̃ and R̃ the geometric means of the left and the right degrees of the graph’s
edges. That is, if the degrees of the vertices in the left part of the graph are l1 , . . . , ln and the degrees of the vertices in right
part of the graph are r1 , . . . , rm (l1 + . . . + ln = r1 + · · · + rm = e, where e is the number of edges), then
1/e

rm 1/e
L̃ := l1l1 · · · lnln
, R̃ := r1r1 · · · rm
.
The proof of Corollary 1 explained above implies that the number of colors in every rich edge coloring of the graph is at least
L̃R̃. Notice that L̃ > L and R̃ > R (these inequalities become equalities, if and only if the graph is uniform on the left or on
the right respectively).
In what follows we exhibit three examples of rich colorings. The first two examples are pretty trivial; in the third example,
Corollary 1 provides a non-trivial lower bound.
Example 1. For some bipartite graphs the lower bound LR proven in Corollary 1 is tight. Consider the simplest example: let
KR,L be the complete bipartite graph with R left and L right vertices so that the degree of each left vertex is exactly L and the
degree of each right vertex is exactly R (see in Fig. 1 an example for R = 3 and L = 4). This graph has LR edges. We may color
them into LR colors, each edge having its unique color. This coloring is rich, as for each pair hleft vertex x, right vertex yi
only the color of that edge touches both x and y.

Fig. 1.

Complete bipartite graph K3,4 .

For this example it is easy to compute directly the minimum number of colors in a rich coloring. Indeed, no different edges
(x1 , y1 ), (x2 , y2 ) can share a color, as in that case the pair x1 , y2 would violate the condition: the color of the edge (x1 , y2 )
also touches both x1 and y2 and is different from the shared color of (x1 , y1 ), (x2 , y2 ).
Example 2. In general, the lower bound from Corollary 1 is not optimal. To construct the simplest example, consider the complete
bipartite graph K3,3 and delete from this graph three edges forming a perfect matching, see Fig. 2. In this graph the degree of
each vertex is 2, so Corollary 1 claims that every rich coloring has at least 2 · 2 = 4 colors. However, it is easy to verify that
the optimal rich coloring has 5 colors: two edges (e.g., the pair of edges shown in bold in Fig. 2) may share a color, while each
of the remaining edge must have a unique color.

4

Fig. 2.

Complete bipartite graph K3,3 minus a perfect matching.

The next example is less obvious and exhibits a series of rich colorings for which Corollary 1 provides a non-trivial lower
bound.
Example 3. Assume that a finite family F of pair-wise disjoint squares inside the square [0; 1)2 in the Euclidean plane is given,
each square having the form [a; b) × [c, d). Assume that all vertices of those squares have rational coordinates 2 . Assume further
for each x ∈ [0; 1) there are at least L squares in F whose first projection includes x and similarly for each y ∈ [0; 1) there
are at least R squares in F whose second projection includes y (see Fig. 3). Then |F | > LR.

Fig. 3.

The square is partitioned into 10 disjoint squares so that each vertical or horizontal line intersects 3 squares.

Proof: Obviously, there is a natural N such that each of the given squares has the form [i/N ; j/N ) × [k/N ; l/N ) for integer
i, j, k, l 6 N . Consider the graph whose left and right nodes are rational numbers of the form i/N with 0 6 i < N . For each
given square [a; b) × [c, d) consider the diagonal {(a + t, c + t)|0 6 t < b − a = c − d}, see Fig 4. The edges of the graph are
j
11
10
9
8
7
6
5
4
3
2
1
0

11
10
9
8
7
6
5
4
3
2
1
0
0 1 2 3 4 5 6 7 8 9 10 11

11
10
9
8
7
6
5
4
3
2
1
0

i

Fig. 4.

Diagonals of the squares of the partition (points with rational coordinates (i/N, j/N ) for N = 12 and the corresponding bipartite graph).

those pairs (x, y) of nodes that lie on such diagonals. The edges of the resulting graph can be naturally colored into |F | colors:
the edges obtained from each diagonal are colored in a unique color. This coloring is rich: if the diagonal of a square has a
point of the form (x, ∗) and a point of the form (∗, y), then that square includes the point (x, y) and there is at most one such

2 This

assumption is added for technical simplicity and may be dropped.

5

square (the squares are disjoint). The left degree of the graph is at least L. Indeed, for each x0 ∈ [0; 1) of the form i/N there
are at least L squares whose first projection includes x0 (see the dashed vertical in Fig 4). For each such square [a; b) × [c, d)
its diagonal intersects the vertical segment {(x0 , y)|0 6 y < 1}, say, in the point (x0 , y0 ). Since both a, c have the form i/N ,
the number y0 = c + (x0 − a) also has this form and hence (x0 , y0 ) is an edge of the graph. Similarly, the right degree of the
graph is at least R (see the dashed horizontal line in Fig 4) and by Corollary 1 we have |F | > LR.
Historical remark: The study of edge colorings with additional constraints is by all means not new, see, e.g., strong edge
colorings [5], complete edge colorings [3], the Thue number of a graph [13], etc. Some versions of constraint edge coloring have
found direct applications in Information theory (e.g., [7], [15]). The problem concerned in Corollary 1 looks quite natural in the
context of the variety of edge coloring problems investigated in graph theory, though we are not aware of any earlier studies or
applications of this specific variant of edge coloring.
B. A lower bound for the biclique cover number of bipartite graphs
Definition 2. For any bipartite graph G = (V1 , V2 , E) (with the set of vertices V1 ∪ V2 and the set of edges E ⊂ V1 × V2 ) its
biclique cover number bcc(G) is defined as the minimal number of bicliques (complete bipartite subgraphs) that cover all edges
of G.
Biclique coverings play an important role in communication complexity. Specifically, the non-deterministic communication
complexity (see [14]) of a predicate
P : U × U → {0, 1}
can be defined as log bcc(G) for the bipartite graph G = (V1 , V2 , E), where V1 = V2 = U , and E is the set of all pairs
(x, y) ∈ U × U such that P (x, y) = 1.
Corollary 2. Assume that the edges of a bipartite graph G = (V1 , V2 , E) are colored in such a way that
(*) if edges (x, y 0 ) and (x0 , y) of the graph have the same color a, and the vertices x and y, as well as vertices x0 and y 0 ,
are also connected by edges, then the latter two edges also have color a.
Assume further that a probability distribution over the edges of the graph is given. Denote by (X, Y, A) the random variables
where
• X = [the left end of the edge],
• Y = [the right end of the edge],
• A = [the color of the edge].
1
Then bcc(G) > 2 2 (H(A|X)+H(A|Y )−H(A)) .
Proof: Assume that this graph G can be covered by t bicliques C1 , . . . , Ct . Extend the distribution (X, Y, A) and add
another random variable: we define Z as the index of a biclique Ci that covers the edge (X, Y ). (If an edge belongs to several
bicliques Ci , then we choose any of them.) Notice that Z ranges over {1, . . . , t}, so H(Z) 6 log t.
The crucial point is that for a fixed value i of Z the condition (2) is satisfied. Indeed, assume that both p(a, x|Z = i) and
p(a, y|Z = i) are positive. Then the biclique Ci has edges (x, y 0 ) and (x0 , y), both with color a. By property (∗) the color of
the edge (x, y) also equals a and hence such a is unique. By Theorem 1 for each conditional distribution (A, X, Y )|Z = i the
inequality (1) holds. Hence we get
H(A|X, Z) + H(A|Y, Z) 6 H(A|Z).
It follows that
H(A|X) − H(Z) + H(A|Y ) − H(Z) 6 H(A).
1
2 [H(A|X)+H(A|Y

)−H(A)]
.
Thus, we obtain t > 2H(Z) > 2
Example 4. Let us apply this corollary to a specific bipartite graph. Consider the bipartite Kneser graph KGn,k = (V1 , V2 , E),
where both parts V1 and V2 consist of k-elements subsets of {1, . . . , n}, and the set of edges E ⊂ V1 × V2 consists of all pairs
of disjoint sets. Let us color the edge (x, y) in color x ∪ y and consider the uniform probability distribution over the edges of
this graph. The condition (∗) is fulfilled. Indeed, assume we are given three pairs of disjoint k-element subsets: (x, y), (x, y 0 )
and (x0 , y). Assume further that x ∪ y 0 = x0 ∪ y = a. Then x = x0 and y = y 0 and hence x ∪ y = a as well. Hence
1

bcc(KGn,k ) > 2 2 [H(A|X)+H(A|Y )−H(A)] .


n
n
We have 2k
equiprobable colors and hence H(A) = log2 2k
. On the other hand, H(A|X) = H(A|Y ) = log2
s
2  
n−k
n
bcc(KGn,k ) >
/
.
k
2k

n−k
k



. Thus

6

2 n 

2k
If n  k then n−k
/ 2k is close to 2k
and we obtain a lower bound about 2k for bcc(KGn,k ). On the other hand, it
k
k ≈2
O(k+log log n)
is known that bcc(KGn,k ) 6 2
(see [14, Section 2.3]), so in the case Ω(log log n) 6 k  n these lower and upper
bounds are pretty close.
The proven bound in itself is
 of no interest; the simple and standard fooling set technique (see [14]) proves for this graph
the bound bcc(KGn,k ) > 2k
that holds for all n > 2k. However, this simple example illustrates the connection between
k
biclique cover and conditional information inequalities. It remains unknown whether a similar technique can surpass the fooling
set method for other examples of graphs.
Historical remark: In graph theory the minimum number of bicliques (complete bipartite subgraphs) needed to cover all edges
of a given graph is known as the biclique cover number or the bipartite dimension of a graph. The problem of computing the
bipartite dimension appears in different areas of computer science. In particular, the notions of bipartite partition and bipartite
cover play the central role in communication complexity, [14].
The problem of determining the bipartite dimension is NP-hard even for bipartite graphs, [4]. A good approximation or a
nontrivial lower bound for the bipartite dimension of some particular classes of graphs may imply substantial progress in various
problems of computational complexity, see [14], [16], [19], [20]. In Corollary 2 we proposed a new technique of lower bounds
for the bipartite dimension. Establishing formal relations between our method and previous approaches to biclique cover remains
an open problem.
V. A GENERALIZATION OF A CONDITIONAL INEQUALITY FROM [21]
In this section we show that Theorem 1 implies some conditional version of Ingleton’s inequality for entropies. So-called
Ingleton’s inequality was originally formulated and proven for ranks of linear subspaces, [2]. It turns out that a counterpart of
this inequality reformulated in terms of Shannon’s entropy (for random variables) has many nontrivial applications. Though in
general this inequality is not valid for entropies (see [10]), it holds for distributions that satisfy some special properties (e.g.,
for random variables that enjoy the property of extracting the mutual information, or for variables with some properties of
independence, see [6], [9], [12], [17], [18]). In particular, in [21] it was shown that Ingleton’s inequality for entropies holds for
all distributions where the entropies satisfy some linear constraints:
Theorem 2 ([21]). If random variables X, Y, A, B satisfy the the constraints
I(X : Y |A) = H(A|X, Y ) = 0,

(4)

I(A : B) 6 I(A : B|X) + I(A : B|Y ) + I(X : Y )

(5)

then Ingleton’s inequality

holds for this distribution.
A noteworthy fact is that this result cannot be obtained as a direct implication of any unconditional linear inequality for
Shannon’s entropy. More precisely, whatever pair of reals λ1 , λ2 we take, the inequality
I(A : B) 6 I(A : B|X) + I(A : B|Y ) + I(X : Y )+
+λ1 I(X : Y |A) + λ2 H(A|X, Y )
does not hold for some distribution, see [24].
We claim that Ingleton’s inequality holds also under condition (2), which is weaker than (4). Moreover, even a stronger
inequality than Ingleton’s inequality (namely the inequality (6) below), holds under condition (2).
Theorem 3. (i) Ingleton’s inequality (5) follows from the inequality
H(A|X, B) + H(A|Y, B) 6 H(A|B).

(6)

(ii) Inequality (6) holds for all random variables A, B, X, Y satisfying condition (2).
(iii) Condition (2) is implied by condition (4).
In brief, Theorem 3 states that (4) ⇒ (2) ⇒ (6) ⇒ (5). The main novelty is the middle implication (2) ⇒ (6), while the
implications (4) ⇒ (2) and (6) ⇒ (5) are almost straightforward (see the proof below) and the implication (4) ⇒ (5) was known
(Theorem 2).
Proof: (i) It is easy to verify that Ingleton’s inequality (5) can be equivalently rewritten as
H(A|X, B) + H(A|Y, B) 6 H(A|B) + I(X : Y |A) + H(A|X, Y ).

(7)

and hence follows from (6). Notice that under the constraints (4), Ingleton’s inequality is equivalent to (6).
(ii) Note that inequality (6) is a relativized version of (1) (the word relativization here means that we insert a new condition in
all entropy expressions). This similarity between inequalities (1) and (6) suggests that Theorem 2 can be deduced from Theorem 1.

7

The key observation is that condition (2) is “relativizable”: property (2) remains true if we restrict the initial probabilistic space
to some subspace.
Lemma. If a tuple of random variables (A, X, Y ) satisfies (2), then for each event E having positive probability the conditional
random variables of (A, X, Y )|E satisfy (2).
Proof: Assume that the four probabilities
Pr[X = x, A = a |E], Pr[Y = y, A = a |E],
Pr[X = x, A = a0 |E], Pr[Y = y, A = a0 |E]
are positive. Then the unconditional probability of each of these events is positive as well and hence a = a0 by (2).
Now we can show that (6) follows from condition (2). Indeed, for every possible value b of B the lemma guarantees that (2)
remains valid conditional on the event B = b. By Theorem 1 this implies
H(A|X, B = b) + H(A|Y, B = b) 6 H(A|B = b),
and taking the average over all values b we get (6).
(iii) Inequality I(X : Y |A) = 0 means that
p(a, x, y)p(a) = p(a, x)p(a, y)
for all triples a, x, y. Thus it implies that for each triple a, x, y of values of A, X, Y , if both probabilities p(a, x) and p(a, y) are
positive, then p(a, x, y) is also positive. Hence, if for some a, a0 , x, y all the four probabilities
p(a, x), p(a, y), p(a0 , x), p(a0 , y)
are positive (the assumption of (2)), then it follows that the probabilities p(a, x, y) and p(a0 , x, y) must be also positive.
Now we employ the condition H(A|X, Y ) = 0 (which means that the value of A is a deterministic function of (X, Y )). If
both probabilities p(a, x, y) and p(a0 , x, y) are positive, then a = a0 , and we obtain the conclusion of (2).
Note that in general inequality (6) is stronger than Ingleton’s inequality (5). For instance, let B be constant, let X, Y be
independent uniformly distributed random bits, and let A = X ⊕ Y . Then inequality (6) specializes to 1 + 1 6 1 and hence is
wrong, while Ingleton’s inequality (5) specializes to 0 6 0 + 0 + 0 (or to 1 + 1 6 1 + 1 + 0, if written in the form (7)) and
hence is true.
Note also that in general condition (2) is weaker than condition (4). For instance, let A be constant and let X, Y be any
dependent random variables.
ACKNOWLEDGMENT
The authors are grateful to Maxim Popov for valuable comments on a preliminary version of this paper. The authors thank
anonymous referees of IEEE Trans. Inform. Theory for many comments and suggestions.
R EFERENCES
[1] V. G. Vizing, “On an estimate of the chromatic class of a p-graph,” Diskret. Analiz., vol. 3, pp. 25–30, 1964.
[2] A. W. Ingleton, “Conditions for representability and transversability of matroids,” In Proc. Fr. Br. Conf 1970, pp. 62–67. Springer-Verlag, 1971.
[3] J. Bosák and J. Nešetřil, “Complete and pseudocomplete colorings of a graph,” Matematicky asopis Slovenskej Akadémie Vied, vol. 26, no. 3, pp. 171–184,
1976.
[4] J. Orlin, “Contentment in graph theory: covering graphs with cliques,” Indagationes Mathematicae, vol. 80, no. 5, pp. 406–424, 1977.
[5] J.-L. Fouquet and J.-L. Jolivet, “Strong edge-colorings of graphs and applications to multi-k-gons,” Ars Combinatorica, vol. 16 (A), pp. 141–150, 1983.
[6] Z. Zhang, R. W. Yeung, “A non-Shannon-type conditional information inequality,” IEEE Trans. Inf. Theory, vol. 43, pp. 1982–1986, 1997.
[7] C. Kaklamanis, P. Persiano, T. Erlebach, and K. Jansen, “Constrained bipartite edge coloring with applications to wavelength routing,” In Proceedings of
24th International Colloquium on Automata, Languages, and Programming (ICALP 97), Bologna, Italy, pp. 493–504, 1997.
[8] Z. Zhang, R. W. Yeung. “On characterization of entropy function via information inequalities,” IEEE Trans. Inf. Theory, vol. 44, no. 4, pp 1440–1452,
1998.
[9] F. Matúš, “Conditional independences among four random variables III: Final conclusion,” Combinatorics, Probability and Computing, vol. 8, pp. 269–276,
1999.
[10] D. Hammer, A. Romashchenko, A. Shen, N. Vereshchagin. “Inequalities for Shannon Entropy and Kolmogorov Complexity,” Journal of Computer and
System Sciences, vol. 60, pp. 442–464, 2000.
[11] R. W. Yeung, “A First Course in Information Theory,” Norwood, MA: Kluwer, 2002.
[12] K. Makarychev, Yu. Makarychev, A. Romashchenko, N. Vereshchagin, “A New Class of non-Shannon-type Inequalities for Entropies,” Comm. Inform.
Syst., vol. 2, no. 2, pp. 147–166, 2002.

8

[13]
[14]
[15]

[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]

N. Alon, J. Grytczuk, M. Hałuszczak, O. Riordan, “Nonrepetitive colorings of graphs,” Random Structures & Algorithms. vol. 21, no. 3–4, pp. 336–346,
2002.
E. Kushilevitz, N. Nisan.“Communication complexity,” Cambridge University Press, 2006.
C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, S. Thite, and S. Thulasidasan, “Strong edge coloring for channel assignment in wireless radio
networks,” Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops), p. 106,
2006.
S. Jukna, “On graph complexity,” Combinatorics, Probability and Computing, vol. 15, no. 6, pp. 855–876, 2006.
F. Matúš, “Infinitely many information inequalities,” Proc. IEEE Int. Symp. Inf. Theory, Nice, France, pp. 41–44, June 2007.
R. Dougherty, C. Freiling, K. Zeger, “Networks, matroids, and non-Shannon information inequalities,” IEEE Trans. Inf. Theory, vol. 53, no. 6, pp. 1949–
1969, 2007.
T. Lee and A. Shraibman, “Lower bounds in communication complexity,” Foundations and Trends in Theoretical Computer Science, vol. 3, no. 4,
pp. 263–399, 2009.
S. Jukna and A. S. Kulikov, “On covering graphs by complete bipartite subgraphs.” Discrete Mathematics, vol. 309, no. 10, pp. 3399–3403, 2009.
T. Kaced, A. Romashchenko, “On essentially conditional information inequalities,” Proc. IEEE Int. Symp. Inf. Theory, pp. 1935–1939, 2011.
R. W. Yeung, “Facets of entropy,” IEEE Information Theory Society Newsletter, vol. 62, no. 8, pp. 6–16, 2012.
P. Formanowicz and K. Tanaś, “A survey of graph coloring-its types, methods and applications,” Foundations of Computing and Decision Sciences, vol. 37,
no. 3, pp. 223–238, 2012.
T. Kaced, A. Romashchenko, “Conditional Information Inequalities for Entropic and Almost Entropic Points,” IEEE Trans. Inf. Theory, vol. 59, issue 11,
pp. 7149–7167, 2013.

