# Complementary Graph Entropy, AND Product, and Disjoint Union of Graphs

Nicolas Charpenay  Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)
Rennes, FRANCE
<EMAIL_ADDRESS>Maël le Treust  Institut de Recherche en
Informatique
et Systèmes Aléatoires (IRISA)
Rennes, FRANCE
<EMAIL_ADDRESS>Aline Roumy  Institut National de Recherche
en Informatique et en Automatique (INRIA)
Rennes, FRANCE
<EMAIL_ADDRESS>
###### Abstract

In the zero-error Slepian-Wolf source coding problem, the optimal rate is
given by the complementary graph entropy $\overline{H}$ of the characteristic
graph. It has no single-letter formula, except for perfect graphs, for the
pentagon graph with uniform distribution $G_{5}$, and for their disjoint
union. We consider two particular instances, where the characteristic graphs
respectively write as an AND product $\wedge$, and as a disjoint union
$\sqcup$. We derive a structural result that equates
$\overline{H}(\wedge\>\cdot)$ and $\overline{H}(\sqcup\>\cdot)$ up to a
multiplicative constant, which has two consequences. First, we prove that the
cases where $\overline{H}(\wedge\>\cdot)$ and $\overline{H}(\sqcup\>\cdot)$
can be linearized coincide. Second, we determine $\overline{H}$ in cases where
it was unknown: products of perfect graphs; and $G_{5}\wedge G$ when $G$ is a
perfect graph, using Tuncel et al.’s result for $\overline{H}(G_{5}\sqcup G)$.
The graphs in these cases are not perfect in general.

##  I Introduction

We study the zero-error variant of Slepian and Wolf source coding problem
depicted in Figure 1, where the estimate $\widehat{X}^{n}$ must be equal to
$X^{n}$ with probability one. This problem is also called “restricted inputs”
in Alon and Orlitsky’s work [1].

###  I-A Characteristic graphs and optimal rate $\overline{H}$

An adequate probabilistic graph $G$ (i.e. a graph with an underlying
probability distribution on its vertices) can be associated to a given
instance of zero-error source coding problem in Figure 1, as in Witsenhausen’s
work [2]. This graph is called “characteristic graph” of the problem, as it
encompasses the problem data in its structure: the vertices are the source
alphabet, with the source probability distribution $P_{X}$ on these vertices,
and two source symbols $xx^{\prime}$ are adjacent if they are “confusable”,
i.e. $P_{X,Y}(x,y)P_{X,Y}(x^{\prime},y)>0$ for some side information symbol
$y$. By construction, the encoder must map adjacent symbols in $G$ to
different codewords in order to prevent any decoding error: the colorings of
the graph $G$ directly correspond to zero-error encoding mappings.

The best rate that can be achieved in the problem of Figure 1 with $n=1$ is
the minimal entropy of the colorings of $G$, as shown in [1]. This quantity is
called _chromatic entropy_ and is denoted by

$\displaystyle H_{\chi}(G)\doteq\inf\\{H(c(V))\>|\>c\text{ is a coloring of
}G\\}.$ (1)

The asymptotic optimal rate in the problem of Figure 1 is characterized by

$\displaystyle\overline{H}(G)=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}(G^{\wedge
n}),$ (2)

where $G^{\wedge n}$ is the $n$-iterated _AND product_ of the characteristic
graph $G$, see [1]. As shown in [3], it is equal to the _complementary graph
entropy_ defined in [4].

A single-letter formula for $\overline{H}$ is not known, except for perfect
graphs [5]; and for $G_{5}\sqcup G$ and its complement, for all perfect graph
$G$ [6], where $G_{5}$ is the pentagon graph with uniform distribution.

EncoderDecoder$Y^{n}$$\widehat{X}^{n}=X^{n}$$X^{n}$$\diagup$$R$ Figure 1:
Zero-error Slepian-Wolf source coding problem.

###  I-B Characteristic graph structure in particular instances

Since determining $\overline{H}$ is difficult, let us consider particular
instances of the problem in Figure 1, depicted in Figure 2. Both settings have
a characteristic graph with a specific structure. Thanks to the side
information at the encoder in Figure 2.a, the characteristic graph is the
_disjoint union_ ($\sqcup$) of a family of auxiliary probabilistic graphs
$(G_{z})_{z\in\mathcal{Z}}$; and in Figure 2.b the characteristic graph is the
_AND product_ ($\wedge$) of the $(G_{z})_{z\in\mathcal{Z}}$. Both $\sqcup$ and
$\wedge$ are binary operators on probabilistic graphs that play a central role
in this study. A natural question arises in the context of Figure 2: can we
determine the optimal rates if we only know $\overline{H}(G_{z})$ for all
$z\in\mathcal{Z}$? With the subadditivity results in [6, Theorem 2], we know
that
$\overline{H}\big{(}\bigsqcup_{z\in\mathcal{Z}}^{P_{g(Y)}}G_{z}\big{)}\leq\sum_{z\in\mathcal{Z}}P_{g(Y)}\overline{H}(G_{z})$
and
$\overline{H}\big{(}\bigwedge_{z\in\mathcal{Z}}G_{z}\big{)}\leq\sum_{z\in\mathcal{Z}}\overline{H}(G_{z})$
holds in general, however characterizing the cases where equality holds is an
open problem.

EncoderDecoder$Y^{n}$$\widehat{X}^{n}=X^{n}$$\big{(}g(Y_{t})\big{)}_{t\leq
n}$$X^{n}$$\diagup$$R$a.

Encoderb.Decoder$Y^{\prime n}_{1},...,{Y^{\prime
n}_{|\mathcal{Z}|}}$$\widehat{X^{\prime n}_{1}},...,\widehat{X^{\prime
n}_{|\mathcal{Z}|}}$$X^{\prime n}_{1},...,{X^{\prime
n}_{|\mathcal{Z}|}}$$\diagup$$R$

Figure 2: Two particular instances of zero-error Slepian-Wolf source coding
problem, where $g:\mathcal{Y}\rightarrow\mathcal{Z}$ is deterministic,
$(X^{\prime n}_{z},Y^{\prime n}_{z})\sim P^{n}_{X,Y|g(Y)=z}$ for all
$z\in\mathcal{Z}$, and the pairs $((X^{\prime n}_{z},Y^{\prime
n}_{z}))_{z\in\mathcal{Z}}$ are mutually independent. For all
$z\in\mathcal{Z}$, the auxiliary graph $G_{z}$ is Witsenhausen’s
characteristic graph for the pair $(X^{\prime}_{z},Y^{\prime}_{z})$.

###  I-C Related work

If the decoder wants to recover a function $f(X,Y)$ instead of $X$, the
setting of Figure 1 becomes the zero-error variant of the “coding for
computing” problem [7]. Charpenay et al. study in [8] the variant with side
information at the encoder, i.e. the setting from Figure 2.a with $f(X,Y)$
requested by the decoder. In [9], Ravi and Dey study a setting with a
bidirectional relay. In [10], Malak introduces a fractional version of
chromatic entropy in a lossless coding for computing scenario.

Another important problem is the Shannon capacity $\Theta$ of a graph [11],
which characterizes the optimal rate in the zero-error channel coding
scenario. Marton has shown in [12] that $\overline{H}(G)+C(G,P)=H(P)$, where
$P$ is the underlying probability distribution of $G$, and $C(G,P)$ is the
graph capacity relative to $P$. The same questions on linearization arise for
$\Theta$: for which $G,G^{\prime}$ do we have $\Theta(G\wedge
G^{\prime})=\Theta(G)\Theta(G^{\prime})$? A counterexample is shown by Haemers
in [13], using an upper-bound on $\Theta$ based on the rank of the adjacency
matrix. Refinements of Haemers bound are developed in [14] by Bukh and Cox,
and in [15] by Gao et al. Recently in [16], Schrijver shows that
$\Theta(G\wedge G^{\prime})=\Theta(G)\Theta(G^{\prime})$ is equivalent to
$\Theta(G\sqcup G^{\prime})=\Theta(G)+\Theta(G^{\prime})$. The computability
of $\Theta$ is investigated in [17] by Boche and Deppe. An asymptotic
expression for $\Theta$ using semiring homomorphisms is given by Zuiddam et
al. in [18]. In [19], Gu and Shayevitz study the two-way channel case. An
extension of $\Theta$ for secure communication is developed in [20] by Wiese
et al.

###  I-D Contributions

In this paper we link the complementary graph entropies of a disjoint union of
probabilistic graphs with that of their product, i.e.
$\overline{H}(\sqcup\>\cdot\>)$ and $\overline{H}(\wedge\>\cdot\>)$. First, we
show a structural result on the complementary graph entropy of a disjoint
union w.r.t. a type $P_{A}$, that makes use of $\wedge$ instead of $\sqcup$.
This enables us to equate $\overline{H}(\sqcup\>\cdot\>)$ and
$\overline{H}(\wedge\>\cdot\>)$ up to a multiplicative constant. This formula
has several consequences.

Firstly, we can derive with it a single-letter formula $\overline{H}$ of
products of perfect graphs. This case was unsolved as a product of perfect
graphs is not perfect in general. However, a disjoint union of perfect graphs
is perfect, this is why studying disjoint unions is the key. Finally, it
enables us to show that the linearizations of $\overline{H}(\sqcup\>\cdot\>)$
and $\overline{H}(\wedge\>\cdot\>)$ are equivalent; i.e. if equality holds for
either equation in Tuncel et al.’s subadditivity results [6, Theorem 2], then
equality also holds for the other one. We use this result to determine the
complementary graph entropy of the non-perfect probabilistic graph
$G_{5}\wedge G$ when $G$ is perfect.

In Section II, we define the graph-theoretic concepts we need to formulate our
main theorems in Section III, and their consequences in Section IV. An example
of application for these theorems is given in Section V, and the main proofs
are developed in Section VI, Section VII and Section VIII.

##  II Notations and definitions

We denote sequences by $x^{n}=(x_{1},...,x_{n})$.

The set of probability distributions over $\mathcal{X}$ is denoted by
$\Delta(\mathcal{X})$; $P_{X}\in\Delta(\mathcal{X})$ is the distribution of a
random variable $X$. The uniform distribution is denoted by Unif. The
conditional distribution of $X$ knowing $Y$ is denoted by $P_{X|Y}$.

A probabilistic graph $G$ is a tuple $(\mathcal{V},\mathcal{E},P_{V})$, where
$(\mathcal{V},\mathcal{E})$ is a graph and $P_{V}\in\Delta(\mathcal{V})$. A
subset $\mathcal{S}\subseteq\mathcal{V}$ is independent in $G$ if for all
$x,x^{\prime}\in\mathcal{S}$, $xx^{\prime}\notin\mathcal{E}$. A mapping
$c:\mathcal{V}\rightarrow\mathcal{C}$ is a coloring if $c^{-1}(i)$ is
independent for all $i\in\mathcal{C}$. The cycle, complete, and empty graphs
with $n$ vertices are respectively denoted by $C_{n}$, $K_{n}$, $N_{n}$.

######  Definition II.1 (AND product $\wedge$)

The AND product of $G_{1}=(\mathcal{V}_{1},\mathcal{E}_{1},P_{V_{1}})$ and
$G_{2}=(\mathcal{V}_{2},\mathcal{E}_{2},P_{V_{2}})$ is a probabilistic graph
denoted by $G_{1}\wedge G_{2}$ with:

  * -

$\mathcal{V}_{1}\times\mathcal{V}_{2}$ as set of vertices,

  * -

$P_{V_{1}}P_{V_{2}}$ as probability distribution on the vertices,

  * -

$(v_{1}v_{2}),(v^{\prime}_{1}v^{\prime}_{2})$ are adjacent if
$v_{1}v^{\prime}_{1}\in\mathcal{E}_{1}$ AND
$v_{2}v^{\prime}_{2}\in\mathcal{E}_{2}$; with the convention of self-adjacency
for all vertices.

We denote by $G_{1}^{\wedge n}$ the $n$-th AND power: $G_{1}^{\wedge n}\doteq
G_{1}\wedge...\wedge G_{1}$.

$1/4$$1/2$$1/4$$G_{1}=$$1/3$$2/3$$G_{2}=$$1/6$$1/12$$1/3$$1/6$$1/6$$1/12$$G_{1}\wedge
G_{2}=$$1/16$$1/8$$1/16$$1/4$$1/2$$G_{1}\\!\\!\\!\overset{\left(\frac{1}{4},\frac{3}{4}\right)}{\sqcup}\\!\\!\\!G_{2}=$
Figure 3: An empty graph $G_{1}=(N_{3},(\frac{1}{4},\frac{1}{2},\frac{1}{4}))$
and a complete graph $G_{2}=(K_{2},(\frac{1}{3},\frac{2}{3}))$, along with
their AND product $G_{1}\wedge G_{2}$ and their disjoint union $G_{1}\sqcup
G_{2}$ w.r.t. $(\frac{1}{4},\frac{3}{4})$.

######  Definition II.2 (Disjoint union $\sqcup$ of probabilistic graphs)

Let $\mathcal{A}$ be a finite set, and let $P_{A}\in\Delta(\mathcal{A})$. For
all $a\in\mathcal{A}$, let $G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{a}})$
be a probabilistic graph, their disjoint union w.r.t. $P_{A}$ is a
probabilistic graph $(\mathcal{V},\mathcal{E},P_{V})$ denoted by
$\bigsqcup^{P_{A}}_{a\in\mathcal{A}}G_{a}$ and defined by:

  * -

$\mathcal{V}=\bigsqcup_{a\in\mathcal{A}}\mathcal{V}_{a}$ is the disjoint union
of the sets $(\mathcal{V}_{a})_{a\in\mathcal{A}}$;

  * -

For all $v,v^{\prime}\in\mathcal{V}$, $vv^{\prime}\in\mathcal{E}$ iff they
both belong to the same $\mathcal{V}_{a}$ and $vv^{\prime}\in\mathcal{E}_{a}$;

  * -

$P_{V}=\sum_{a\in\mathcal{A}}P_{A}(a)P_{V_{a}}$; note that the
$(P_{V_{a}})_{a\in\mathcal{A}}$ have disjoint support in $\mathcal{V}$.

###### Remark II.3

The disjoint union $\sqcup$ that we consider here is also called “sum of
graphs” by Tuncel et al. in [6]. Note that $\sqcup$ is the disjoint union over
the vertices: it differs in nature from the union over the edges $\cup$ that
is already studied in the literature, in particular in [21], [5] and [12].

An example of AND product and disjoint union is given in Figure 3.

##  III Main result

In this section, $\mathcal{A}$ is a finite set, $P_{A}$ is a distribution from
$\Delta(\mathcal{A})$ and $(G_{a})_{a\in\mathcal{A}}$ is a family of
probabilistic graphs.

In Theorem III.2 we give an expression for the complementary graph entropy of
a disjoint union w.r.t. a type; the proof is given in Section III-A. With
Corollary III.3 we equate $\overline{H}(\sqcup\>\cdot\>)$ and
$\overline{H}(\wedge\>\cdot\>)$ up to a multiplicative constant when
$P_{A}=\operatorname*{Unif}(\mathcal{A})$.

######  Definition III.1 (Type of a sequence)

Let $a^{k}\in\mathcal{A}^{k}$, its type $T_{a^{k}}$ is its empirical
distribution. The set of types of sequences from $\mathcal{A}^{k}$ is denoted
by $\Delta_{k}(\mathcal{A})\subset\Delta(\mathcal{A})$.

###### Theorem III.2

If $P_{A}\in\Delta_{k}(\mathcal{A})$ for some $k\in\mathbb{N}^{\star}$ then

$\overline{H}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)=\frac{1}{k}\overline{H}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
kP_{A}(a)}\right).$ (3)

###### Corollary III.3

$\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{\operatorname*{Unif}(\mathcal{A})}G_{a}\big{)}=\frac{1}{|\mathcal{A}|}\overline{H}\left(\bigwedge_{a\in\mathcal{A}}G_{a}\right)$.

###  III-A Proof of Theorem III.2

In order to complete the proof, we need Lemma 1, it is the cornerstone of the
connection between $\overline{H}(\sqcup\>\cdot\>)$ and
$\overline{H}(\wedge\>\cdot\>)$. The main reasons why $\wedge$ appears in (4)
are the AND powers used in $\overline{H}$, and the distributivity of $\wedge$
w.r.t. $\sqcup$ (see Lemma 2). The proof of Lemma 1 is developed in Section
VI.

###### Lemma 1

Let
$(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}\in\mathcal{A}^{\mathbb{N}^{\star}}$
be any sequence such that $T_{\overline{a}^{n}}\rightarrow P_{A}$ when
$n\rightarrow\infty$. Then we have

$\overline{H}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{n}}(a)}\right).$ (4)

Now let us prove Theorem III.2. Let
$(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}$ be a $k$-periodic sequence such
that $T_{\overline{a}^{k}}=P_{A}$, then
$T_{\overline{a}^{nk}}=T_{\overline{a}^{k}}$ for all $n\in\mathbb{N}^{\star}$,
and $T_{\overline{a}^{n}}\underset{n\rightarrow\infty}{\rightarrow}P_{A}$. We
can use Lemma 1 and consider every $k$-th term in the limit:

$\displaystyle\overline{H}\Big{(}\textstyle\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\Big{)}$
$\displaystyle=\lim\limits_{n\rightarrow\infty}\frac{1}{kn}H_{\chi}\Big{(}\textstyle\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
knT_{\overline{a}^{kn}}(a)}\Big{)}$
$\displaystyle=\lim\limits_{n\rightarrow\infty}\frac{1}{kn}H_{\chi}\Big{(}\Big{(}\textstyle\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
kT_{\overline{a}^{k}}(a)}\Big{)}^{\wedge n}\Big{)}$
$\displaystyle=\frac{1}{k}\overline{H}\Big{(}\textstyle\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
kP_{A}(a)}\Big{)}.$

##  IV Consequences

###  IV-A Single-letter formula of $\overline{H}$ for products of perfect
graphs

With the exceptions of $G_{5}=(C_{5},\operatorname*{Unif}(\\{1,...,5\\}))$ and
$G_{5}\sqcup G$ and its complement when $\overline{H}(G)$ is known, the only
cases where $\overline{H}$ is known are perfect graphs with any underlying
distribution: it is given by the Körner graph entropy, defined below. We
extend the known cases with Theorem IV.6, which gives a single-letter
expression for $\overline{H}$ for AND products of perfect graphs. This case
was not solved before, as a product of perfect graphs is not perfect in
general (see Figure 4 for a counterexample). The proof of Theorem IV.6 is
developed in Section VIII.

0,00,10,20,30,40,51,01,11,21,31,41,52,02,12,22,32,42,53,03,13,23,33,43,54,04,14,24,34,44,55,05,15,25,35,45,56,06,16,26,36,46,57,07,17,27,37,47,5
Figure 4: This is the AND product of two perfect graphs $C_{6}$ and $C_{8}$.
The thick edges represent an induced subgraph $C_{7}$, which makes
$C_{6}\wedge C_{8}$ non perfect by the strong perfect graph Theorem (see
Theorem IV.4).

######  Definition IV.1 (Induced subgraph)

The subgraph induced in a graph $G$ by a subset of vertices $\mathcal{S}$ is
the graph obtained from $G$ by keeping only the vertices in $\mathcal{S}$ and
the edges between them, and is denoted by $G[\mathcal{S}]$. When $G$ is a
probabilistic graph, we give it the underlying probability distribution
$P_{V}/P_{V}(\mathcal{S})$.

######  Definition IV.2 (Perfect graph)

A graph $G=(\mathcal{V},\mathcal{E})$ is perfect if
$\>\forall\mathcal{S}\subset\mathcal{V},\;\chi(G[\mathcal{S}])=\omega(G[\mathcal{S}])$;
where $\omega$ is the size of the largest clique (i.e. complete induced
subgraph); and $\chi(G[\mathcal{S}])$ is the smallest $|\mathcal{C}|$ such
that there exists a coloring $c:\mathcal{S}\rightarrow\mathcal{C}$ of
$G[\mathcal{S}]$. By extension, we call perfect a probabilistic graph
$(\mathcal{V},\mathcal{E},P_{V})$ if $(\mathcal{V},\mathcal{E})$ is perfect.

######  Definition IV.3 (Körner graph entropy $H_{\kappa}$)

For all $G=(\mathcal{V},\mathcal{E},P_{V})$, let $\Gamma(G)$ be the collection
of independent sets of vertices in $G$. The Körner graph entropy of $G$ is
defined by

$\displaystyle H_{\kappa}(G)=\min_{V\in W\in\Gamma(G)}I(W;V),$ (5)

where the minimum is taken over all distributions
$P_{W|V}\in\Delta(\mathcal{W})^{\mathcal{V}}$, with $\mathcal{W}=\Gamma(G)$
and with the constraint that the random vertex $V$ belongs to the random
independent set $W$ with probability one, i.e. $V\in W\in\Gamma(G)$ in (5).

######  Theorem IV.4 (Strong perfect graph theorem, from [22])

A graph $G$ is perfect if and only if neither $G$ nor its complement have an
induced odd cycle of length at least 5.

######  Theorem IV.5 (from [5])

Let $G$ be a perfect probabilistic graph, then
$\overline{H}(G)=H_{\kappa}(G)$.

###### Theorem IV.6

When $(G_{a})_{a\in\mathcal{A}}$ is a family of perfect probabilistic graphs,
the following single-letter characterizations hold:

$\displaystyle\overline{H}\left(\bigwedge_{a\in\mathcal{A}}G_{a}\right)=\sum_{a\in\mathcal{A}}\overline{H}(G_{a})=\sum_{a\in\mathcal{A}}H_{\kappa}(G_{a}),$
(6)
$\displaystyle\overline{H}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)=\sum_{a\in\mathcal{A}}P_{A}(a)\overline{H}(G_{a})=\sum_{a\in\mathcal{A}}P_{A}(a)H_{\kappa}(G_{a}).$
(7)

###  IV-B Linearization of the complementary graph entropy

In their subadditivity result [6, Theorem 2], Tuncel et al. show that for all
probabilistic graphs $G_{1},G_{2}$ and $\alpha\in(0,1)$,

$\displaystyle\overline{H}(G_{1}\overset{(\alpha,1-\alpha)}{\sqcup}G_{2})\leq\alpha\overline{H}(G_{1})+(1-\alpha)\overline{H}(G_{2}),$
(8) $\displaystyle\overline{H}(G_{1}\wedge
G_{2})\leq\overline{H}(G_{1})+\overline{H}(G_{2}).$ (9)

We show in Theorem IV.7 that the cases where equality holds in (8) and (9)
coincide.

###### Theorem IV.7

For all probabilistic graphs $G_{1},G_{2}$, for all $\alpha\in(0,1)$, we have:

$\displaystyle\overline{H}(G_{1}\overset{(\alpha,1-\alpha)}{\sqcup}G_{2})=\alpha\overline{H}(G_{1})+(1-\alpha)\overline{H}(G_{2})$
(10) $\displaystyle\Longleftrightarrow\>$
$\displaystyle\overline{H}(G_{1}\wedge
G_{2})=\overline{H}(G_{1})+\overline{H}(G_{2}).$ (11)

We prove and use the more general formula stated in Theorem IV.8. The proof is
given in Section VII.

###### Theorem IV.8

Let $P_{A}\in\Delta(\mathcal{A})$ with full-support, then the following
equivalence holds

$\displaystyle\overline{H}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)=\sum_{a\in\mathcal{A}}P_{A}(a)\overline{H}(G_{a})$
(12) $\displaystyle\Longleftrightarrow\;\;$
$\displaystyle\overline{H}\left(\bigwedge_{a\in\mathcal{A}}G_{a}\right)=\sum_{a\in\mathcal{A}}\overline{H}(G_{a}).$
(13)

A case where equality holds in (12) is developed by Tuncel et al. in [6, Lemma
3]: $G_{5}\doteq(C_{5},\operatorname*{Unif}(\\{1,...,5\\}))$ along with any
perfect graph. We provide a single-letter formula for
$\overline{H}(G_{5}\wedge G)$ when $G$ is perfect; while $G_{5}\wedge G$ is
not perfect as $G_{5}\wedge G$ contains an induced $C_{5}$ (see Theorem IV.4).
The proof of the following Corollary is given in Appendix A.

###### Corollary IV.9

For all perfect probabilistic graph $G$,

$\displaystyle\overline{H}\big{(}G\wedge
G_{5})=\overline{H}(G)+\overline{H}(G_{5})=H_{\kappa}(G)+\textstyle\frac{1}{2}\log
5.$ (14)

##  V Example

In this section, for all $i\in\mathbb{N}^{\star}$, $G_{i}$ denotes the cycle
graph with $i$ vertices uniform distribution, i.e.
$G_{i}=\big{(}C_{i},\operatorname*{Unif}(\\{0,...,i-1\\})\big{)}$. Both
$G_{6}$ and $G_{8}$ are perfect, and as shown in Figure 4, $G_{6}\wedge G_{8}$
is not a perfect graph. We have:

$\displaystyle H_{\kappa}(G_{6})$ $\displaystyle=H(V_{6})-\max_{V_{6}\in
W_{6}\in\Gamma(G_{6})}H(V_{6}|W_{6})$ (15) $\displaystyle=1+\log 3-\log 3=1$
(16)

as $H(V_{6}|W_{6})$ in (15) is maximized by taking $W_{6}=\\{0,2,4\\}$ when
$V_{6}\in\\{0,2,4\\}$, and $W_{6}=\\{1,3,5\\}$ otherwise.

Similarly, $H_{\kappa}(G_{8})=1$.

We can use Theorem IV.5 to find $\overline{H}(G_{6}\wedge G_{8})$:

$\displaystyle\overline{H}(G_{6}\wedge
G_{8})=H_{\kappa}(G_{6})+H_{\kappa}(G_{8})=2.$ (17)

We can build an optimal coloring of $G_{6}\wedge G_{8}$,
$c^{*}:(v_{6},v_{8})\mapsto(\mathds{1}_{v_{6}\text{ is
even}},\mathds{1}_{v_{8}\text{ is even}})$.

##  VI Proof of Lemma 1

###  VI-A Preliminary results

Lemma 2 establishes the distributivity of $\wedge$ w.r.t. $\sqcup$ for
probabilistic graphs, similarly as in [18] for graphs without underlying
distribution. Lemma 3 states that $\overline{H}$ can be computed with
subgraphs induced by sets that have an asymptotic probability one, in
particular we will use it with typical sets of vertices. The proofs of Lemma 2
and Lemma 3 are respectively given in Appendix C and Appendix D.

###### Lemma 2

Let $\mathcal{A},\mathcal{B}$ be finite sets, let
$P_{A}\in\Delta(\mathcal{A})$ and $P_{B}\in\Delta(\mathcal{B})$. For all
$a\in\mathcal{A}$ and $b\in\mathcal{B}$, let
$G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{a}})$ and
$G_{b}=(\mathcal{V}_{b},\mathcal{E}_{b},P_{V_{b}})$ be probabilistic graphs.
Then

$\displaystyle\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)\wedge\left(\bigsqcup_{b\in\mathcal{B}}^{P_{B}}G_{b}\right)=\bigsqcup_{(a,b)\in\mathcal{A}\times\mathcal{B}}^{P_{A}P_{B}}G_{a}\wedge
G_{b}.$ (18)

###### Lemma 3

Let $G=(\mathcal{V},\mathcal{E},P_{V})$, and
$(\mathcal{S}^{n})_{n\in\mathbb{N}^{\star}}$ be a sequence of sets such that
for all $n\in\mathbb{N}^{\star}$, $\mathcal{S}^{n}\subset\mathcal{V}^{n}$, and
$P^{n}_{V}(\mathcal{S}^{n})\rightarrow 1$ when $n\rightarrow\infty$. Then
$\overline{H}(G)=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\big{(}G^{\wedge
n}[\mathcal{S}^{n}]\big{)}$.

######  Definition VI.1 (Isomorphic probabilistic graphs)

Let $G_{1}=(\mathcal{V}_{1},\mathcal{E}_{1},P_{V_{1}})$ and
$G_{2}=(\mathcal{V}_{2},\mathcal{E}_{2},P_{V_{2}})$. We say that $G_{1}$ is
isomorphic to $G_{2}$ if there exists an isomorphism between them, i.e. a
bijection $\psi:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$ such that:

  * -

For all $v_{1},v_{1}^{\prime}\in\mathcal{V}_{1}$,
$v_{1}v^{\prime}_{1}\in\mathcal{E}_{1}\Longleftrightarrow\psi(v_{1})\psi(v^{\prime}_{1})\in\mathcal{E}_{2}$,

  * -

For all $v_{1}\in\mathcal{V}_{1}$,
$P_{V_{1}}(v_{1})=P_{V_{2}}\big{(}\psi(v_{1})\big{)}$.

######  Lemma 4 (from [8])

Let $\mathcal{B}$ be a finite set, let $P_{B}\in\Delta(\mathcal{B})$ and let
$(G_{b})_{b\in\mathcal{B}}$ be a family of isomorphic probabilistic graphs,
then
$H_{\chi}\big{(}\bigsqcup_{b^{\prime}\in\mathcal{B}}^{P_{B}}G_{b^{\prime}}\big{)}=H_{\chi}(G_{b})$
for all $b\in\mathcal{B}$.

###  VI-B Main proof of Lemma 1

For all $a\in\mathcal{A}$, let
$G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{A}})$, and let
$G=\bigsqcup^{P_{A}}_{a\in\mathcal{A}}G_{a}$. Let
$P_{A}\in\Delta(\mathcal{A})$, and let
$(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}\in\mathcal{A}^{\mathbb{N}^{\star}}$
be a sequence such that $T_{\overline{a}^{n}}\rightarrow P_{A}$ when
$n\rightarrow\infty$.

Let $\epsilon>0$, and for all $n\in\mathbb{N}^{\star}$ let

$\displaystyle\mathcal{T}^{n}_{\epsilon}(P_{A})\doteq\big{\\{}a^{n}\in\mathcal{A}^{n}\>\big{|}\>\|T_{a^{n}}-P_{A}\|_{\infty}\leq\epsilon\big{\\}},$
(19) $\displaystyle P^{\prime
n}\doteq\frac{P^{n}_{A}}{P^{n}_{A}(\mathcal{T}^{n}_{\epsilon}(P_{A}))},\qquad\mathcal{S}_{\epsilon}^{n}\doteq\bigsqcup_{a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})}\;\prod_{t\leq
n}\mathcal{V}_{a_{t}}.$

By Lemma 3 we have

$\displaystyle\overline{H}(G)=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\Big{(}G^{\wedge
n}[\mathcal{S}^{n}_{\epsilon}]\Big{)},$ (20)

as $P^{n}_{V}(\mathcal{S}^{n}_{\epsilon})\rightarrow 1$ when
$n\rightarrow\infty$. Let us study the limit in (20). For all $n$ large
enough, $\overline{a}^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})$ as
$T_{\overline{a}^{n}}\rightarrow P_{A}$. Therefore, for all
$a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})$ and $a^{\prime}\in\mathcal{A}$,

$\displaystyle\big{|}T_{\overline{a}^{n}}(a^{\prime})-T_{a^{n}}(a^{\prime})\big{|}\leq
2\epsilon.$ (21)

We have on one hand

$\displaystyle
H_{\chi}\Big{(}\big{(}\textstyle\bigsqcup^{P_{A}}_{a\in\mathcal{A}}G_{a}\big{)}^{\wedge
n}[\mathcal{S}^{n}_{\epsilon}]\Big{)}$ $\displaystyle=\;$ $\displaystyle
H_{\chi}\left(\left(\textstyle\bigsqcup_{a^{n}\in\mathcal{A}^{n}}^{P_{A}^{n}}\;\textstyle\bigwedge_{t\leq
n}G_{a_{t}}\right)[\mathcal{S}^{n}_{\epsilon}]\right)$ (22) $\displaystyle=\;$
$\displaystyle
H_{\chi}\left(\textstyle\bigsqcup_{a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})}^{P^{\prime
n}}\;\textstyle\bigwedge_{t\leq n}G_{a_{t}}\right)$ (23) $\displaystyle=\;$
$\displaystyle
H_{\chi}\left(\textstyle\bigsqcup_{a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})}^{P^{\prime
n}}\;\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{a^{n}}(a^{\prime})}\right)$ (24) $\displaystyle\leq\;$ $\displaystyle
H_{\chi}\left(\textstyle\bigsqcup_{a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})}^{P^{\prime
n}}\;\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})+\lceil 2n\epsilon\rceil}\right)$ (25)
$\displaystyle=\;$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})+\lceil 2n\epsilon\rceil}\right)$ (26)
$\displaystyle\leq\;$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})}\right)+H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge\lceil
2n\epsilon\rceil}\right)$ (27) $\displaystyle\leq\;$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})}\right)+\lceil
2n\epsilon\rceil|\mathcal{A}|\log|\mathcal{V}|;$ (28)

where (22) comes from Lemma 2; (23) comes from the definition of
$\mathcal{S}_{\epsilon}^{n}$ and $P^{\prime n}$ in (19); (24) is a
rearrangement of the terms inside the product; (25) comes from (21); (26)
follows from Lemma 4, the graphs
$\big{(}\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})+\lceil
2n\epsilon\rceil}\big{)}_{a^{n}\in\mathcal{T}^{n}_{\epsilon}(P_{A})}$ are
isomorphic as they do not depend on $a^{n}$; (27) follows from the
subadditivity of $H_{\chi}$; and (28) is the upper bound on $H_{\chi}$ given
by the highest entropy of a coloring.

On the other hand, we obtain with similar arguments

$\displaystyle
H_{\chi}\Big{(}\big{(}\textstyle\bigsqcup^{P_{A}}_{a\in\mathcal{A}}G_{a}\big{)}^{\wedge
n}[\mathcal{S}^{n}_{\epsilon}]\Big{)}$ $\displaystyle\geq\>$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})-\lceil 2n\epsilon\rceil}\right)$ (29)
$\displaystyle\geq\>$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})}\right)-H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge\lceil
2n\epsilon\rceil}\right),$ (30) $\displaystyle\geq\>$ $\displaystyle
H_{\chi}\left(\textstyle\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})}\right)-\lceil
2n\epsilon\rceil|\mathcal{A}|\log|\mathcal{V}|.$ (31)

Note that (30) also comes from the subadditivity of $H_{\chi}$ :
$H_{\chi}(G_{2})\geq H_{\chi}(G_{1}\wedge G_{2})-H_{\chi}(G_{1})$ for all
$G_{1},G_{2}$.

By combining (28) and (31) we obtain

$\displaystyle\left|\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}(G^{\wedge
n}[\mathcal{S}^{n}_{\epsilon}])-\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\left(\bigwedge_{a^{\prime}\in\mathcal{A}}G_{a^{\prime}}^{\wedge
nT_{\overline{a}^{n}}(a^{\prime})}\right)\right|$ $\displaystyle\leq
2\epsilon|\mathcal{A}|\log|\mathcal{V}|.$ (32)

As this holds for all $\epsilon>0$, combining (20) and (32) yields the desired
result.

##  VII Proof of Theorem IV.8

###  VII-A Preliminary results

In Lemma 5 we give regularity properties of
$P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$.
The proof of Lemma 5 is developed in Appendix E. Lemma 6 states that if a
convex function $\gamma$ of $\Delta(\mathcal{A})$ meets the linear
interpolation of the $(\gamma(\mathds{1}_{a}))_{a\in\mathcal{A}}$ at an
interior point, then $\gamma$ is linear. We use it for proving the equivalence
in Theorem IV.8, by considering
$\gamma=P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$.
The proof of Lemma 6 is given in Appendix F.

###### Lemma 5

The function
$P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$
is convex and $(\log\max_{a}|\mathcal{V}_{a}|)$-Lipschitz.

###### Lemma 6

Let $\mathcal{A}$ be a finite set, and
$\gamma:\Delta(\mathcal{A})\rightarrow\mathbb{R}$ be a convex function. Then
the following holds:

$\displaystyle\exists
P_{A}\in\operatorname*{int}(\Delta(\mathcal{A})),\,\gamma(P_{A})=\textstyle\sum_{a\in\mathcal{A}}P_{A}(a)\gamma(\mathds{1}_{a})$
(33) $\displaystyle\Longleftrightarrow\;\;$ $\displaystyle\forall
P_{A}\in\Delta(\mathcal{A}),\,\gamma(P_{A})=\textstyle\sum_{a\in\mathcal{A}}P_{A}(a)\gamma(\mathds{1}_{a})$
(34)

where $\operatorname*{int}(\Delta(\mathcal{A}))$ is the interior of
$\Delta(\mathcal{A})$ (i.e. the full-support distributions on $\mathcal{A}$).

###  VII-B Main proof of Theorem IV.8

$(\Longrightarrow)$ Assume that
$\overline{H}\left(\textstyle\bigwedge_{a\in\mathcal{A}}G_{a}\right)=\textstyle\sum_{a\in\mathcal{A}}\overline{H}(G_{a})$.

We can use Corollary III.3:
$\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{\operatorname*{Unif}(\mathcal{A})}G_{a}\big{)}=\sum_{a\in\mathcal{A}}\frac{1}{|\mathcal{A}|}\overline{H}(G_{a})$.
Thus, the function
$P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$
is convex by Lemma 5, and satisfies (33) with the interior point
$P_{A}=\operatorname*{Unif}(\mathcal{A})$: by Lemma 6 we have

$\displaystyle\forall
P_{A}\in\Delta(\mathcal{A}),\;\overline{H}\big{(}\textstyle\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}=\textstyle\sum_{a\in\mathcal{A}}P_{A}(a)\overline{H}(G_{a}).$
(35)

$(\Longleftarrow)$ Conversely, assume (35), then
$P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$
is linear. We can use Corollary III.3, and we have
$\overline{H}\big{(}\bigwedge_{a\in\mathcal{A}}G_{a}\big{)}=|\mathcal{A}|\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{\operatorname*{Unif}(\mathcal{A})}G_{a}\big{)}=\sum_{a\in\mathcal{A}}\overline{H}(G_{a})$.

##  VIII Proof of Theorem IV.6

###  VIII-A Preliminary results

Lemma 7 comes from [23, Corollary 3.4], and states that the function
$P_{A}\mapsto
H_{\kappa}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$, defined
analogously to
$P_{A}\mapsto\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$,
is always linear. We give a proof of Lemma 7 in Appendix G for the sake of
completeness. The proof of Lemma 8 is given in Appendix H.

###### Lemma 7

For all probabilistic graphs $(G_{a})_{a\in\mathcal{A}}$ and
$P_{A}\in\Delta(\mathcal{A})$, we have
$H_{\kappa}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}=\sum_{a\in\mathcal{A}}P_{A}(a)H_{\kappa}(G_{a})$.

###### Lemma 8

The probabilistic graph $\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}$ is perfect
if and only if $G_{a}$ is perfect for all $a\in\mathcal{A}$.

###  VIII-B Main proof of Theorem IV.6

For all $a\in\mathcal{A}$, let
$G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{a}})$ be a perfect probabilistic
graph. By Lemma 8, $\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}$ is also perfect;
and we have
$\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}=H_{\kappa}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}$
by Theorem IV.5. We also have
$H_{\kappa}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}=\sum_{a\in\mathcal{A}}P_{A}(a)H_{\kappa}(G_{a})=\sum_{a\in\mathcal{A}}P_{A}(a)\overline{H}(G_{a})$
by Lemma 7 and Theorem IV.5 used on the perfect graphs
$(G_{a})_{a\in\mathcal{A}}$.

Therefore (12) is satisfied by the graphs $(G_{a})_{a\in\mathcal{A}}$ and
$P_{A}$: by Theorem IV.8, it follows that
$\overline{H}\left(\bigwedge_{a\in\mathcal{A}}G_{a}\right)=\sum_{a\in\mathcal{A}}\overline{H}(G_{a})=\sum_{a\in\mathcal{A}}H_{\kappa}(G_{a})$,
where the last equality comes from Theorem IV.5.

##  IX Conclusion

Theorem III.2 shows that
$\overline{H}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}=\frac{1}{k}\overline{H}\big{(}\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
kP_{A}(a)}\big{)}$ holds for all $P_{A}\in\Delta_{k}(\mathcal{A})$. The
consequences of this result are stated in Theorem IV.6, Theorem IV.8 and
Corollary IV.9. We provide a single-letter formula for $\overline{H}$ for a
new class of graphs. By (2), this allows to characterize optimal rates for the
two source coding problems depicted in Figure 2.

###### Proposition IX.1

The optimal rates in the settings from Figure 2.a and Figure 2.b are
respectively given by
$\overline{H}\big{(}\bigsqcup_{z\in\mathcal{Z}}^{P_{g(Y)}}G_{z}\big{)}$ and
$\overline{H}\big{(}\bigwedge_{z\in\mathcal{Z}}G_{z}\big{)}$.

## References

  * [1] N. Alon and A. Orlitsky, “Source coding and graph entropies,” _IEEE Transactions on Information Theory_ , vol. 42, no. 5, pp. 1329–1339, 1996.
  * [2] H. Witsenhausen, “The zero-error side information problem and chromatic numbers (corresp.),” _IEEE Transactions on Information Theory_ , vol. 22, no. 5, pp. 592–593, 1976.
  * [3] P. Koulgi, E. Tuncel, S. L. Regunathan, and K. Rose, “On zero-error source coding with decoder side information,” _IEEE Transactions on Information Theory_ , vol. 49, no. 1, pp. 99–111, 2003.
  * [4] J. Korner and G. Longo, “Two-step encoding for finite sources,” _IEEE Transactions on Information Theory_ , vol. 19, no. 6, pp. 778–782, 1973.
  * [5] I. Csiszár, J. Körner, L. Lovász, K. Marton, and G. Simonyi, “Entropy splitting for antiblocking corners and perfect graphs,” _Combinatorica_ , vol. 10, no. 1, pp. 27–40, 1990.
  * [6] E. Tuncel, J. Nayak, P. Koulgi, and K. Rose, “On complementary graph entropy,” _IEEE transactions on information theory_ , vol. 55, no. 6, pp. 2537–2546, 2009.
  * [7] A. Orlitsky and J. R. Roche, “Coding for computing,” in _Proceedings of IEEE 36th Annual Foundations of Computer Science_. IEEE, 1995, pp. 502–511.
  * [8] N. Charpenay, M. l. Treust, and A. Roumy, “Zero-error coding for computing with encoder side-information,” _arXiv preprint arXiv:2211.03649_ , 2022\.
  * [9] J. Ravi and B. K. Dey, “Zero-error function computation through a bidirectional relay,” in _2015 IEEE Information Theory Workshop (ITW)_. IEEE, 2015, pp. 1–5.
  * [10] D. Malak, “Fractional graph coloring for functional compression with side information,” _arXiv preprint arXiv:2204.11927_ , 2022.
  * [11] C. Shannon, “The zero error capacity of a noisy channel,” _IRE Transactions on Information Theory_ , vol. 2, no. 3, pp. 8–19, 1956.
  * [12] K. Marton, “On the shannon capacity of probabilistic graphs,” _Journal of Combinatorial Theory, Series B_ , vol. 57, no. 2, pp. 183–195, 1993.
  * [13] W. Haemers _et al._ , “On some problems of lovász concerning the shannon capacity of a graph,” _IEEE Transactions on Information Theory_ , vol. 25, no. 2, pp. 231–232, 1979.
  * [14] B. Bukh and C. Cox, “On a fractional version of haemers’ bound,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3340–3348, 2018.
  * [15] L. Gao, S. Gribling, and Y. Li, “On a tracial version of haemers bound,” _IEEE Transactions on Information Theory_ , 2022.
  * [16] A. Schrijver, “On the shannon capacity of sums and products of graphs,” _Indagationes Mathematicae_ , vol. 34, no. 1, pp. 37–41, 2023.
  * [17] H. Boche and C. Deppe, “Computability of the zero-error capacity of noisy channels,” in _2021 IEEE Information Theory Workshop (ITW)_. IEEE, 2021, pp. 1–6.
  * [18] J. Zuiddam _et al._ , _Algebraic complexity, asymptotic spectra and entanglement polytopes_. Institute for Logic, Language and Computation, 2018.
  * [19] Y. Gu and O. Shayevitz, “On the non-adaptive zero-error capacity of the discrete memoryless two-way channel,” _Entropy_ , vol. 23, no. 11, p. 1518, 2021.
  * [20] M. Wiese, T. J. Oechtering, K. H. Johansson, P. Papadimitratos, H. Sandberg, and M. Skoglund, “Secure estimation and zero-error secrecy capacity,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 3, pp. 1047–1062, 2018.
  * [21] J. Körner and K. Marton, “Graphs that split entropies,” _SIAM journal on discrete mathematics_ , vol. 1, no. 1, pp. 71–79, 1988.
  * [22] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, “The strong perfect graph theorem,” _Annals of mathematics_ , pp. 51–229, 2006.
  * [23] G. Simonyi, “Graph entropy: a survey,” _Combinatorial Optimization_ , vol. 20, pp. 399–441, 1995.

##  Appendix A Proof of Corollary IV.9

By [6, Lemma 3], if $G$ is perfect then

$\displaystyle\overline{H}(G\overset{(\alpha,1-\alpha)}{\sqcup}G_{5})=\alpha\overline{H}(G)+(1-\alpha)\overline{H}(G_{5}).$
(36)

By Theorem IV.8, we have $\overline{H}(G\wedge
G_{5})=\overline{H}(G)+\overline{H}(G_{5})=H_{\kappa}(G)+\frac{\log 5}{2}$;
where the last equality comes from [3, Example 1] which states that
$\overline{H}(G_{5})=\frac{\log 5}{2}$, and from Theorem IV.6.

##  Appendix B Proof dependencies

An illustration of the dependencies between the results can be found in Figure
5.

Lemma 2Lemma 9Lemma 3Lemma 4Lemma 5Theorem III.2Lemma 1Lemma 10Lemma 7Lemma
6Theorem IV.8Theorem IV.6Theorem IV.5Lemma 8 Figure 5: An arrow from A to B
means that A is used in the proof of B. Results from the literature are
represented with a dashed outline.

##  Appendix C Proof of Lemma 2

The probabilistic graphs in both sides of (18) have

$\displaystyle\left(\bigsqcup_{a\in\mathcal{A}}\mathcal{V}_{a}\right)\times\left(\bigsqcup_{b\in\mathcal{B}}\mathcal{V}_{b}\right)=\bigsqcup_{(a,b)\in\mathcal{A}\times\mathcal{B}}\mathcal{V}_{a}\times\mathcal{V}_{b}$
(37)

as set of vertices, with underlying distribution

$\displaystyle\left(\sum_{a\in\mathcal{A}}P_{A}(a)P_{V_{a}}\right)\left(\sum_{b\in\mathcal{B}}P_{B}(b)P_{V_{b}}\right)$
$\displaystyle=\sum_{(a,b)\in\mathcal{A}\times\mathcal{B}}P_{A}(a)P_{B}(b)P_{V_{a}}P_{V_{b}}.$
(38)

Now let us show that these two graphs have the same edges. Let
$(v_{\mathcal{A}},v_{\mathcal{B}}),(v^{\prime}_{\mathcal{A}},v^{\prime}_{\mathcal{B}})\in\left(\bigsqcup_{a\in\mathcal{A}}\mathcal{V}_{a}\right)\times\left(\bigsqcup_{b\in\mathcal{B}}\mathcal{V}_{b}\right)$;
let $a_{*},a^{\prime}_{*}\in\mathcal{A}$ and
$b_{*},b^{\prime}_{*}\in\mathcal{B}$ be the unique indexes such that

$\displaystyle(v_{\mathcal{A}},v_{\mathcal{B}})\in\mathcal{V}_{a_{*}}\times\mathcal{V}_{b_{*}}\quad\text{and}\quad(v^{\prime}_{\mathcal{A}},v^{\prime}_{\mathcal{B}})\in\mathcal{V}_{a^{\prime}_{*}}\times\mathcal{V}_{b^{\prime}_{*}}.$
(39)

We have:

$\displaystyle\\!\\!\\!(v_{\mathcal{A}},v_{\mathcal{B}}),(v^{\prime}_{\mathcal{A}},v^{\prime}_{\mathcal{B}})\text{
are adjacent in
}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)\wedge\left(\bigsqcup_{b\in\mathcal{B}}^{P_{B}}G_{b}\right)$
(40) $\displaystyle\Longleftrightarrow$
$\displaystyle\;v_{\mathcal{A}},v^{\prime}_{\mathcal{A}}\text{ adjacent in
}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\text{ and }$ $\displaystyle
v_{\mathcal{B}},v^{\prime}_{\mathcal{B}}\text{ adjacent in
}\bigsqcup_{b\in\mathcal{B}}^{P_{B}}G_{b}$ (41)
$\displaystyle\Longleftrightarrow$ $\displaystyle\;a_{*}=a^{\prime}_{*}\text{
and }v_{\mathcal{A}}v^{\prime}_{\mathcal{A}}\in\mathcal{E}_{a_{*}}\text{ and
}b_{*}=b^{\prime}_{*}\text{ and
}v_{\mathcal{B}}v^{\prime}_{\mathcal{B}}\in\mathcal{E}_{b_{*}}$ (42)
$\displaystyle\Longleftrightarrow$
$\displaystyle\;(a_{*},b_{*})=(a^{\prime}_{*},b^{\prime}_{*})\text{ and }$
$\displaystyle\;(v_{\mathcal{A}},v_{\mathcal{B}}),(v^{\prime}_{\mathcal{A}},v^{\prime}_{\mathcal{B}})\text{
are adjacent in }G_{a_{*}}\wedge G_{b_{*}}$ (43)
$\displaystyle\Longleftrightarrow$
$\displaystyle\;(v_{\mathcal{A}},v_{\mathcal{B}}),(v^{\prime}_{\mathcal{A}},v^{\prime}_{\mathcal{B}})\text{
are adjacent in
}\bigsqcup_{(a,b)\in\mathcal{A}\times\mathcal{B}}^{P_{A}P_{B}}G_{a}\wedge
G_{b}.$ (44)

##  Appendix D Proof of Lemma 3

###  D-A Preliminary results

In Lemma 9 we give upper and lower bounds on the chromatic entropy of an
induced subgraph $G[\mathcal{S}]$, using the chromatic entropy of the whole
graph $G$ and the probability $P_{V}(\mathcal{S})$. The core idea is that if
$P_{V}(\mathcal{S})$ is close to $1$ and $H_{\chi}(G)$ is big, then
$H_{\chi}(G[\mathcal{S}])$ is close to $H_{\chi}(G)$. The proof of Lemma 9 is
given in Appendix I

###### Lemma 9

Let $G=(\mathcal{V},\mathcal{E},P_{V})$ and $\mathcal{S}\subset\mathcal{V}$,
then

$\displaystyle H_{\chi}(G)-1-(1-P_{V}(\mathcal{S}))\log|\mathcal{V}|\leq
H_{\chi}(G[\mathcal{S}])\leq\frac{H_{\chi}(G)}{P_{V}(\mathcal{S})}.$ (45)

###### Remark D.1

$H_{\chi}(G[\mathcal{S}])$ can be greater than $H_{\chi}(G)$, even if
$G[\mathcal{S}]$ has less vertices and inherits the structure of $G$. This
stems from the normalized distribution $P_{V}/P_{V}(\mathcal{S})$ on the
vertices of $G[\mathcal{S}]$ which gives more weight to the vertices in
$\mathcal{S}$. For example, consider

$\displaystyle
G=\big{(}N_{5},\operatorname*{Unif}(\\{1,...,5\\})\big{)}\overset{(1-\epsilon,\epsilon)}{\sqcup}\big{(}K_{5},\operatorname*{Unif}(\\{1,...,5\\})\big{)},$

with $\mathcal{S}$ being the vertices in the connected component $K_{5}$ in
$G$. Then $H_{\chi}(G)=\epsilon\log 5$ and $H_{\chi}(G[\mathcal{S}])=\log 5$.

###  D-B Main proof of Lemma 3

By Lemma 9, we have for all $n\in\mathbb{N}^{\star}$:

$\displaystyle H_{\chi}(G^{\wedge
n})-1-(1-P^{n}_{V}(\mathcal{S}^{n}))\log|\mathcal{V}|$ $\displaystyle\leq\>$
$\displaystyle H_{\chi}(G^{\wedge
n}[\mathcal{S}^{n}])\leq\frac{H_{\chi}(G^{\wedge
n})}{P^{n}_{V}(\mathcal{S}^{n})}.$ (46)

Since $P^{n}_{V}(\mathcal{S}^{n})\rightarrow 1$, and $H_{\chi}(G^{\wedge
n})=n\overline{H}(G)+o(n)$ when $n\rightarrow\infty$, the desired results
follows immediately by normalization and limit.

##  Appendix E Proof of Lemma 5

###  E-A Preliminary results

Lemma 10 is a generalization for infinite sequences of the following
observation: if $T_{\overline{a}^{n}}=P_{A}\in\Delta_{n}(\mathcal{A})$
satisfies $P_{A}=\frac{i}{n}P^{\prime}_{A}+\frac{n-i}{n}P^{\prime\prime}_{A}$
with $P^{\prime}_{A}\in\Delta_{i}(\mathcal{A})$ and
$P^{\prime\prime}_{A}\in\Delta_{n-i}(\mathcal{A})$, then $\overline{a}^{n}$
can be separated into two subsequences $a^{\prime i}$ and $a^{\prime\prime
n-i}$ such that $T_{a^{\prime i}}=P^{\prime}_{A}$ and $T_{a^{\prime\prime
n-i}}=P^{\prime\prime}_{A}$. The proof is given in Appendix J.

######  Lemma 10 (Type-splitting lemma)

Let
$(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}\in\mathcal{A}^{\mathbb{N}^{\star}}$
be a sequence such that $T_{\overline{a}^{n}}\rightarrow
P_{A}\in\Delta(\mathcal{A})$ when $n\rightarrow\infty$, let $\beta\in(0,1)$
and $P^{\prime}_{A},P^{\prime\prime}_{A}\in\Delta(\mathcal{A})$ such that

$\displaystyle P_{A}=\beta P^{\prime}_{A}+(1-\beta)P^{\prime\prime}_{A}.$ (47)

Then there exists a sequence
$(b_{n})_{n\in\mathbb{N}^{\star}}\in\\{0,1\\}^{\mathbb{N}^{\star}}$ such that
the two extracted sequences
$a^{\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=0\end{subarray}}$ and
$a^{\prime\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=1\end{subarray}}$ satisfy

$\displaystyle
T_{b^{n}}\underset{n\rightarrow\infty}{\rightarrow}(\beta,1-\beta),$ (48)
$\displaystyle T_{a^{\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime}_{A},$ $\displaystyle
T_{a^{\prime\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime\prime}_{A}.$ (49)

###  E-B Main proof of Lemma 5

($\eta$ Lipschitz) Let us first prove that $\eta$ is Lipschitz. For all
$P_{A},P^{\prime}_{A}\in\Delta(\mathcal{A})$ we need to bound the quantity
$|\eta(P_{A})-\eta(P^{\prime}_{A})|$; by Lemma 1 this is equivalent to
bounding

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\left|H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{n}}(a)}\right)-H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{\prime n}}(a)}\right)\right|$ (50)

where $(T_{\overline{a}^{n}},T_{\overline{a}^{\prime
n}})\rightarrow(P_{A},P^{\prime}_{A})$ when $n\rightarrow\infty$.

Fix $n\in\mathbb{N}^{\star}$, we assume that the quantity inside $|\cdot|$ in
(50) is positive; the other case can be treated with the same arguments by
symmetry of the roles. We have

$\displaystyle H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{n}}(a)}\right)-H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{\prime n}}(a)}\right)$ (51) $\displaystyle\leq$
$\displaystyle\;H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{n}}(a)}\right)-H_{\chi}\Bigg{(}\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
n\min(T_{\overline{a}^{n}}(a),T_{\overline{a}^{\prime n}}(a))}\\!\Bigg{)}$
(52) $\displaystyle=$
$\displaystyle\;H_{\chi}\Bigg{(}\\!\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
n\min(T_{\overline{a}^{n}}(a),T_{\overline{a}^{\prime
n}}(a))}\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
n|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime n}}(a)|_{+}}\\!\\!\Bigg{)}$
$\displaystyle-H_{\chi}\Bigg{(}\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
n\min(T_{\overline{a}^{n}}(a),T_{\overline{a}^{\prime n}}(a))}\Bigg{)}$ (53)
$\displaystyle\leq$
$\displaystyle\;H_{\chi}\Bigg{(}\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
n|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime n}}(a)|_{+}}\Bigg{)}$ (54)
$\displaystyle\leq$
$\displaystyle\;\log\left(\max_{a}|\mathcal{V}_{a}|\right)\sum_{a\in\mathcal{A}}n|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime
n}}(a)|_{+}$ (55) $\displaystyle\leq$
$\displaystyle\;n\log\left(\max_{a}|\mathcal{V}_{a}|\right)\|T_{\overline{a}^{n}}-T_{\overline{a}^{\prime
n}}\|_{1},$ (56)

where $|\cdot|_{+}=\max(\cdot,0)$ and
$\|T_{\overline{a}^{n}}-T_{\overline{a}^{\prime
n}}\|_{1}=\sum_{a\in\mathcal{A}}|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime
n}}(a)|$; (52) follows from the removal of terms in the second product, as
$H_{\chi}(G\wedge G^{\prime})\geq H_{\chi}(G)$ for all probabilistic graphs
$G,G^{\prime}$; (53) is an arrangement of the terms in the first product, as
$\min(s,t)+\max(s-t,0)=s$ for all real numbers $s,t$; (54) comes from the
subadditivity of $H_{\chi}$; (55) follows from
$H_{\chi}(G_{a})\leq\log\max_{a^{\prime}}|\mathcal{V}_{a^{\prime}}|$ for all
$a\in\mathcal{A}$; (56) results from
$|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime
n}}(a)|_{+}\leq|T_{\overline{a}^{n}}(a)-T_{\overline{a}^{\prime n}}(a)|$ for
all $a\in\mathcal{A}$.

By normalization and limit, it follows that

$\displaystyle|\eta(P_{A})-\eta(P^{\prime}_{A})|$
$\displaystyle\leq\lim_{n\rightarrow\infty}\log\left(\max_{a}|\mathcal{V}_{a}|\right)\cdot\|T_{\overline{a}^{n}}-T_{\overline{a}^{\prime
n}}\|_{1}$ (57)
$\displaystyle=\log\left(\max_{a}|\mathcal{V}_{a}|\right)\cdot\|P_{A}-P^{\prime}_{A}\|_{1}.$
(58)

Hence $\eta$ is $(\log\max_{a}|\mathcal{V}_{a}|)$-Lipschitz.

($\eta$ convex) Let us now prove that $\eta$ is convex. Let
$P^{\prime}_{A},P^{\prime\prime}_{A}\in\Delta(\mathcal{A})$, and
$\beta\in(0,1)$, we have by Lemma 1

$\displaystyle\eta\big{(}\beta
P^{\prime}_{A}+(1-\beta)P^{\prime\prime}_{A}\big{)}=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge
nT_{\overline{a}^{n}}(a)}\right),$ (59)

where $T_{\overline{a}^{n}}\rightarrow\beta
P^{\prime}_{A}+(1-\beta)P^{\prime\prime}_{A}$ when $n\rightarrow\infty$. By
Lemma 10, there exists
$(b_{n})_{n\in\mathbb{N}^{\star}}\in\\{0,1\\}^{\mathbb{N}^{\star}}$ such that
the decomposition of $(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}$ into two
subsequences
$a^{\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=0\end{subarray}}$ and
$a^{\prime\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=1\end{subarray}}$ satisfies

$\displaystyle
T_{b^{n}}\underset{n\rightarrow\infty}{\rightarrow}(\beta,1-\beta),$ (60)
$\displaystyle T_{a^{\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime}_{A},$ $\displaystyle
T_{a^{\prime\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime\prime}_{A}.$ (61)

For all $n\in\mathbb{N}^{\star}$, let $\Xi(n)\doteq nT_{b^{n}}(0)$, we have

$\displaystyle\eta\big{(}\beta
P^{\prime}_{A}+(1-\beta)P^{\prime\prime}_{A}\big{)}$ (62) $\displaystyle=$
$\displaystyle\;\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge\Xi(n)T_{a^{\prime\Xi(n)}}(a)+(n-\Xi(n))T_{a^{\prime\prime
n-\Xi(n)}}(a)}\right)$ (63) $\displaystyle\leq$
$\displaystyle\;\lim_{n\rightarrow\infty}\frac{\Xi(n)}{n}\frac{1}{\Xi(n)}H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge\Xi(n)T_{a^{\prime\Xi(n)}}(a)}\right)$
(64)
$\displaystyle+\frac{n-\Xi(n)}{n}\frac{1}{n-\Xi(n)}H_{\chi}\left(\bigwedge_{a\in\mathcal{A}}G_{a}^{\wedge(n-\Xi(n))T_{a^{\prime\prime
n-\Xi(n)}}(a)}\right)$ (65) $\displaystyle=$
$\displaystyle\;\beta\eta(P^{\prime}_{A})+(1-\beta)\eta(P^{\prime\prime}_{A});$
(66)

where (63) comes from (59); (65) follows from the subadditivity of $H_{\chi}$;
(66) comes from (60), (61) and Lemma 1. Since (66) holds for all
$P^{\prime}_{A},P^{\prime\prime}_{A}\in\Delta(\mathcal{A})$ and
$\beta\in(0,1)$, we have that $\eta$ is convex.

##  Appendix F Proof of Lemma 6

It can be easily observed that

$\displaystyle\exists
P_{A}\in\operatorname*{int}(\Delta(\mathcal{A})),\,\gamma(P_{A})=\sum_{a\in\mathcal{A}}P_{A}(a)\gamma(\mathds{1}_{a})$
(67) $\displaystyle\Longleftarrow\;\;$ $\displaystyle\forall
P_{A}\in\Delta(\mathcal{A}),\,\gamma(P_{A})=\sum_{a\in\mathcal{A}}P_{A}(a)\gamma(\mathds{1}_{a}).$
(68)

Now let us prove (67) $\Rightarrow$ (68). Let
$P^{*}_{A}\in\operatorname*{int}\Delta(\mathcal{A})$ such that
$\gamma(P^{*}_{A})=\sum_{a\in\mathcal{A}}P^{*}_{A}(a)\gamma(\mathds{1}_{a})$.
Let $m:\Delta(\mathcal{A})\rightarrow\mathbb{R}$ linear such that
$m(P^{*}_{A})=\gamma(P^{*}_{A})$ and $\forall
P_{A}\in\Delta(\mathcal{A}),\,m(P_{A})\leq\gamma(P_{A})$. We have

$\displaystyle
0=\gamma(P^{*}_{A})-m(P^{*}_{A})=\sum_{a\in\mathcal{A}}P^{*}_{A}(a)\big{(}\gamma(\mathds{1}_{a})-m(\mathds{1}_{a})\big{)};$
(69)

and therefore $\gamma(\mathds{1}_{a})=m(\mathds{1}_{a})$ for all
$a\in\mathcal{A}$, as $\gamma-m\geq 0$ and $P^{*}_{A}(a)>0$ for all
$a\in\mathcal{A}$. For all $P_{A}\in\Delta(\mathcal{A})$, we have

$\displaystyle f(P_{A})$
$\displaystyle\leq\sum_{a\in\mathcal{A}}P_{A}(a)\gamma(\mathds{1}_{a})$ (70)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)m(\mathds{1}_{a})=m(P_{A}),$ (71)

hence $\gamma=m$ and $\gamma$ is linear.

##  Appendix G Proof of Lemma 7

Let $G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{a}})$, and
$G=(\mathcal{V},\mathcal{E},P_{V})$ such that
$G=\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}$. Let $A$ be the random variable
with distribution $P_{A}$ such that $V=V_{A}$, i.e. $P_{V|A=a}=P_{V_{a}}$.

Achievability

For all $a\in\mathcal{A}$, let $W^{*}_{a}$ be a minimizer of

$\displaystyle\min_{V_{a}\in W_{a}\in\Gamma(G_{a})}I(V_{a};W_{a}).$ (72)

Let $W^{*}$ be the random variable defined as follows: for all
$\mathcal{S}\in\Gamma(G)$, $a\in\mathcal{A}$ and $v_{a}\in\mathcal{V}_{a}$,

$\displaystyle P_{W^{*}|A=a,V=v_{a}}(\mathcal{S})\doteq
P_{W^{*}_{a}|V_{a}=v_{a}}(\mathcal{S}_{a})\prod_{\begin{subarray}{c}a^{\prime}\in\mathcal{A}\\\
a^{\prime}\neq
a\end{subarray}}P_{W^{*}_{a^{\prime}}}(\mathcal{S}_{a^{\prime}}),$ (73)

where $\mathcal{S}$ is uniquely decomposed as
$\bigsqcup_{a\in\mathcal{A}}\mathcal{S}_{a}$, with
$\mathcal{S}_{a}\in\Gamma(G_{a})$ for all $a\in\mathcal{A}$. The random
variable $W^{*}$ takes its values in $\Gamma(G)$, as

$\displaystyle P_{W^{*}}(\mathcal{S})>0\Longrightarrow\forall
a\in\mathcal{A},\,P_{W^{*}_{a}}(\mathcal{S}_{a})>0.$ (74)

The conditional distribution w.r.t. $(A=a)$ writes:

$\displaystyle P_{W^{*}|A=a}(\mathcal{S})=$
$\displaystyle\sum_{v_{a}\in\mathcal{V}_{a}}P_{V_{a}}(v_{a})P_{W^{*}|A=a,V=v_{a}}(\mathcal{S})$
(75) $\displaystyle=$
$\displaystyle\sum_{v_{a}\in\mathcal{V}_{a}}P_{V_{a}}(v_{a})P_{W^{*}_{a}|V_{a}=v_{a}}(\mathcal{S}_{a})\prod_{\begin{subarray}{c}a^{\prime}\in\mathcal{A}\\\
a^{\prime}\neq
a\end{subarray}}P_{W^{*}_{a^{\prime}}}(\mathcal{S}_{a^{\prime}})$ (76)
$\displaystyle=$
$\displaystyle\prod_{a^{\prime}\in\mathcal{A}}P_{W^{*}_{a^{\prime}}}(\mathcal{S}_{a^{\prime}}).$
(77)

It follows that the random variable $W^{*}$ is independent of $A$ as the
expression (77) does not depend on $a$. Note that $P_{W^{*}}$ defined in (73)
is a probability distribution, as

$\displaystyle\sum_{\mathcal{S}\in\Gamma(G)}P_{W^{*}}(\mathcal{S})=$
$\displaystyle\;\sum_{\mathcal{S}\in\Gamma(G)}\;\;\prod_{a^{\prime}\in\mathcal{A}}P_{W^{*}_{a^{\prime}}}(\mathcal{S}_{a^{\prime}})$
(78) $\displaystyle=$
$\displaystyle\;\sum_{(\mathcal{S}_{a^{\prime}})_{a^{\prime}\in\mathcal{A}}\in\prod_{a^{\prime}\in\mathcal{A}}\Gamma(G_{a^{\prime}})}\;\;\prod_{a^{\prime}\in\mathcal{A}}P_{W^{*}_{a^{\prime}}}(\mathcal{S}_{a^{\prime}})$
(79) $\displaystyle=$ $\displaystyle\;1,$ (80)

where (78) comes from (77); (79) follows from
$\Gamma(G)=\big{\\{}\bigsqcup_{a\in\mathcal{A}}\mathcal{S}_{a}\>\big{|}\>\forall
a\in\mathcal{A},\,\mathcal{S}_{a}\in\Gamma(G_{a})\big{\\}}$; and (80) holds as
$W^{*}_{a}$ takes its values in $\Gamma(G_{a})$ for all $a\in\mathcal{A}$.

Now, let us show that $V\in W^{*}$ with probability one. For all
$a\in\mathcal{A}$ and $v_{a}\in\mathcal{V}_{a}$,

$\displaystyle\\{\mathcal{S}\cap\mathcal{V}_{a}\>|\>\mathcal{S}\in\operatorname*{supp}P_{W^{*}|V=v_{a}}\\}=\operatorname*{supp}P_{W^{*}_{a}|V_{a}=v_{a}};$
(81)

where $\operatorname*{supp}$ denotes the support of a probability
distribution. Since $V_{a}\in W^{*}_{a}$ with probability one, all the sets in
$\operatorname*{supp}P_{W^{*}_{a}|V_{a}=v_{a}}$ contain $v_{a}$, hence all
sets in $\operatorname*{supp}P_{W^{*}|V=v_{a}}$ also contain $v_{a}$: $V\in
W^{*}$ with probability one.

Now let us combine the results on $W^{*}$:

$\displaystyle H_{\kappa}(G)$ $\displaystyle\leq I(V;W^{*})$ (82)
$\displaystyle=I(V,A;W^{*})$ (83)
$\displaystyle=I(A;W^{*})+\sum_{a\in\mathcal{A}}P_{A}(a)I(V;W^{*}|A=a)$ (84)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)I(V_{a};W_{a}^{*})$ (85)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)H_{\kappa}(G_{a});$ (86)

where (82) holds as $W^{*}$ takes its values in $\Gamma(G)$ and $V\in W^{*}$
with probability one; (83) holds as $A$ is a deterministic function of $V$;
(84) comes from the decomposition $I(V,A;W)=I(V;W|A)+I(A;W)$; (85) follows
from the independence of $A$ and $W^{*}$; (86) comes from the fact that
$W^{*}_{a}$ minimizes (72).

Converse

$\displaystyle\\!\\!H_{\kappa}\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)$
$\displaystyle=\min_{V\in W\in\Gamma(G)}I(V,A;W)$ (87)
$\displaystyle\geq\min_{V\in
W\in\Gamma(G)}\sum_{a\in\mathcal{A}}P_{A}(a)I(V;W|A=a)$ (88)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)\min_{V\in
W\in\Gamma(G)}\\!I(V;W|A=a)$ (89)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)\min_{V_{a}\in
W\in\Gamma(G_{a})}I(V_{a};W)$ (90)
$\displaystyle=\sum_{a\in\mathcal{A}}P_{A}(a)H_{\kappa}(G_{a});$ (91)

where (87) holds as $A$ is a deterministic function of $V$; (88) follows from
the decomposition $I(V,A;W)=I(V;W|A)+I(A;W)$; and (90) holds as $V=V_{A}$.

##  Appendix H Proof of Lemma 8

$(\Longrightarrow)$ Let $G=\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}$ be a
perfect probabilistic graph. Let $a^{\prime}\in\mathcal{A}$ and
$\mathcal{S}_{a^{\prime}}\subset\mathcal{V}_{a^{\prime}}$. We have
$\chi\big{(}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}[\mathcal{S}_{a^{\prime}}]\big{)}=\omega\big{(}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}[\mathcal{S}_{a^{\prime}}]\big{)}$
since $G$ is perfect, and therefore
$\chi(G_{a^{\prime}}[\mathcal{S}_{a^{\prime}}])=\omega(G_{a^{\prime}}[\mathcal{S}_{a^{\prime}}])$,
as
$\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}[\mathcal{S}_{a^{\prime}}]=G_{a^{\prime}}[\mathcal{S}_{a^{\prime}}]$.
Thus all the graphs $(G_{a})_{a\in\mathcal{A}}$ are perfect.

$(\Longleftarrow)$ Conversely, assume that for all $a\in\mathcal{A}$,
$G_{a}=(\mathcal{V}_{a},\mathcal{E}_{a},P_{V_{a}})$ is perfect. Then for all
$\mathcal{S}\subset\bigsqcup_{a\in\mathcal{A}}\mathcal{V}_{a}$, $\mathcal{S}$
can be written as $\bigsqcup_{a\in\mathcal{A}}\mathcal{S}_{a}$ where
$\mathcal{S}_{a}\subset\mathcal{V}_{a}$ for all $a\in\mathcal{A}$, and we have
for all $P_{A}\in\Delta(\mathcal{A})$:

$\displaystyle\chi\left(\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\right)[\mathcal{S}]\right)$
$\displaystyle=\chi\left(\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}[\mathcal{S}_{a}]\right)$
(92)
$\displaystyle=\max_{a\in\mathcal{A}}\chi\left(G_{a}[\mathcal{S}_{a}]\right)$
(93)
$\displaystyle=\max_{a\in\mathcal{A}}\omega\left(G_{a}[\mathcal{S}_{a}]\right),$
(94)

and similarly,
$\omega\big{(}\big{(}\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}\big{)}[\mathcal{S}]\big{)}=\max_{a\in\mathcal{A}}\omega\left(G_{a}[\mathcal{S}_{a}]\right)$.
Hence $\bigsqcup_{a\in\mathcal{A}}^{P_{A}}G_{a}$ is also perfect.

##  Appendix I Proof of Lemma 9

Let $c^{*}:\mathcal{V}\rightarrow\mathcal{C}$ and
$c^{*}_{\mathcal{S}}:\mathcal{S}\rightarrow\mathcal{C}$ be the optimal
colorings of $G$ and $G[\mathcal{S}]$, respectively. Consider the coloring
$c:\mathcal{V}\rightarrow\mathcal{C}\sqcup\mathcal{V}$ of $G$ defined by
$c(v)=c^{*}_{\mathcal{S}}$ if $v\in\mathcal{S}$, $c(v)=v$ otherwise.

(Lower bound) On one hand, we have

$\displaystyle H_{\chi}(G)\leq$
$\displaystyle\>H(c(V),\mathds{1}_{V\in\mathcal{S}})$ (95) $\displaystyle=$
$\displaystyle\>H(\mathds{1}_{V\in\mathcal{S}})+P_{V}(\mathcal{S})H(c(V)|V\in\mathcal{S})$
$\displaystyle+(1-P_{V}(\mathcal{S}))H(c(V)|V\notin\mathcal{S})$ (96)
$\displaystyle\leq$
$\displaystyle\>1+H(c^{*}_{\mathcal{S}}(V)|V\in\mathcal{S})+(1-P_{V}(\mathcal{S}))\log|\mathcal{V}|$
(97) $\displaystyle=$
$\displaystyle\>H_{\chi}(G[\mathcal{S}])+1+(1-P_{V}(\mathcal{S}))\log|\mathcal{V}|;$
(98)

where (95) comes from the fact that $c$ is a coloring of $G$; (96) is a
decomposition using conditional entropies; (97) comes from the construction of
$c$: $c|_{\mathcal{S}}=c^{*}_{\mathcal{S}}$; (98) follows from the optimality
of $c^{*}_{\mathcal{S}}$ as a coloring of $G[\mathcal{S}]$.

(Upper bound) On the other hand,

$\displaystyle H_{\chi}(G[\mathcal{S}])$ $\displaystyle\leq$
$\displaystyle\>H(c^{*}(V)|V\in\mathcal{S})$ (99) $\displaystyle=$
$\displaystyle\,\frac{1}{P_{V}(\mathcal{S})}\Big{(}\\!H(c^{*}(V)|\mathds{1}_{V\in\mathcal{S}})-(1-P_{V}(\mathcal{S}))H(c^{*}(V)|V\notin\mathcal{S})\\!\Big{)}$
(100) $\displaystyle\leq$
$\displaystyle\>\frac{H(c^{*}(V))}{P_{V}(\mathcal{S})}=\frac{H_{\chi}(G)}{P_{V}(\mathcal{S})}$
(101)

where (99) comes from the fact that $c^{*}$ induces a coloring of
$G[\mathcal{S}]$; (100) is a decomposition using conditional entropies; (101)
results from the elimination of negative terms and the optimality of $c^{*}$.

##  Appendix J Proof of Lemma 10

Let
$(\overline{a}_{n})_{n\in\mathbb{N}^{\star}}\in\mathcal{A}^{\mathbb{N}^{\star}}$
be a sequence such that $T_{\overline{a}^{n}}\rightarrow P_{A}=\beta
P^{\prime}_{A}+(1-\beta)P^{\prime\prime}_{A}$ when $n\rightarrow\infty$.

Consider a sequence $(B_{n})_{n\in\mathbb{N}^{\star}}$ of independent
Bernoulli random variables such that for all $n\in\mathbb{N}^{\star}$,

$\displaystyle\Pr(B_{n}=0)=\frac{\beta
P^{\prime}_{A}(\overline{a}_{n})}{P_{A}(\overline{a}_{n})}.$ (102)

By the strong law of large numbers,

$\displaystyle\Pr\left(T_{B^{n},\overline{a}^{n}}\underset{n\rightarrow\infty}{\rightarrow}(\beta
P^{\prime}_{A},(1-\beta)P^{\prime\prime}_{A})\right)=1.$ (103)

Therefore, there exists at least one realization
$(b_{n})_{n\in\mathbb{N}^{\star}}$ of $(B_{n})_{n\in\mathbb{N}^{\star}}$ such
that $T_{b^{n},\overline{a}^{n}}$ converges to $\big{(}\beta
P^{\prime}_{A},(1-\beta)P^{\prime\prime}_{A}\big{)}$. The convergences of
marginal and conditional types yield

$\displaystyle
T_{b^{n}}\underset{n\rightarrow\infty}{\rightarrow}(\beta,1-\beta),$ (104)
$\displaystyle T_{a^{\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime}_{A},\qquad
T_{a^{\prime\prime
n}}\underset{n\rightarrow\infty}{\rightarrow}P^{\prime\prime}_{A},$ (105)

where
$a^{\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=0\end{subarray}}$ and
$a^{\prime\prime}\doteq(\overline{a}_{n})_{\begin{subarray}{c}n\in\mathbb{N}^{\star},\\\
b_{n}=1\end{subarray}}$ are the extracted sequences.