## B.2.4 Proof of Proposition 5.2.5

In order to prove Proposition 5.2.5 we need Lemma B.2.8, which is a consequence of Marton's formula in Theorem 5.1.5 applied to a disjoint union. The proof of Lemma B.2.8 can be found in Appendix B.6.6.

**Lemma B.2.8** Let $P_A \in \Delta(\mathcal{A})$, then

$$ \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) + C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) H(P_{V_a}). \quad (B.23) $$

Let us prove Proposition 5.2.5. We have on one hand:

$$ H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) C(G_a, P_{V_a}) \quad (B.24) $$

$$ = H(P_A) + \sum_{a \in \mathcal{A}} -P_A(a)\overline{H}(G_a) + P_A(a)H(P_{V_a}) \quad (B.25) $$

$$ \leq H(P_A) - \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) + \sum_{a \in \mathcal{A}} P_A(a) H(P_{V_a}) \quad (B.26) $$

$$ = C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a}\right); \quad (B.27) $$

where (B.25) comes from Theorem 5.1.5; (B.26) follows from Theorem 5.1.11; and (B.27) follows from Lemma B.2.8. Therefore,

$$ C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) C(G_a, P_{V_a}) \quad (B.28) $$

$$ \iff \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) = \sum_{a \in \mathcal{A}} P_A(a) \overline{H}(G_a). \quad (B.29) $$

On the other hand:

$$ \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) = \sum_{a \in \mathcal{A}} -\overline{H}(G_a) + H(P_{V_a}) \quad (B.30) $$

$$ \leq -\overline{H}(\bigcap_{a \in \mathcal{A}} G_a) + \sum_{a \in \mathcal{A}} H(P_{V_a}) \quad (B.31) $$

$$ = -\overline{H}(\bigcap_{a \in \mathcal{A}} G_a) + H(\bigotimes_{a \in \mathcal{A}} P_{V_a}) \quad (B.32) $$

$$ = C(\bigcap_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}); \quad (B.33) $$

where (B.30) comes from Theorem 5.1.5; (B.31) follows from Theorem 5.1.11; and (B.33) also follows from Theorem 5.1.5. Therefore,

$$ \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) = C(\bigcap_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}) \quad (B.34) $$
$$ \iff \overline{H}(\Lambda_{a \in A} G_a) = \sum_{a \in A} \overline{H}(G_a). \qquad (B.35) $$

# B.3 Main proofs for the capacity-achieving distributions

## B.3.1 Proof of Lemma 5.1.3

Lemma B.3.1 enables us to replace the limit superior in the definition of $C(G, P_V)$ by a regular limit. The proof is given in Appendix B.6.7 and uses superadditivity arguments.

**Lemma B.3.1** For all $\epsilon > 0$, we have

$$ \limsup_{n \to \infty} \frac{1}{n} \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]) = \sup_{n \in \mathbb{N}^{*}} \frac{1}{n} \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]) = \lim_{n \to \infty} \frac{1}{n} \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]). \quad (B.36) $$

Now let us prove Lemma 5.1.3.

By definition of $C(G, P_V)$ and Lemma B.3.1,

$$ \lim_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon'}^{n}(P_V)]) \xrightarrow{\epsilon' \to 0} C(G, P_V). \qquad (B.37) $$

Thus, there exists a mapping $\epsilon: \mathbb{N}^* \to \mathbb{R}_+^*$ such that $\epsilon(k) \xrightarrow{k \to \infty} 0$ and for all $k \in \mathbb{N}^*$,

$$ \left| \lim_{n' \to \infty} \frac{1}{n'} \log \alpha(G^{\wedge n'}[\mathcal{T}_{\epsilon(k)}^{n'}(P_V)]) - C(G, P_V) \right| \le \frac{1}{k}. \qquad (B.38) $$

Now, let $m(k) \in \mathbb{N}^*$ such that for all $n \ge m(k)$,

$$ \left| \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon(k)}^{n}(P_V)]) - \lim_{n' \to \infty} \frac{1}{n'} \log \alpha(G^{\wedge n'}[\mathcal{T}_{\epsilon(k)}^{n'}(P_V)]) \right| \le \frac{1}{k}. \qquad (B.39) $$

It can be easily observed that (B.39) is also satisfied if $n \ge \max(k, m(k))$. Therefore, for all $k \in \mathbb{N}^*$, and $n \ge \max(k, m(k))$, we have

$$ \left| \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon(k)}^{n}(P_V)]) - C(G, P_V) \right| \le \frac{1}{2k}. \qquad (B.40) $$

Now we can build the desired sequence of codebooks. For all $n \in \mathbb{N}^*$, let $C_n \subseteq \mathcal{V}^n$ be a maximal independent set in $G^{\wedge n}[\mathcal{T}_{\epsilon(k(n))}^{n}(P_V)];$ where $k(n)$ is the biggest $k$ such that
$n \ge \max(k, m(k))$. Note that $k(n)$ exists as $k(n) \le n$, and

$$k(n) \underset{n \to \infty}{\to} \infty. \qquad (B.41)$$

We have

$$\left| \frac{\log |\mathcal{C}_n|}{n} - C(G, P_V) \right| = \left| \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon(k(n))}^n(P_V)]) - C(G, P_V) \right| \quad (B.42)$$

$$\le \frac{1}{2k(n)} \qquad (B.43)$$

$$\underset{n \to \infty}{\to} 0; \qquad (B.44)$$

where (B.42) follows from the construction of $\mathcal{C}_n$; (B.43) is a consequence of (B.40); and (B.44) follows from (B.41).

Since for all $k \in \mathbb{N}^*$, $\mathcal{C}_n \subseteq \mathcal{T}_{\epsilon(k(n))}^n(P_V)$, we also have

$$\max_{v^n \in \mathcal{C}_n} \|T_{v^n} - P_V\|_{\infty} \le \epsilon(k(n)) \underset{n \to \infty}{\to} 0. \qquad (B.45)$$

Conversely, assume that for all $n \in \mathbb{N}^*$, $\mathcal{C}_n \subseteq \mathcal{V}^n$ is an independent set in $G^{\wedge n}$, such that

$$\max_{v^n \in \mathcal{C}_n} \|T_{v^n} - P_V\|_{\infty} \underset{n \to \infty}{\to} 0. \qquad (B.46)$$

Then for all $\epsilon > 0$ and $n$ large enough, $\mathcal{C}_n \in \mathcal{T}_{\epsilon}^n(P_V)$ and

$$\frac{1}{n} \log |\mathcal{C}_n| \le \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_V)]). \qquad (B.47)$$

By taking the limit superior when $n \to \infty$ and $\epsilon \to 0$ we obtain

$$\limsup_{n \to \infty} \frac{1}{n} \log |\mathcal{C}_n| \le C(G, P_V). \qquad (B.48)$$

## B.3.2 Proof of Theorem 5.1.4

($\le$) By definition of $C_0$ and $C(G, P_V)$ we have

$$\sup_{P_V \in \Delta(\mathcal{V})} C(G, P_V) = \sup_{P_V \in \Delta(\mathcal{V})} \limsup_{\epsilon \to 0} \lim_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_V)]) \qquad (B.49)$$
$$ \leq \sup_{P_V \in \Delta(\mathcal{V})} \lim_{\epsilon \to 0} \limsup_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}) \quad (B.50) $$

$$ = C_0(G). \quad (B.51) $$

(≥) Let $(C_n)_{n \in \mathbb{N}^*}$ be a sequence such that for all $n \in \mathbb{N}^*$, $C_n$ is an independent set in $G^{\wedge n}$, and

$$ \lim_{n \to \infty} \frac{1}{n} \log |C_n| = C_0(G); \quad (B.52) $$

the existence of the sequence $(C_n)_{n \in \mathbb{N}^*}$ follows from the definition of $C_0$.

Let $(\tau_n)_{n \in \mathbb{N}^*}$ be the sequence defined by: for all $n \in \mathbb{N}^*$,

$$ \tau_n \doteq \frac{1}{|C_n|} \sum_{v^n \in C_n} T_{v^n}. \quad (B.53) $$

The terms of the sequence $(\tau_n)_{n \in \mathbb{N}^*}$ are in $\Delta(\mathcal{V})$, which is a compact set. Therefore, by Bolzano-Weierstrass theorem, $(\tau_n)_{n \in \mathbb{N}^*}$ has a convergent subsequence $(\tau_{\phi(n)})_{n \in \mathbb{N}^*}$, where $\phi: \mathbb{N}^* \to \mathbb{N}^*$ is strictly increasing. We denote by $(C_{\phi(n)})_{n \in \mathbb{N}^*}$ the corresponding subsequence of independent sets, and

$$ P_V^* \doteq \lim_{n \to \infty} \tau_{\phi(n)} \in \Delta(\mathcal{V}). \quad (B.54) $$

By construction, we also have

$$ \lim_{n \to \infty} \frac{\log |C_{\phi(n)}|}{\phi(n)} = C_0(G). \quad (B.55) $$

Let us build an adequate sequence of codebooks with type converging uniformly to $P_V^*$, and with asymptotic rate $C_0(G)$. For all $n \in \mathbb{N}^*$, let

$$ C_{n\phi(n)}^* \doteq (C_{\phi(n)})^n \cap \mathcal{T}_{\epsilon_n}^{n\phi(n)}(P_V^*), \quad (B.56) $$

where $\epsilon_n \doteq \|P_V^* - \tau_{\phi(n)}\|_{\infty} + \frac{1}{\sqrt{n}}$.

It can be easily observed that $\epsilon_n \xrightarrow{n \to \infty} 0$ and $C_{n\phi(n)}^* \subseteq \mathcal{T}_{\epsilon_n}^{n\phi(n)}(P_V^*)$: by construction we have

$$ \max_{v^{n\phi(n)} \in C_{n\phi(n)}^*} \|T_{v^{n\phi(n)}} - P_V^*\|_{\infty} \xrightarrow{n \to \infty} 0. \quad (B.57) $$
Furthermore, for all $n \in \mathbb{N}^*$, $C_{n\phi(n)}^*$ is independent in $G^{\wedge n\phi(n)}$, as it is contained in the independent set $(C_{\phi(n)})^n$.

Now let us prove that $\frac{\log |C_{n\phi(n)}^*|}{n\phi(n)} \to C_0(G)$ when $n \to \infty$. Let us draw a codeword

$$C^{n\phi(n)} = (C_1^{\phi(n)}, \dots, C_n^{\phi(n)}) \qquad (B.58)$$

uniformly from $(C_{\phi(n)})^n$, and show that it is in $T_{\epsilon_n}^{n\phi(n)}(P_V^*)$ with high probability. On one hand, for all $t \le n$, the average type of $C_t^{\phi(n)}$ writes

$$\mathbb{E}[T_{C_t^{\phi(n)}}] = \frac{1}{|C_{\phi(n)}|} \sum_{c^{\phi(n)} \in C_{\phi(n)}} T_{c^{\phi(n)}} = \tau_{\phi(n)}. \qquad (B.59)$$

On the other hand,

$$\frac{|C_{n\phi(n)}^*|}{|(C_{\phi(n)})^n|} = \frac{|(C_{\phi(n)})^n \cap T_{\epsilon_n}^{n\phi(n)}(P_V^*)|}{|(C_{\phi(n)})^n|} \qquad (B.60)$$

$$= \mathbb{P}(C^{n\phi(n)} \in T_{\epsilon_n}^{n\phi(n)}(P_V^*)) \qquad (B.61)$$

$$= \mathbb{P}(\|T_{C^{n\phi(n)}} - P_V^*\|_{\infty} \le \epsilon_n) \qquad (B.62)$$

$$\ge \mathbb{P}(\|T_{C^{n\phi(n)}} - \tau_{\phi(n)}\|_{\infty} + \|\tau_{\phi(n)} - P_V^*\|_{\infty} \le \epsilon_n) \qquad (B.63)$$

$$= \mathbb{P}(\|T_{C^{n\phi(n)}} - \tau_{\phi(n)}\|_{\infty} \le n^{-1/4}) \qquad (B.64)$$

$$= \mathbb{P}(\left\| \frac{1}{n} \sum_{t \le n} T_{C_t^{\phi(n)}} - \tau_{\phi(n)} \right\|_{\infty} \le n^{-1/4}) \qquad (B.65)$$

$$= 1 - \mathbb{P}\left(\left\|\left(\sum_{t \le n} T_{C_t^{\phi(n)}}\right) - n\tau_{\phi(n)}\right\|_{\infty} > n^{3/4}\right) \qquad (B.66)$$

$$\ge 1 - \sum_{v \in \mathcal{V}} \mathbb{P}\left(\left|\sum_{t \le n} T_{C_t^{\phi(n)}}(v) - n\tau_{\phi(n)}(v)\right| > n^{3/4}\right) \qquad (B.67)$$

$$\ge 1 - \sum_{v \in \mathcal{V}} \frac{1}{n^{3/2}} \mathbb{V}\left[\sum_{t \le n} T_{C_t^{\phi(n)}}(v)\right] \qquad (B.68)$$

$$\ge 1 - \frac{|\mathcal{V}|}{n^{1/2}} \to 1; \qquad (B.69)$$

where (B.61) and (B.65) come from the construction of $C^{n\phi(n)}$; (B.64) comes from the construction of $\epsilon_n$; (B.67) follows from the union bound; (B.68) comes from Chebyshev's inequality and (B.59); (B.69) follows from $\mathbb{V}[\sum_{t \le n} T_{C_t^{\phi(n)}}(v)] = \sum_{t \le n} \mathbb{V}[T_{C_t^{\phi(n)}}(v)] \le n$, as the random variables $T_{C_t^{\phi(n)}}(v)$ are iid and takes values in $[0, 1]$. Hence

$$\lim_{n \to \infty} \frac{\log |C_{n\phi(n)}^*|}{n\phi(n)} = \lim_{n \to \infty} \frac{\log |(C_{\phi(n)})^n|}{n\phi(n)} = C_0(G). \qquad (B.70)$$
By combining (B.57), (B.70) and Lemma 5.1.3, it follows that

$$C_0(G) = \lim_{n \to \infty} \frac{\log |\mathcal{C}_{n\phi(n)}^*|}{n\phi(n)} \le C(G, P_V). \quad (B.71)$$

### B.3.3 Proof of Proposition 5.3.2

Let us show that for all graph $G = (\mathcal{V}, \mathcal{E})$, the function $P_V \mapsto C(G, P_V)$ is concave. Let $P_V, P'_V \in \Delta(\mathcal{V})$ and $\beta \in [0, 1]$. Let $(b_n)_{n \in \mathbb{N}}$ be a sequence of integers such that $\frac{b_n}{n} \to \beta$.

By Lemma 5.1.3, there exists two sequences $(C_n)_{n \in \mathbb{N}}$ and $(C'_n)_{n \in \mathbb{N}}$ that satisfy the following:

$$\forall n \in \mathbb{N}^*, C_n \subseteq \mathcal{V}^n \text{ and } C'_n \subseteq \mathcal{V}^n \text{ are independent in } G^{\wedge n}; \quad (B.72)$$

and

$$\frac{\log |\mathcal{C}_n|}{n} \underset{n \to \infty}{\to} C(G, P_V), \qquad \frac{\log |\mathcal{C}'_n|}{n} \underset{n \to \infty}{\to} C(G, P'_V), \quad (B.73)$$

$$\max_{v^n \in \mathcal{C}_n} \|T_{v^n} - P_V\|_{\infty} \underset{n \to \infty}{\to} 0, \qquad \max_{v^n \in \mathcal{C}'_n} \|T_{v^n} - P_V\|_{\infty} \underset{n \to \infty}{\to} 0. \quad (B.74)$$

Let us build a sequence of codebooks $(C''_n)_{n \in \mathbb{N}^*}$ adapted to the distribution $\beta P_V + (1 - \beta) P'_V$ by using a time-sharing between $(C_n)_{n \in \mathbb{N}^*}$ and $(C'_n)_{n \in \mathbb{N}^*}$. For all $n \in \mathbb{N}^*$, let

$$C_n'' \doteq C_n^{b_n} \times C_n'^{n-b_n}. \quad (B.75)$$

For all $n \in \mathbb{N}^*$, $C_n'' \subseteq \mathcal{V}^{n^2}$ is independent in $G^{\wedge n^2}$ as a product of independent sets.

The rate associated to $C_n''$ writes

$$\frac{\log |\mathcal{C}_n''|}{n^2} = \frac{b_n \log |\mathcal{C}_n| + (n - b_n) \log |\mathcal{C}_n'|}{n^2} \quad (B.76)$$

$$= \frac{b_n \log |\mathcal{C}_n|}{n} + \frac{n - b_n \log |\mathcal{C}_n'|}{n} \quad (B.77)$$

$$\underset{n \to \infty}{\to} \beta C(G, P_V) + (1 - \beta) C(G, P'_V); \quad (B.78)$$

and the types of the codewords in $C_n''$ satisfy

$$\max_{v^{n^2} \in \mathcal{C}_n''} \|T_{v^{n^2}} - \beta P_V - (1 - \beta) P'_V\|_{\infty} \quad (B.79)$$
$$ = \max_{v^{nb_n} \in \mathcal{C}_n} \max_{v'^{n(n-b_n)} \in \mathcal{C}'_n} \left\| \frac{nb_n}{n^2} T_{v^{nb_n}} + \frac{n(n-b_n)}{n^2} T_{v'^{n(n-b_n)}} - \beta P_V - (1-\beta)P'_V \right\|_{\infty} \quad (B.80) $$

$$ \leq \max_{v^{nb_n} \in \mathcal{C}_n} \left\| \frac{b_n}{n} T_{v^{nb_n}} - \beta P_V \right\|_{\infty} + \max_{v'^{n(n-b_n)} \in \mathcal{C}'_n} \left\| \frac{n-b_n}{n} T_{v'^{n(n-b_n)}} - (1-\beta)P'_V \right\|_{\infty} \quad (B.81) $$

$$ = \beta \max_{v^{nb_n} \in \mathcal{C}_n} \left\| T_{v^{nb_n}} - P_V + o(1)T_{v^{nb_n}} \right\|_{\infty} \\ + (1-\beta) \max_{v'^{n(n-b_n)} \in \mathcal{C}'_n} \left\| T_{v'^{n(n-b_n)}} - P'_V + o(1)T_{v'^{n(n-b_n)}} \right\|_{\infty} \quad (B.82) $$

$$ \leq \beta \max_{v^{nb_n} \in \mathcal{C}_n} \left\| T_{v^{nb_n}} - P_V \right\|_{\infty} + o(1) \left\| T_{v^{nb_n}} \right\|_{\infty} \\ + (1-\beta) \max_{v'^{n(n-b_n)} \in \mathcal{C}'_n} \left\| T_{v'^{n(n-b_n)}} - P'_V \right\|_{\infty} + o(1) \left\| T_{v'^{n(n-b_n)}} \right\|_{\infty} \quad (B.83) $$

$$ \xrightarrow{n \to \infty} 0. \quad (B.84) $$

By Lemma 5.1.3, $\lim_{n \to \infty} \frac{\log |\mathcal{C}_n''|}{n^2} \leq C(G, \beta P_V + (1-\beta)P'_V)$, thus

$$ \beta C(G, P_V) + (1-\beta)C(G, P'_V) \leq C(G, \beta P_V + (1-\beta)P'_V). \quad (B.85) $$

The function $P_V \mapsto C(G, P_V)$ is concave on the convex compact set $\Delta(\mathcal{V})$, therefore its set of maximizers $\mathcal{P}^*(G) = \operatorname*{argmax}_{P_V \in \Delta(\mathcal{V})} C(G, P_V)$ is convex. Furthermore, by Theorem 5.1.4, the set $\mathcal{P}^*(G)$ is nonempty and satisfies

$$ \forall P_V \in \mathcal{P}^*(G), C(G, P_V) = C_0(G). \quad (B.86) $$

### B.3.4 Proof of Theorem 5.3.3

The proof techniques used here are similar as in the proof of Theorem 5.1.4 in Appendix B.3.2.

Let us start by showing that Theorem 5.3.3 is true when $\mathcal{A}$ has two elements. Let $G = (\mathcal{V}, \mathcal{E})$, and $G' = (\mathcal{V}', \mathcal{E}')$ be two graphs, and let $P_{V,V'} \in \mathcal{P}^*(G \wedge G')$. We will prove that $P_V \otimes P_{V'}$ is also capacity-achieving by building an adequate sequence of codebooks.

For all $n \in \mathbb{N}^*$, let $\mathcal{C}_n \subseteq (\mathcal{V} \times \mathcal{V}')^n$ such that $\mathcal{C}_n$ is an independent set in $(G \wedge G')^{\wedge n}$, and

$$ \frac{1}{n} \log |\mathcal{C}_n| \xrightarrow{n \to \infty} C_0(G \wedge G'), \quad (B.87) $$

$$ \max_{(v^{n}, v'^{n}) \in \mathcal{C}_n} \| T_{v^{n}, v'^{n}} - P_{V,V'} \|_{\infty} \xrightarrow{n \to \infty} 0. \quad (B.88) $$
The existence of such a sequence is given by Lemma 5.1.3, and Proposition 5.3.2. Let

$$Q_{V,V'}^{(n)} \doteq \frac{1}{|C_n|} \sum_{(v^n, v'^n) \in C_n} T_{v^n, v'^n}. \qquad (B.89)$$

An immediate observation is that

$$Q_{V,V'}^{(n)} \underset{n \to \infty}{\to} P_{V,V'} \qquad (B.90)$$

as a consequence of (B.88).

Let us build a sequence of codebooks with asymptotic rate $C_0(G \wedge G')$, such that the type of their codewords converge uniformly to $P_V \otimes P_{V'}$:

$$C_{n^3}^* \doteq \mathcal{T}_{\epsilon_n}^{n^3} (P_V \otimes P_{V'}) \cap \left( \prod_{t \le n} C_n^{(t)} \right)^n; \qquad (B.91)$$

where

$$\epsilon_n \doteq \|Q_V^{(n)} \otimes Q_{V'}^{(n)} - P_V \otimes P_{V'}\|_{\infty} + \frac{1}{\sqrt{n}}; \qquad (B.92)$$

and where for all $t \le n$, the shifted codebook $C_n^{(t)}$ is defined by

$$C_n^{(t)} \doteq \left\{ \left( (v_t, v_{t+1}, \dots, v_n, v_1, \dots, v_{t-1}), v'^n \right) \mid (v^n, v'^n) \in C_n \right\}. \qquad (B.93)$$

By construction, $C_{n^3}^* \subseteq \mathcal{T}_{\epsilon_n}^{n^3} (P_V \otimes P_{V'})$ thanks to (B.91), and $\epsilon_n \underset{n \to \infty}{\to} 0$ thanks to (B.92) and (B.90); therefore we have

$$\max_{v^{n^3} \in C_n^*} \|T_{v^{n^3}} - P_V \otimes P_{V'}\|_{\infty} \underset{n \to \infty}{\to} 0. \qquad (B.94)$$

Furthermore, $C_{n^3}^*$ is an independent set in $(G \wedge G')^{\wedge n^3}$, as it is contained in the product independent set $(\prod_{t \le n} C_n^{(t)})^n$; note that this holds because the shifted codebook $C_n^{(t)}$ is an independent set in $(G \wedge G')^{\wedge n}$ for all $t \le n$.

Now let us prove that $\frac{\log |C_{n^3}^*|}{n^3} \underset{n \to \infty}{\to} C_0(G \wedge G')$. Let us draw a codeword uniformly from $(\prod_{t \le n} C_n^{(t)})^n$:

$$C^{n^3} \doteq (C_1^{n^2}, \dots, C_n^{n^2}), \qquad (B.95)$$
where for all $t \le n$, $C_t^{n2}$ is a random $n \times n$-sequence drawn uniformly from $\prod_{t \le n} C_n^{(t)}$. We want to prove that $C^{n3} \in \mathcal{T}_{\epsilon_n}^{n3}(P_V \otimes P_{V'})$ with high probability.

On one hand we have to determine the average type of the random variables $(C_t^{n2})_{t \le n}$ which are iid copies of $C^{n2} = (C_1^n, \dots, C_n^n)$; where each $C_t^n$ is drawn uniformly from $C_n^{(t)}$, and the $(C_t^n)_{t \le n}$ are mutually independent.

$$ \mathbb{E}[T_{C_t^{n2}}] = \frac{1}{n} \sum_{t \le n} \mathbb{E}[T_{C_t^n}] \qquad (B.96) $$

$$ = \frac{1}{n} \sum_{t \le n} \frac{1}{|C_n^{(t)}|} \sum_{(v^n, v'^n) \in C_n^{(t)}} T_{v^n, v'^n} \qquad (B.97) $$

$$ = \frac{1}{n} \sum_{t \le n} \frac{1}{|C_n|} \sum_{(v^n, v'^n) \in C_n} T_{\sigma_t(v^n), v'^n} \qquad (B.98) $$

$$ = \frac{1}{|C_n|} \sum_{(v^n, v'^n) \in C_n} \frac{1}{n} \sum_{t \le n} T_{\sigma_t(v^n), v'^n} \qquad (B.99) $$

$$ = \frac{1}{|C_n|} \sum_{(v^n, v'^n) \in C_n} T_{v^n} \otimes T_{v'^n} \qquad (B.100) $$

$$ = Q_V^{(n)} \otimes Q_{V'}^{(n)}, \qquad (B.101) $$

where $\sigma_t(v^n) = (v_t, v_{t+1}, \dots, v_n, v_1, \dots, v_{n-1})$; (B.98) comes from the construction of $C_n^{(t)}$ in (B.93); and (B.100) comes from the following observation:

$$ \sum_{t \le n} T_{\sigma_t(v^n), v'^n} = \sum_{t \le n} \sum_{s \le n} T_{v_{s+t}, v'_s} = \sum_{s \le n} \sum_{t \le n} T_{v_{s+t}, v'_s} \qquad (B.102) $$

$$ = \sum_{s \le n} T_{v^n, (v'_s, \dots, v'_s)} = \sum_{s \le n} T_{v^n} \otimes T_{v'_s} = T_{v^n} \otimes T_{v'^n}, \qquad (B.103) $$

where the index $s+t$ is taken modulo $n$.

On the other hand we have

$$ \frac{|C_{n^3}^*|}{|\left(\prod_{t \le n} C_n^{(t)}\right)^n|} \qquad (B.104) $$

$$ = \frac{|\mathcal{T}_{\epsilon_n}^{n3}(P_V \otimes P_{V'}) \cap \left(\prod_{t \le n} C_n^{(t)}\right)^n|}{\left|\left(\prod_{t \le n} C_n^{(t)}\right)^n\right|} \qquad (B.105) $$

$$ = \mathbb{P}(C^{n3} \in \mathcal{T}_{\epsilon_n}^{n3}(P_V \otimes P_{V'})) \qquad (B.106) $$

$$ = \mathbb{P}\left(\left\|\frac{1}{n}\sum_{t \le n} T_{C_t^{n2}} - P_V \otimes P_{V'}\right\|_{\infty} \le \epsilon_n\right) \qquad (B.107) $$
$$ \geq \mathbb{P} \left( \left\| \frac{1}{n} \sum_{t \leq n} T_{C_t^{n^2}} - Q_V^{(n)} \otimes Q_{V'}^{(n)} \right\|_{\infty} + \left\| Q_V^{(n)} \otimes Q_{V'}^{(n)} - P_V \otimes P_{V'} \right\|_{\infty} \leq \epsilon_n \right) \quad (B.108) $$

$$ = \mathbb{P} \left( \left\| \sum_{t \le n} T_{C_t^{n^2}} - nQ_V^{(n)} \otimes Q_{V'}^{(n)} \right\|_{\infty} \le n^{3/4} \right) \quad (B.109) $$

$$ \geq 1 - \sum_{(v,v') \in V \times V'} \mathbb{P} \left( \left| \sum_{t \le n} T_{C_t^{n^2}}(v, v') - nQ_V^{(n)} \otimes Q_{V'}^{(n)}(v, v') \right| > n^{3/4} \right) \quad (B.110) $$

$$ \geq 1 - \sum_{(v,v') \in V \times V'} \frac{1}{n^{3/2}} \mathbb{V} \left[ \sum_{t \le n} T_{C_t^{n^2}}(v, v') \right] \quad (B.111) $$

$$ \geq 1 - \frac{|V||V'|}{n^{1/2}} \xrightarrow{n \to \infty} 1; \quad (B.112) $$

where (B.106) and (B.107) come from the construction of $C^{n^3}$; (B.109) comes from the construction of $\epsilon_n$; (B.110) follows from the union bound; (B.111) comes from Chebyshev's inequality and (B.101); and (B.112) comes from the fact that $\mathbb{V}[\sum_{t \le n} T_{C_t^{n^2}}(v, v')] = \sum_{t \le n} \mathbb{V}[T_{C_t^{n^2}}(v, v')] \le n$, as the random variables $T_{C_t^{n^2}}(v, v')$ are iid and takes values in $[0, 1]$. Hence

$$ \lim_{n \to \infty} \frac{\log |\mathcal{C}_{n^3}|}{n^3} = \lim_{n \to \infty} \frac{\log \left| \left( \prod_{t \le n} \mathcal{C}_n^{(t)} \right)^n \right|}{n^3} = \lim_{n \to \infty} \frac{\log |\mathcal{C}_n|}{n} = C_0(G \wedge G'); \quad (B.113) $$

where the second equality holds as the shifted codebooks $(\mathcal{C}_n^{(t)})_{t \le n}$ all have cardinality $|\mathcal{C}_n|$.

Thus, by combining (B.113), Lemma 5.1.3, and Proposition 5.3.2 we obtain

$$ C_0(G \wedge G') = \lim_{n \to \infty} \frac{\log |\mathcal{C}_{n^3}|}{n^3} \le C(G \wedge G', P_V \otimes P_{V'}) \le C_0(G \wedge G'), \quad (B.114) $$

hence $P_V \otimes P_{V'} \in \mathcal{P}^*(G \wedge G')$.

Therefore, Theorem 5.3.3 is proved when $\mathcal{A}$ has two elements:

$$ P_{V,V'} \in \mathcal{P}^*(G \wedge G') \implies P_V \otimes P_{V'} \in \mathcal{P}^*(G \wedge G'). \quad (B.115) $$

Now let us consider the case where $\mathcal{A}$ has a cardinality greater than 2. Let $P_{V_1, \dots, V_A} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$. By considering the product graphs

$$ \bigwedge_{a \in \mathcal{A}} G_a = \left( \bigwedge_{1 \le i < i^*} G_i \right) \wedge \left( \bigwedge_{i^* \le i \le |\mathcal{A}|} G_i \right); \quad (B.116) $$

for all $i^* \le |\mathcal{A}|$, and applying (B.115) successively, we obtain

$$ P_{V_1, \dots, V_A} \in \mathcal{P}^* (\bigwedge_{a \in \mathcal{A}} G_a) \implies P_{V_1} \otimes P_{V_2, \dots, V_{|\mathcal{A}|}} \in \mathcal{P}^* (\bigwedge_{a \in \mathcal{A}} G_a) \quad (B.117) $$
$$ \implies (P_{V_1} \otimes P_{V_2}) \otimes P_{V_3, \dots, V_{|A|}} \in \mathcal{P}^*(\bigwedge_{a \in A} G_a) \quad (B.118) $$

$$ \implies \dots \quad (B.119) $$

$$ \implies \bigotimes_{a \in A} P_{V_a} \in \mathcal{P}^*(\bigwedge_{a \in A} G_a). \quad (B.120) $$

### B.3.5 Proof of Lemma 5.3.7

Let $G$ be a vertex-transitive graph, and let $P_V \in \mathcal{P}^*(G)$. Let $\psi \in \mathrm{Aut}(G)$, we first prove that $P_{\psi(V)} \in \mathcal{P}^*(G)$, then we will conclude by using the convexity of $\mathcal{P}^*(G)$.

Let $(C_n)_{n \in \mathbb{N}^*}$ be a sequence such that

$$ \forall n \in \mathbb{N}^*, C_n \subseteq \mathcal{V}^n \text{ is an independent set in } G^{\wedge n}, \quad (B.121) $$

$$ \max_{v^n \in C_n} \|T_{v^n} - P_V\|_{\infty} \xrightarrow{n \to \infty} 0, \quad (B.122) $$

$$ \frac{\log |C_n|}{n} \xrightarrow{n \to \infty} C(G, P_V) = C_0(G). \quad (B.123) $$

The existence of such a sequence is given by Lemma 5.1.3. Note that the last equality in (B.123) comes from the assumption $P_V \in \mathcal{P}^*(G)$.

Now, for all $n \in \mathbb{N}^*$ the codebook

$$ \psi(C_n) = \{(\psi(v_1), \dots, \psi(v_n)) \mid v^n \in C_n\} \quad (B.124) $$

is also independent in $G^{\wedge n}$, as $\psi$ is a graph automorphism and therefore preserves adjacencies. We have by construction

$$ \max_{v^n \in \psi(C_n)} \|T_{v^n} - P_{\psi(V)}\|_{\infty} \xrightarrow{n \to \infty} 0. \quad (B.125) $$

Furthermore, since $\psi$ is a bijection we have $|\psi(C_n)| = |C_n|$ for all $n \in \mathbb{N}^*$, thus

$$ \frac{\log |\psi(C_n)|}{n} = \frac{\log |C_n|}{n} \xrightarrow{n \to \infty} C_0(G). \quad (B.126) $$

Hence

$$ P_{\psi(V)} \in \mathcal{P}^*(G). \quad (B.127) $$

Now, for all $v, v' \in \mathcal{V}$, denote by $S_{v' \to v} \subseteq \mathrm{Aut}(G)$ the set of automorphisms that map $v'$ to $v$; note that this set is nonempty thanks to the vertex-transitivity of $G$. We have for
all $v \in \mathcal{V}$

$$ \mathrm{Aut}(G) = \bigsqcup_{v' \in \mathcal{V}} \mathcal{S}_{v' \to v}. \qquad (\mathrm{B}.128) $$

Furthermore, for all $v \in \mathcal{V}$, all the sets $(\mathcal{S}_{v' \to v})_{v' \to v}$ have the same cardinality: for all $v', v'' \in \mathcal{V}$,

$$ \mathcal{S}_{v'' \to v} \circ \psi_1 \subseteq \mathcal{S}_{v' \to v}, \qquad (\mathrm{B}.129) $$

where $\psi_1 \in \mathcal{S}_{v' \to v''}$. It follows that for all $v, v' \in \mathcal{V}$,

$$ |\mathcal{S}_{v' \to v}| = \frac{|\mathrm{Aut}(G)|}{|\mathcal{V}|}. \qquad (\mathrm{B}.130) $$

Therefore, for all $v \in \mathcal{V}$ we have

$$ \frac{1}{|\mathrm{Aut}(G)|} \sum_{\psi \in \mathrm{Aut}(G)} P_{\psi(v)} \quad \in \mathcal{P}^*(G) \qquad (\mathrm{B}.131) $$

$$ = \left( \frac{1}{|\mathrm{Aut}(G)|} \sum_{\psi \in \mathrm{Aut}(G)} P_V(\psi^{-1}(v)) \right)_{v \in \mathcal{V}} \qquad (\mathrm{B}.132) $$

$$ = \left( \frac{1}{|\mathrm{Aut}(G)|} \sum_{v' \in \mathcal{V}} |\mathcal{S}_{v' \to v}| P_V(v') \right)_{v \in \mathcal{V}} \qquad (\mathrm{B}.133) $$

$$ = \left( \frac{1}{|\mathrm{Aut}(G)|} \sum_{v' \in \mathcal{V}} \frac{|\mathrm{Aut}(G)|}{|\mathcal{V}|} P_V(v') \right)_{v \in \mathcal{V}} \qquad (\mathrm{B}.134) $$

$$ = \mathrm{Unif}(\mathcal{V}); \qquad (\mathrm{B}.135) $$

where (B.131) comes from the convexity of $\mathcal{P}^*(G)$ given by Proposition 5.3.2 and (B.127);
(B.133) comes from (B.128); and (B.134) comes from (B.130).

# B.4 Main proofs for the link between linearizations of $C(\cdot, P_V)$ and $C_0$

## B.4.1 Proof of Theorem 5.4.1

We prove Theorem 5.4.1 in two steps, which are Lemma B.4.1 and Lemma B.4.2. The proofs are respectively given in Appendix B.4.2 and B.4.3.
**Lemma B.4.1**

$$C_0 \left( \bigwedge_{a \in \mathcal{A}} G_a \right) = \sum_{a \in \mathcal{A}} C_0(G_a) \qquad (B.136)$$

$$\implies \forall (P_{V_a}^*)_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a), \left\{ \begin{array}{l} \bigotimes_{a \in \mathcal{A}} P_{V_a}^* \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a) \text{ and} \\ C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}^*) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*). \end{array} \right. \qquad (B.137)$$

**Lemma B.4.2** For all $P_{V_1,...,V_{|\mathcal{A}|}} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$, the following holds

$$C \left( \bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a} \right) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) \qquad (B.138)$$

$$\implies C_0 \left( \bigwedge_{a \in \mathcal{A}} G_a \right) = \sum_{a \in \mathcal{A}} C_0(G_a) \text{ and } \forall a \in \mathcal{A}, P_{V_a} \in \mathcal{P}^*(G_a). \qquad (B.139)$$

Let us prove Theorem 5.4.1. Let $(P_{V_a}^*)_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a)$, we have by Lemma B.4.1

$$C_0(\bigwedge_{a \in \mathcal{A}} G_a) = \sum_{a \in \mathcal{A}} C_0(G_a) \qquad (B.140)$$

$$\implies \bigotimes_{a \in \mathcal{A}} P_{V_a}^* \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a) \text{ and } C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}^*) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*) \qquad (B.141)$$

$$\implies \exists P_{V_1,...,V_{|\mathcal{A}|}} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a), C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}). \qquad (B.142)$$

Conversely, by Lemma B.4.2 we have

$$\exists P_{V_1,...,V_{|\mathcal{A}|}} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a), C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) \qquad (B.143)$$

$$\implies C_0(\bigwedge_{a \in \mathcal{A}} G_a) = \sum_{a \in \mathcal{A}} C_0(G_a), \qquad (B.144)$$

and any $P_{V_1,...,V_{|\mathcal{A}|}}$ that satisfies (B.143) also satisfies $(P_{V_a})_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a)$.

## B.4.2 Proof of Lemma B.4.1

For all family of graphs $(G_a)_{a \in \mathcal{A}}$, and distributions $(P_{V_a}^*)_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a)$ the following holds:

$$C_0(\bigwedge_{a \in \mathcal{A}} G_a) = \max_{(P_{V_a})_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \Delta(V_a)} C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}) \qquad (B.145)$$
$$ \geq C (\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}^*) \qquad (B.146) $$

$$ \geq \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*) \qquad (B.147) $$

$$ = \sum_{a \in \mathcal{A}} C_0(G_a); \qquad (B.148) $$

where (B.145) and (B.146) follow from Corollary 5.3.4; (B.147) comes from Proposition 5.2.5; and (B.148) follows from Proposition 5.3.2.

Now assume that $\sum_{a \in \mathcal{A}} C_0(G_a) = C_0(\bigwedge_{a \in \mathcal{A}} G_a)$, then equality holds in (B.145) to (B.148). In particular, we have

$$ C_0(\bigwedge_{a \in \mathcal{A}} G_a) = C(\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}^*), \quad \text{hence } \otimes_{a \in \mathcal{A}} P_{V_a}^* \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a); \qquad (B.149) $$

$$ C(\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}^*) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*). \qquad (B.150) $$

### B.4.3 Proof of Lemma B.4.2

Let $P_{V_1, \dots, V_{|\mathcal{A}|}} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$, by Theorem 5.3.3, we have

$$ \otimes_{a \in \mathcal{A}} P_{V_a} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a). \qquad (B.151) $$

Additionally, for all $(P_{V_a}^*)_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a)$ we have for all $a \in \mathcal{A}$

$$ C(G_a, P_{V_a}) \leq C(G_a, P_{V_a}^*), \qquad (B.152) $$

and the following holds

$$ C(\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}) \qquad (B.153) $$

$$ \geq C (\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}^*) \qquad (B.154) $$

$$ \geq \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*) \qquad (B.155) $$

$$ \geq \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}); \qquad (B.156) $$

where (B.154) comes from (B.151); (B.155) comes from Proposition 5.2.5; and (B.156) comes from (B.152).

Now assume that

$$ C(\bigwedge_{a \in \mathcal{A}} G_a, \otimes_{a \in \mathcal{A}} P_{V_a}) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}), \qquad (B.157) $$
then equality holds in (B.153) to (B.156). In particular, we have for all $a \in \mathcal{A}$:

$$C(G_a, P_{V_a}) = C(G_a, P_{V_a}^*) \qquad (B.158)$$

as a consequence of $\sum_{a \in \mathcal{A}} C(G_a, P_{V_a}^*) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a})$ and (B.152). Hence $P_{V_a}$ also maximizes $C(G_a, \cdot)$ for all $a \in \mathcal{A}$:

$$\forall a \in \mathcal{A}, P_{V_a} \in \mathcal{P}^*(G_a). \qquad (B.159)$$

Furthermore,

$$C_0(\bigwedge_{a \in \mathcal{A}} G_a) = C(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}) \qquad (B.160)$$

$$= \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) \qquad (B.161)$$

$$= \sum_{a \in \mathcal{A}} C_0(G_a); \qquad (B.162)$$

where (B.160) comes from Corollary 5.3.4; (B.161) follows from (B.157); and (B.162) comes from (B.159) and Proposition 5.3.2.

### B.4.4 Proof of Theorem 5.4.2

The techniques used in this proof are the same as in the proof of Theorem 5.4.1. We prove Theorem 5.4.2 in two steps, which are Lemma B.4.3 and Lemma B.4.4; their proofs are respectively given in Appendix B.4.5 and B.4.6.

**Lemma B.4.3 Let**

$$P_A^* \doteq \left( \frac{2^{C_0(G_a)}}{\sum_{a' \in \mathcal{A}} 2^{C_0(G_{a'})}} \right)_{a \in \mathcal{A}}, \qquad (B.163)$$

we have

$$C_0\left(\bigcup_{a \in \mathcal{A}} G_a\right) = \log\left(\sum_{a \in \mathcal{A}} 2^{C_0(G_a)}\right) \\ \implies \forall (P_{V_a}^*)_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a), \sum_{a \in \mathcal{A}} P_A^*(a) P_{V_a}^* \in \mathcal{P}^*\left(\bigcup_{a \in \mathcal{A}} G_a\right) \text{ and} \\ C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A^*(a) P_{V_a}^*\right) = H(P_A^*) + \sum_{a \in \mathcal{A}} P_A^*(a) C(G_a, P_{V_a}^*), \qquad (B.164)$$
**Lemma B.4.4 Let**

$$ P_A^* \doteq \left( \frac{2^{C_0(G_a)}}{\sum_{a' \in A} 2^{C_0(G_{a'})}} \right)_{a \in A}, \qquad (B.165) $$

for all $\sum_{a \in A} P_A(a)P_{V_a} \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a)$ the following holds

$$ \begin{gathered} C\left(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in A} P_A(a)C(G_a, P_{V_a}) \\ \implies C_0\left(\bigsqcup_{a \in A} G_a\right) = \log\left(\sum_{a \in A} 2^{C_0(G_a)}\right), \quad (P_{V_a})_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a), \text{ and } P_A = P_A^*. \end{gathered} \qquad (B.166) $$

Now let us prove Theorem 5.4.2. Let $(P_{V_a}^*)_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a)$, we have by Lemma B.4.3

$$ \begin{gathered} C_0(\bigsqcup_{a \in A} G_a) = \log\left(\sum_{a \in A} 2^{C_0(G_a)}\right) \qquad (B.167) \\ \implies \sum_{a \in A} P_A^*(a)P_{V_a}^* \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a) \text{ and} \end{gathered} $$

$$ C\left(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A^*(a)P_{V_a}^*\right) = H(P_A^*) + \sum_{a \in A} P_A^*(a)C(G_a, P_{V_a}^*), \qquad (B.168) $$

$$ \begin{gathered} \implies \exists P_V \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a), \\ C\left(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A^*(a)P_{V_a}^*\right) = H(P_A^*) + \sum_{a \in A} P_A^*(a)C(G_a, P_{V_a}^*), \end{gathered} $$

where $P_{V_a}^* = P_{V|V \in V_a}$ and $P_A^*(a) = P_V(V_a)$ for all $a \in A$.

Conversely, by Lemma B.4.4 we have

$$ \exists P_V \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a), \qquad (B.169) $$

$$ \begin{gathered} C\left(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in A} P_A(a)C(G_a, P_{V_a}) \\ \implies C_0\left(\bigsqcup_{a \in A} G_a\right) = \log\left(\sum_{a \in A} 2^{C_0(G_a)}\right), \end{gathered} \qquad (B.170) $$

and any $P_V = \sum_{a \in A} P_A(a)P_{V_a}$ that satisfies (B.169) also satisfies

$$ (P_{V_a})_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a), \text{ and } P_A = \left( \frac{2^{C_0(G_a)}}{\sum_{a' \in A} 2^{C_0(G_{a'})}} \right)_{a \in A}. \qquad (B.171) $$
### B.4.5 Proof of Lemma B.4.3

Lemma B.4.5 states that the function $(w_a)_{a \in A} \mapsto \log(\sum_{a \in A} 2^{w_a})$ is the Legendre-Fenchel conjugate [69] of the entropy function $P_A \mapsto H(P_A)$. The proof of Lemma B.4.5 is given in Appendix B.6.8.

**Lemma B.4.5** Let $(w_a)_{a \in A} \in \mathbb{R}^{|A|}$, then the mapping

$$ \zeta: P_A \mapsto H(P_A) + \sum_{a \in A} P_A(a)w_a \quad (B.172) $$

has a unique maximum

$$ P_A^* = \left( \frac{2^{w_a}}{\sum_{a' \in A} 2^{w_{a'}}} \right)_{a \in A}; \quad (B.173) $$

and

$$ \zeta(P_A^*) = \log \left( \sum_{a \in A} 2^{w_a} \right). \quad (B.174) $$

Now let us prove Lemma B.4.3. Let

$$ \sum_{a \in A} P_A(a) P_{V_a} \in \mathcal{P}^* (\bigcup_{a \in A} G_a), \quad (B.175) $$

$$ (P_{V_a}^*)_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a), \quad (B.176) $$

$$ P_A^* = \left( \frac{2^{C_0(G_a)}}{\sum_{a' \in A} 2^{C_0(G_{a'})}} \right)_{a \in A}. \quad (B.177) $$

We have

$$ C_0(\bigcup_{a \in A} G_a) = C(\bigcup_{a \in A} P_A^* G_a, \sum_{a \in A} P_A(a) P_{V_a}^*) \quad (B.178) $$

$$ \geq C \left( \bigcup_{a \in A} P_A^* G_a, \sum_{a \in A} P_A^*(a) P_{V_a}^* \right) \quad (B.179) $$

$$ \geq H(P_A^*) + \sum_{a \in A} P_A^*(a) C(G_a, P_{V_a}^*) \quad (B.180) $$

$$ = H(P_A^*) + \sum_{a \in A} P_A^*(a) C_0(G_a) \quad (B.181) $$

$$ = \log \left( \sum_{a \in A} 2^{C_0(G_a)} \right); \quad (B.182) $$

where (B.178) and (B.179) come from (B.175) and Proposition 5.3.2; (B.180) comes from
Proposition 5.2.5; (B.181) comes from (B.176) and Proposition 5.3.2; and (B.182) comes from (B.177) and Lemma B.4.5.

Assume that $C_0(\bigsqcup_{a \in A} G_a) = \log(\sum_{a \in A} 2^{C_0(G_a)})$, then equality holds in (B.178) to (B.182), therefore the following holds:

$$
\begin{align*}
C_0(\bigsqcup_{a \in A} G_a) &= \log \left( \sum_{a \in A} 2^{C_0(G_a)} \right) \\
\implies \forall (P_{V_a}^*)_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a), \quad \sum_{a \in A} P_A^*(a) P_{V_a}^* \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a) \text{ and} \\
C(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A^*(a) P_{V_a}^*) &= H(P_A^*) + \sum_{a \in A} P_A^*(a) C(G_a, P_{V_a}^*). \tag{B.183}
\end{align*}
$$

B.4.6 Proof of Lemma B.4.4

Let

$$
\sum_{a \in A} P_A(a) P_{V_a} \in \mathcal{P}^* (\bigsqcup_{a \in A} G_a), \quad (B.184)
$$

$$
(P_{V_a}^*)_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a), \qquad (B.185)
$$

$$
P_A^* \doteq \left( \frac{2^{C_0(G_a)}}{\sum_{a' \in A} 2^{C_0(G_{a'})}} \right)_{a \in A} . \qquad (B.186)
$$

We have

$$
C(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A(a) P_{V_a}) = C_0(\bigsqcup_{a \in A} G_a) \quad (B.187)
$$

$$
\geq \log \left( \sum_{a \in A} 2^{C_0(G_a)} \right) \qquad (B.188)
$$

$$
= H(P_A^*) + \sum_{a \in A} P_A^*(a) C_0(G_a) \qquad (B.189)
$$

$$
\geq H(P_A) + \sum_{a \in A} P_A(a) C_0(G_a) \qquad (B.190)
$$

$$
= H(P_A) + \sum_{a \in A} P_A(a) C(G_a, P_{V_a}^*) \qquad (B.191)
$$

$$
\geq H(P_A) + \sum_{a \in A} P_A(a) C(G_a, P_{V_a}); \qquad (B.192)
$$

where (B.187) comes from (B.184) and Proposition 5.3.2; (B.188) comes from Theorem
5.1.17; (B.189) and (B.190) come from (B.186) and Lemma B.4.5, which can be found in
Appendix B.4.5; (B.191) and (B.192) come from (B.185) and Proposition 5.3.2.

Assume that $C(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A(a)P_{V_a}) = H(P_A) + \sum_{a \in A} P_A(a)C(G_a, P_{V_a})$, then equality holds in (B.187) to (B.192). In particular $P_A = P_A^*$ as a consequence of the equality between (B.189) and (B.190); and $(P_{V_a})_{a \in A} \in \prod_{a \in A} \mathcal{P}^*(G_a)$ as a consequence of the equality between (B.191) and (B.192). Thus, for all $\sum_{a \in A} P_A(a)P_{V_a} \in \mathcal{P}^*(\bigsqcup_{a \in A} G_a)$
the following holds:

$$ C (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a}) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) C(G_a, P_{V_a}) \\ \implies C_0 (\bigsqcup_{a \in \mathcal{A}} G_a) = \log (\sum_{a \in \mathcal{A}} 2^{C_0(G_a)}), (P_{V_a})_{a \in \mathcal{A}} \in \prod_{a \in \mathcal{A}} \mathcal{P}^*(G_a), \text{ and } P_A = P_A^*. \quad (B.193) $$

# B.5 Main proofs for the examples and counterexamples

## B.5.1 Proof of Theorem 5.5.8

Lemma B.5.1 comes from [63, Corollary 1], and states that the function $P_A \mapsto H_\kappa (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$, defined analogously to $P_A \mapsto \bar{H} (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$, is always linear. The proof of Lemma B.5.2 is given in Appendix B.6.9.

**Lemma B.5.1 (from [61, Corollary 3.4])** For all probabilistic graphs $(G_a)_{a \in \mathcal{A}}$ and $P_A \in \Delta(\mathcal{A})$, we have $H_\kappa (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) = \sum_{a \in \mathcal{A}} P_A(a) H_\kappa(G_a)$.

**Lemma B.5.2** 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}$.

Now let us prove Theorem 5.5.8.

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 B.5.2, $\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a$ is also perfect; and we have $\bar{H} (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) = H_\kappa (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$ by Theorem 5.5.4. We also have $H_\kappa (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) = \sum_{a \in \mathcal{A}} P_A(a) H_\kappa(G_a) = \sum_{a \in \mathcal{A}} P_A(a) \bar{H}(G_a)$ by Lemma B.5.1 and Theorem 5.5.4 used on the perfect graphs $(G_a)_{a \in \mathcal{A}}$. Thus

$$ \bar{H} (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) = \sum_{a \in \mathcal{A}} P_A(a) \bar{H}(G_a). \qquad (B.194) $$

By Theorem 5.2.4, it follows that $\bar{H} (\bigwedge_{a \in \mathcal{A}} G_a) = \sum_{a \in \mathcal{A}} \bar{H}(G_a) = \sum_{a \in \mathcal{A}} H_\kappa(G_a)$, where the last equality comes from Theorem 5.5.4.
# B.6 Secondary proofs

## B.6.1 Proof of Lemma B.2.2

In order to prove Lemma B.2.2 we need Lemma B.2.1, which can be found in Appendix B.2.1; and Lemma B.6.1, which is a generalization for infinite sequences of the following observation: if $T_{\bar{a}^n} = P_A \in \Delta_n(\mathcal{A})$ satisfies $P_A = \frac{i}{n}P'_A + \frac{n-i}{n}P''_A$ with $P'_A \in \Delta_i(\mathcal{A})$ and $P''_A \in \Delta_{n-i}(\mathcal{A})$, then $\bar{a}^n$ can be separated into two subsequences $a^i$ and $a''^{n-i}$ such that $T_{a^i} = P'_A$ and $T_{a''^{n-i}} = P''_A$. The proof is given in Appendix B.6.10.

**Lemma B.6.1 (Type-splitting lemma)** Let $(\bar{a}_n)_{n \in \mathbb{N}^*} \in \mathcal{A}^{\mathbb{N}^*}$ be a sequence such that $T_{\bar{a}^n} \to P_A \in \Delta(\mathcal{A})$ when $n \to \infty$, let $\beta \in (0, 1)$ and $P'_A, P''_A \in \Delta(\mathcal{A})$ such that

$$P_A = \beta P'_A + (1 - \beta) P''_A. \qquad (B.195)$$

Then there exists a sequence $(b_n)_{n \in \mathbb{N}^*} \in \{0, 1\}^{\mathbb{N}^*}$ such that the two extracted sequences $a' = (\bar{a}_n)_{n \in \mathbb{N}^*, b_n=0}$ and $a'' = (\bar{a}_n)_{n \in \mathbb{N}^*, b_n=1}$ satisfy

$$T_{b^n} \xrightarrow{n \to \infty} (\beta, 1 - \beta), \qquad (B.196)$$

$$T_{a'^n} \xrightarrow{n \to \infty} P'_A, \qquad T_{a''^n} \xrightarrow{n \to \infty} P''_A. \qquad (B.197)$$

Now let us prove Lemma B.2.2. Let $\eta: P_A \mapsto \bar{H}(\cup_{a \in A} P_A G_a)$.

(η Lipschitz) Let us first prove that $\eta$ is Lipschitz. For all $P_A, P'_A \in \Delta(\mathcal{A})$ we need to bound the quantity $|\eta(P_A) - \eta(P'_A)|$; by Lemma B.2.1 this is equivalent to bounding

$$\lim_{n \to \infty} \frac{1}{n} \left| H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n T_{\bar{a}^n}(a)} \right) - H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n T_{\bar{a}'^n}(a)} \right) \right| \qquad (B.198)$$

where $(T_{\bar{a}^n}, T_{\bar{a}'^n}) \to (P_A, P'_A)$ when $n \to \infty$.

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

$$H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n T_{\bar{a}^n}(a)} \right) - H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n T_{\bar{a}'^n}(a)} \right) \qquad (B.199)$$

$$\leq H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n T_{\bar{a}^n}(a)} \right) - H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n \min(T_{\bar{a}^n}(a), T_{\bar{a}'^n}(a))} \right) \qquad (B.200)$$

$$= H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n \min(T_{\bar{a}^n}(a), T_{\bar{a}'^n}(a))} \bigwedge_{a \in A} G_a^{\wedge n |T_{\bar{a}^n}(a) - T_{\bar{a}'^n}(a)|_+} \right)$$

$$- H_{\chi} \left( \bigwedge_{a \in A} G_a^{\wedge n \min(T_{\bar{a}^n}(a), T_{\bar{a}'^n}(a))} \right) \qquad (B.201)$$
$$ \leq H_{\chi} (\bigwedge_{a \in \mathcal{A}} G_a^{\wedge n} |T_{\bar{a}^n}(a) - T_{\bar{a}^{n'}}(a)|_+) \quad (B.202) $$

$$ \leq \log \left( \max_a |\mathcal{V}_a| \right) \sum_{a \in \mathcal{A}} n |T_{\bar{a}^n}(a) - T_{\bar{a}^{n'}}(a)|_+ \quad (B.203) $$

$$ \leq n \log \left( \max_a |\mathcal{V}_a| \right) \|T_{\bar{a}^n} - T_{\bar{a}^{n'}}\|_1, \quad (B.204) $$

where $|\cdot|_+ = \max(\cdot, 0)$ and $\|T_{\bar{a}^n} - T_{\bar{a}^{n'}}\|_1 = \sum_{a \in \mathcal{A}} |T_{\bar{a}^n}(a) - T_{\bar{a}^{n'}}(a)|$; (B.200) follows from the removal of terms in the second product, as $H_{\chi}(G \wedge G') \geq H_{\chi}(G)$ for all probabilistic graphs $G, G'$; (B.201) 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$; (B.202) comes from the subadditivity of $H_{\chi}$; (B.203) follows from $H_{\chi}(G_a) \leq \log \max_{a'} |\mathcal{V}_{a'}|$ for all $a \in \mathcal{A}$; (B.204) results from $|T_{\bar{a}^n}(a) - T_{\bar{a}^{n'}}(a)|_+ \leq |T_{\bar{a}^n}(a) - T_{\bar{a}^{n'}}(a)|$ for all $a \in \mathcal{A}$.

By normalization and limit, it follows that

$$ |\eta(P_A) - \eta(P'_A)| \leq \lim_{n \to \infty} \log \left( \max_a |\mathcal{V}_a| \right) \|T_{\bar{a}^n} - T_{\bar{a}^{n'}}\|_1 \quad (B.205) $$

$$ = \log \left( \max_a |\mathcal{V}_a| \right) \|P_A - P'_A\|_1. \quad (B.206) $$

Hence $\eta$ is $(\log \max_a |\mathcal{V}_a|)$-Lipschitz.

(η convex) Let us now prove that $\eta$ is convex. Let $P'_A, P''_A \in \Delta(\mathcal{A})$, and $\beta \in (0, 1)$, we have by Lemma B.2.1

$$ \eta(\beta P'_A + (1 - \beta) P''_A) = \lim_{n \to \infty} \frac{1}{n} H_{\chi} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge n T_{\bar{a}^n}(a)} \right), \quad (B.207) $$

where $T_{\bar{a}^n} \to \beta P'_A + (1 - \beta) P''_A$ when $n \to \infty$. By Lemma B.6.1, there exists $(b_n)_{n \in \mathbb{N}^*} \in \{0, 1\}^{\mathbb{N}^*}$ such that the decomposition of $(\bar{a}_n)_{n \in \mathbb{N}^*}$ into two subsequences $a' \doteq (\bar{a}_n)_{n \in \mathbb{N}^*}$, and $a'' \doteq (\bar{a}_n)_{n \in \mathbb{N}^*}$, satisfies

$$ T_{b^n} \xrightarrow{n \to \infty} (\beta, 1 - \beta), \quad (B.208) $$

$$ T_{a^{n'}} \xrightarrow{n \to \infty} P'_A, \qquad T_{a^{n'}} \xrightarrow{n \to \infty} P''_A. \quad (B.209) $$

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

$$ \eta(\beta P'_A + (1 - \beta) P''_A) \quad (B.210) $$
$$= \lim_{n \to \infty} \frac{1}{n} H_{\chi} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge \Xi(n) T_{a' \Xi(n)}(a) + (n - \Xi(n)) T_{a'' n - \Xi(n)}(a)} \right) \quad (B.211)$$

$$\le \lim_{n \to \infty} \frac{\Xi(n)}{n} \frac{1}{\Xi(n)} H_{\chi} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge \Xi(n) T_{a' \Xi(n)}(a)} \right) \quad (B.212)$$

$$+ \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''n - \Xi(n)}(a)} \right) \quad (B.213)$$

$$= \beta\eta(P'_A) + (1 - \beta)\eta(P''_A); \quad (B.214)$$

where (B.211) comes from (B.207); (B.213) follows from the subadditivity of $H_\chi$; (B.214) comes from (B.208), (B.209) and Lemma B.2.1. Since (B.214) holds for all $P'_A, P''_A \in \Delta(\mathcal{A})$ and $\beta \in (0, 1)$, we have that $\eta$ is convex.

## B.6.2 Proof of Lemma B.2.3

It can be easily observed that

$$\exists P_A \in \mathrm{int}(\Delta(\mathcal{A})), \gamma(P_A) = \sum_{a \in \mathcal{A}} P_A(a)\gamma(1_a) \quad (B.215)$$

$$\iff \forall P_A \in \Delta(\mathcal{A}), \gamma(P_A) = \sum_{a \in \mathcal{A}} P_A(a)\gamma(1_a). \quad (B.216)$$

Now let us prove (B.215) ⇒ (B.216). Let $P_A^* \in \mathrm{int}(\Delta(\mathcal{A}))$ such that $\gamma(P_A^*) = \sum_{a \in \mathcal{A}} P_A^*(a)\gamma(1_a)$. Let $m: \Delta(\mathcal{A}) \to \mathbb{R}$ linear such that $m(P_A^*) = \gamma(P_A^*)$ and $\forall P_A \in \Delta(\mathcal{A})$, $m(P_A) \le \gamma(P_A)$. We have

$$0 = \gamma(P_A^*) - m(P_A^*) = \sum_{a \in \mathcal{A}} P_A^*(a)(\gamma(1_a) - m(1_a)); \quad (B.217)$$

and therefore $\gamma(1_a) = m(1_a)$ for all $a \in \mathcal{A}$, as $\gamma - m \ge 0$ and $P_A^*(a) > 0$ for all $a \in \mathcal{A}$. For all $P_A \in \Delta(\mathcal{A})$, we have

$$f(P_A) \le \sum_{a \in \mathcal{A}} P_A(a)\gamma(1_a) \quad (B.218)$$

$$= \sum_{a \in \mathcal{A}} P_A(a)m(1_a) = m(P_A), \quad (B.219)$$

hence $\gamma = m$ and $\gamma$ is linear.
### B.6.3 Proof of Lemma B.2.4

The probabilistic graphs in both sides of (B.8) have

$$ (\bigsqcup_{a \in \mathcal{A}} \mathcal{V}_a) \times (\bigsqcup_{b \in \mathcal{B}} \mathcal{V}_b) = \bigsqcup_{(a,b) \in \mathcal{A} \times \mathcal{B}} \mathcal{V}_a \times \mathcal{V}_b \quad (B.220) $$

as set of vertices, with underlying distribution

$$ \begin{aligned} & (\sum_{a \in \mathcal{A}} P_A(a) P_{V_a}) (\sum_{b \in \mathcal{B}} P_B(b) P_{V_b}) \\ & = \sum_{(a,b) \in \mathcal{A} \times \mathcal{B}} P_A(a) P_B(b) P_{V_a} P_{V_b}. \end{aligned} \quad (B.221) $$

Now let us show that these two graphs have the same edges. Let $(v_A, v_B), (v'_A, v'_B) \in (\bigsqcup_{a \in \mathcal{A}} \mathcal{V}_a) \times (\bigsqcup_{b \in \mathcal{B}} \mathcal{V}_b)$; let $a_*, a'_* \in \mathcal{A}$ and $b_*, b'_* \in \mathcal{B}$ be the unique indexes such that

$$ (v_A, v_B) \in \mathcal{V}_{a_*} \times \mathcal{V}_{b_*} \quad \text{and} \quad (v'_A, v'_B) \in \mathcal{V}_{a'_*} \times \mathcal{V}_{b'_*}. \quad (B.222) $$

We have:

$$ (v_A, v_B), (v'_A, v'_B) \text{ are adjacent in } (\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) \wedge (\bigsqcup_{b \in \mathcal{B}}^{P_B} G_b) \quad (B.223) $$

$$ \iff v_A, v'_A \text{ adjacent in } \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \text{ and } v_B, v'_B \text{ adjacent in } \bigsqcup_{b \in \mathcal{B}}^{P_B} G_b \quad (B.224) $$

$$ \iff a_* = a'_* \text{ and } v_A v'_A \in \mathcal{E}_{a_*} \text{ and } b_* = b'_* \text{ and } v_B v'_B \in \mathcal{E}_{b_*} \quad (B.225) $$

$$ \iff (a_*, b_*) = (a'_*, b'_*) \text{ and } (v_A, v_B), (v'_A, v'_B) \text{ are adjacent in } G_{a_*} \wedge G_{b_*} \quad (B.226) $$

$$ \iff (v_A, v_B), (v'_A, v'_B) \text{ are adjacent in } \bigsqcup_{(a,b) \in \mathcal{A} \times \mathcal{B}}^{P_A P_B} G_a \wedge G_b. \quad (B.227) $$

### B.6.4 Proof of Lemma B.2.5

In order to prove Lemma B.2.5, we need Lemma B.6.2. In Lemma B.6.2 we give upper and lower bounds on the chromatic entropy of an induced subgraph $G[S]$, using the chromatic entropy of the whole graph $G$ and the probability $P_V(S)$. The core idea is that if $P_V(S)$ is close to 1 and $H_\chi(G)$ is big, then $H_\chi(G[S])$ is close to $H_\chi(G)$. The proof of Lemma B.6.2 is given in Appendix B.6.11

**Lemma B.6.2** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$ and $S \subseteq \mathcal{V}$, then

$$ H_{\chi}(G) - 1 - (1 - P_V(S)) \log |\mathcal{V}| \le H_{\chi}(G[S]) \le \frac{H_{\chi}(G)}{P_V(S)}. \quad (B.228) $$
**Remark B.6.3** $H_\chi(G[S])$ can be greater than $H_\chi(G)$, even if $G[S]$ has less vertices and inherits the structure of $G$. This stems from the normalized distribution $P_V/P_V(S)$ on the vertices of $G[S]$ which gives more weight to the vertices in $S$. For example, consider

$$G = (N_5, \text{Unif}(\{1, \dots, 5\}))^{(1-\epsilon, \epsilon)} (K_5, \text{Unif}(\{1, \dots, 5\}));$$

where $K_n$ (resp. $N_n$) is the complete (resp. empty) graph with $n$ vertices, i.e. there is an edge (resp. no edge) between any pair of distinct vertices; and with $S$ being the vertices in the connected component $K_5$ in $G$. Then $H_\chi(G) = \epsilon \log 5$ and $H_\chi(G[S]) = \log 5$.

Now let us prove Lemma B.2.5. By Lemma B.6.2, we have for all $n \in \mathbb{N}^*$:

$$ \begin{aligned} H_{\chi}(G^{\wedge n}) - 1 - (1 - P_{V}^{n}(S_{n})) \log |\mathcal{V}| & \\ \leq H_{\chi}(G^{\wedge n}[S^{n}]) & \leq \frac{H_{\chi}(G^{\wedge n})}{P_{V}^{n}(S_{n})}. \end{aligned} \qquad (B.229) $$

Since $P_V^n(S_n) \to 1$, and $H_\chi(G^{\wedge n}) = n\bar{H}(G) + o(n)$ when $n \to \infty$, the desired results follows immediately by normalization and limit.

## B.6.5 Proof of Lemma B.2.7

Let $(\tilde{G}_i)_{i \leq N}$ be isomorphic probabilistic graphs and $G$ such that $G = \bigsqcup_i \tilde{G}_i$. Let $c_1^*$: $\mathcal{V}_1 \to \mathcal{C}$ be the coloring of $\tilde{G}_1$ with minimal entropy, and let $c^*$ be the coloring of $G$ defined by

$$c^* : \mathcal{V} \to \mathcal{C} \qquad (B.230)$$

$$v \mapsto c_1^* \circ \psi_{i_v \to 1}(v), \qquad (B.231)$$

where $i_v$ is the unique integer such that $v \in \mathcal{V}_{i_v}$, and $\psi_{i_v \to 1}: \mathcal{V}_{i_v} \to \mathcal{V}_1$ is an isomorphism between $\tilde{G}_{i_v}$ and $\tilde{G}_1$. In other words $c^*$ applies the same coloring pattern $c_1^*$ on each connected component of $G$. We have

$$H_{\chi}(G) \leq H(c^*(V)) \qquad (B.232)$$

$$= h\left(\sum_{j \leq N} P_{i_v}(j) P_{c^*(V_j)}\right) \qquad (B.233)$$

$$= h\left(\sum_{j \leq N} P_{i_v}(j) P_{c_1^*(V_1)}\right) \qquad (B.234)$$
$$= H(c_1^*(V_1)) \qquad (B.235)$$

$$= H_{\chi}(\tilde{G}_1), \qquad (B.236)$$

where $h$ denotes the entropy of a distribution; (B.234) comes from the definition of $c^*$; and (B.236) comes from the definition of $c_1^*$.

Now let us prove the upper bound on $H_{\chi}(\tilde{G}_1)$. Let $c$ be a coloring of $G$, and let $i^* = \operatorname*{argmin}_i H(c(V_i))$ (i.e. $i^*$ is the index of the connected component for which the entropy of the coloring induced by $c$ is minimal). We have

$$H(c(V)) = h\left(\sum_{j \le N} P_{i_V}(j) P_{c(V_j)}\right) \qquad (B.237)$$

$$\geq \sum_{j \le N} P_{i_V}(j)h(P_{c(V_j)}) \qquad (B.238)$$

$$\geq \sum_{j \le N} P_{i_V}(j)H(c(V_{i^*})) \qquad (B.239)$$

$$\geq H_{\chi}(\tilde{G}_{i^*}), \qquad (B.240)$$

$$= H_{\chi}(\tilde{G}_1), \qquad (B.241)$$

where (B.238) follows from the concavity of $h$; (B.239) follows from the definition of $i^*$; (B.240) comes from the fact that $c$ induces a coloring of $\tilde{G}_{i^*}$; (B.241) comes from the fact that $\tilde{G}_1$ and $\tilde{G}_{i^*}$ are isomorphic. Now, we can combine the bounds (B.236) and (B.241): for all coloring $c$ of $G$ we have

$$H_{\chi}(G) \leq H_{\chi}(\tilde{G}_1) \leq H(c(V)), \qquad (B.242)$$

which yields the desired equality when taking the infimum over $c$.

### B.6.6 Proof of Lemma B.2.8

The probabilistic graph $\bigsqcup_{a \in A}^{P_A} G_a$ has $\sum_{a \in A} P_A(a) P_{V_a}$ as underlying distribution. Let $A, V$ be two random variables such that $A$ is drawn with $P_A$, and $V$ is drawn with $P_{V|A}(\cdot|a) = P_{V_a}$, so that

$$P_V = \sum_{a \in A} P_A(a) P_{V_a}. \qquad (B.243)$$

We have

$$\bar{H}(\bigsqcup_{a \in A}^{P_A} G_a) + C(\bigsqcup_{a \in A}^{P_A} G_a, \sum_{a \in A} P_A(a) P_{V_a}) \qquad (B.244)$$
$$= H(V) \qquad (B.245)$$

$$= H(A, V) \qquad (B.246)$$

$$= H(A) + H(V|A) \qquad (B.247)$$

$$= H(P_A) + \sum_{a \in A} P_A(a)H(P_{V_a}); \qquad (B.248)$$

where (B.245) comes from Theorem 5.1.5 and (B.243); and (B.246) comes from the fact that A can be written as a function of V: by definition, the vertex set of ⋃ P$_{A}$ a ∈ $_{A}$G$_{a}$ writes V = ⋃ a ∈ $_{A}$V$_{a}$ and supp P$_{V}$$_{a}$ ⊆ V$_{a}$, therefore A is the unique index such that V ∈ V$_{A}$.

## B.6.7 Proof of Lemma B.3.1

In this proof, we need Lemma B.6.4 and Lemma B.6.5; their proofs are respectively given in Appendix and Appendix B.6.12 and Appendix B.6.13.

**Lemma B.6.4** For all distributions P$_{V}$, P'$_{V}$ ∈ Δ( V ), for all ϵ ≥ 0, and m, n ∈ $^{N}$⋆,

$$\mathcal{T}_{\epsilon}^{m}(P_{V}) \times \mathcal{T}_{\epsilon}^{n}(P'_{V}) \subseteq \mathcal{T}_{\epsilon}^{m+n} \left( \frac{m}{m+n} P_{V} + \frac{n}{m+n} P'_{V} \right). \qquad (B.249)$$

**Lemma B.6.5** For all graphs G = ( V , E ), G' = ( V' , E' ) and sets S ⊆ V , S ⊆ V' we have

$$(G \wedge G') [S \times S'] \simeq G[S] \wedge G'[S'], \qquad (B.250)$$

where ≃ denotes isomorphic graphs, defined in Definition B.2.6.

Let us prove that for all ϵ > 0 and P$_{V}$ ∈ Δ( V ), the sequence

$$(\log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]))_{n \in \mathbb{N}^{*}} \qquad (B.251)$$

is superadditive. For all integers m, n we have

$$\log \alpha(G^{\wedge n+m}[\mathcal{T}_{\epsilon}^{n+m}(P_V)]) \geq \log \alpha(G^{\wedge m+n}[\mathcal{T}_{\epsilon}^{m}(P_V) \times \mathcal{T}_{\epsilon}^{n}(P_V)]) \qquad (B.252)$$

$$= \log \alpha(G^{\wedge m}[\mathcal{T}_{\epsilon}^{m}(P_V)] \wedge G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]) \qquad (B.253)$$

$$\geq \log \alpha(G^{\wedge m}[\mathcal{T}_{\epsilon}^{m}(P_V)]) + \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]), \qquad (B.254)$$

where (B.252) and (B.253) respectively come from Lemma B.6.4 and Lemma B.6.5.
We can use Fekete's lemma [25]: for all $\epsilon > 0$, the following limit exists

$$ \lim_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]) = \limsup_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]) \quad (B.255) $$

$$ = \sup_{n \in \mathbb{N}^{\star}} \frac{1}{n} \log \alpha(G^{\wedge n}[\mathcal{T}_{\epsilon}^{n}(P_V)]). \quad (B.256) $$

## B.6.8 Proof of Lemma B.4.5

Let us maximize

$$ \zeta: P_A \mapsto H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)w_a. \quad (B.257) $$

It can be easily observed that $\zeta$ is strictly concave, hence the existence and uniqueness of the maximum. We have

$$ \nabla \zeta(P_A) = \left( -\log P_A(a) - \frac{1}{\ln 2} + w_a \right)_{a \in \mathcal{A}}, \quad (B.258) $$

hence

$$ \nabla \zeta(P_A) \perp \Delta(\mathcal{A}) \iff \exists C \in \mathbb{R}, \nabla \zeta(P_A) = (C, \dots, C) \quad (B.259) $$

$$ \iff \exists C' \in \mathbb{R}, (-\log P_A(a) + w_a)_{a \in \mathcal{A}} = (C', \dots, C') \quad (B.260) $$

$$ \iff \exists C' \in \mathbb{R}, P_A = 2^{-C'} (2^{w_a})_{a \in \mathcal{A}} \quad (B.261) $$

The value of $C'$ can be deduced from the fact that $P_A$ is a probability distribution: $2^{C'}$ is the normalization constant $\sum_{a' \in \mathcal{A}} 2^{w_{a'}}$. Hence the maximum of $\zeta$ writes

$$ P_A^* = \left( \frac{2^{w_a}}{\sum_{a' \in \mathcal{A}} 2^{w_{a'}}} \right)_{a \in \mathcal{A}}; \quad (B.262) $$

and we have

$$ \zeta(P_A^*) = \sum_{a \in \mathcal{A}} P_A^*(a) \left( \log \left( \frac{\sum_{a' \in \mathcal{A}} 2^{w_{a'}}}{2^{w_a}} \right) + w_a \right) \quad (B.263) $$

$$ = \log \left( \sum_{a' \in \mathcal{Z}} 2^{w_{a'}} \right). \quad (B.264) $$
## B.6.9 Proof of Lemma B.5.2

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

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

$$ \chi((\bigsqcup_{a \in A}^{P_A} G_a)[S]) = \chi(\bigsqcup_{a \in A}^{P_A} G_a[S_a]) \quad (B.265) $$

$$ = \max_{a \in A} \chi(G_a[S_a]) \quad (B.266) $$

$$ = \max_{a \in A} \omega(G_a[S_a]), \quad (B.267) $$

and similarly, $\omega((\bigsqcup_{a \in A}^{P_A} G_a)[S]) = \max_{a \in A} \omega(G_a[S_a])$. Hence $\bigsqcup_{a \in A}^{P_A} G_a$ is also perfect.

## B.6.10 Proof of Lemma B.6.1

Let $(\bar{a}_n)_{n \in \mathbb{N}^*} \in \mathcal{A}^{\mathbb{N}^*}$ be a sequence such that $T_{\bar{a}^n} \to P_A = \beta P'_A + (1-\beta)P''_A$ when $n \to \infty$.

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

$$ \mathbb{P}(B_n = 0) = \frac{\beta P'_A(\bar{a}_n)}{P_A(\bar{a}_n)}. \quad (B.268) $$

By the strong law of large numbers,

$$ \mathbb{P} \left( T_{B^n, \bar{a}^n} \xrightarrow{n \to \infty} (\beta P'_A, (1-\beta)P''_A) \right) = 1. \quad (B.269) $$

Therefore, there exists at least one realization $(b_n)_{n \in \mathbb{N}^*}$ of $(B_n)_{n \in \mathbb{N}^*}$ such that $T_{b^n, \bar{a}^n}$ converges to $(\beta P'_A, (1-\beta)P''_A)$. The convergences of marginal and conditional types yield

$$ T_{b^n} \xrightarrow{n \to \infty} (\beta, 1-\beta), \quad (B.270) $$

$$ T_{a'^n} \xrightarrow{n \to \infty} P'_A, \quad T_{a''^n} \xrightarrow{n \to \infty} P''_A, \quad (B.271) $$
where $a' = (\bar{a}_n)_{n \in \mathbb{N}^*}$, and $a'' = (\bar{a}_n)_{n \in \mathbb{N}^*}$, are the extracted sequences.

## B.6.11 Proof of Lemma B.6.2

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

(Lower bound) On one hand, we have

$$H_{\chi}(G) \leq H(c(V), \mathbb{1}_{V \in \mathcal{S}}) \qquad (B.272)$$

$$= H(\mathbb{1}_{V \in \mathcal{S}}) + P_V(\mathcal{S})H(c(V)|V \in \mathcal{S}) \\ + (1 - P_V(\mathcal{S}))H(c(V)|V \notin \mathcal{S}) \qquad (B.273)$$

$$\leq 1 + H(c_S^*(V)|V \in \mathcal{S}) + (1 - P_V(\mathcal{S})) \log |\mathcal{V}| \qquad (B.274)$$

$$= H_{\chi}(G[\mathcal{S}]) + 1 + (1 - P_V(\mathcal{S})) \log |\mathcal{V}|; \qquad (B.275)$$

where (B.272) comes from the fact that $c$ is a coloring of $G$; (B.273) is a decomposition using conditional entropies; (B.274) comes from the construction of $c: c|_{\mathcal{S}} = c_S^*$; (B.275) follows from the optimality of $c_S^*$ as a coloring of $G[\mathcal{S}]$.

(Upper bound) On the other hand,

$$H_{\chi}(G[\mathcal{S}]) \\ \leq H(c^*(V)|V \in \mathcal{S}) \qquad (B.276)$$

$$= \frac{1}{P_V(\mathcal{S})} \left( H(c^*(V)|\mathbb{1}_{V \in \mathcal{S}}) - (1 - P_V(\mathcal{S}))H(c^*(V)|V \notin \mathcal{S}) \right) \qquad (B.277)$$

$$\leq \frac{H(c^*(V))}{P_V(\mathcal{S})} = \frac{H_{\chi}(G)}{P_V(\mathcal{S})} \qquad (B.278)$$

where (B.276) comes from the fact that $c^*$ induces a coloring of $G[\mathcal{S}]$; (B.277) is a decomposition using conditional entropies; (B.278) results from the elimination of negative terms and the optimality of $c^*$.
## B.6.12 Proof of Lemma B.6.4

Let $(v^m, v^n) \in \mathcal{T}_\epsilon^m(P_V) \times \mathcal{T}_\epsilon^n(P'_V)$. We have

$$ \left\| T_{v^{m+n}} - \left( \frac{m}{n+m} P_V + \frac{n}{n+m} P'_V \right) \right\|_{\infty} \qquad (B.279) $$

$$ = \left\| \frac{m}{n+m} T_{v^m} + \frac{n}{n+m} T_{v^n} - \frac{m}{n+m} P_V - \frac{n}{n+m} P'_V \right\|_{\infty} \qquad (B.280) $$

$$ \leq \frac{m}{n+m} \|T_{v^m} - P_V\|_{\infty} + \frac{n}{n+m} \|T_{v^n} - P'_V\|_{\infty} \qquad (B.281) $$

$$ \leq \frac{m}{n+m}\epsilon + \frac{n}{n+m}\epsilon = \epsilon, \qquad (B.282) $$

hence the desired result.

## B.6.13 Proof of Lemma B.6.5

The graphs $G[S] \wedge G'[S']$ and $(G \wedge G')[S \times S']$ both have $S \times S'$ as set of vertices. For all $(v_1, v'_1), (v_2, v'_2) \in S \times S'$, we have:

$$ (v_1, v'_1), (v_2, v'_2) \text{ are adjacent in } G[S] \wedge G'[S'] \qquad (B.283) $$

$$ \iff v_1, v_2 \text{ are adjacent in } G \text{ and } v'_1, v'_2 \text{ are adjacent in } G' \qquad (B.284) $$

$$ \iff (v_1, v'_1), (v_2, v'_2) \text{ are adjacent in } (G \wedge G')[S \times S'] \qquad (B.285) $$
<figure><img src="image_28.png" /></figure>
# PROOFS FOR CODING FOR COMPUTING
ZERO-ERROR RESULTS

## C.1 Proof of Theorem 6.3.2

Consider the particular case $f(X, Y) = X$ of Figure 6.2. The optimal rate in this particular case equals the optimal rate $R^*$ in the following auxiliary problem, depicted in Figure C.1: $(X, g(Y))$ as source available at the encoder and to be retrieved by the decoder which knows $Y$ (thus expecting it to retrieve $g(Y)$ in addition to $X$ does not change the optimal rate).

<figure><img src="image_29.png" /><figcaption>Figure C.1 – An auxiliary zero-error Slepian-Wolf problem.</figcaption></figure>

This auxiliary problem is a particular instance of the zero-error Slepian-Wolf problem; its optimal rate writes $\overline{H}(G)$, where $G$ is the characteristic graph defined in Definition 3.2.4 for the pair $((X, g(Y)), Y)$. The graph $G$ has $\mathcal{X} \times \mathcal{Z}$ as set of vertices, and $(x, z)$ is adjacent to $(x', z')$ if there exists a side information symbol $y \in \mathcal{Y}$ such that $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z') > 0$. It can be observed that the vertices $(x, z)$ and $(x', z')$ such that $z \neq z'$ are not adjacent in $G$. The graph $G$ is therefore a disjoint union indexed by $\mathcal{Z}$:

$$G = \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z; \qquad (C.1)$$

$$R^* = \overline{H}(G) = \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right); \qquad (C.2)$$

where for all $z \in \mathcal{Z}$, $G_z$ is the characteristic graph defined in Definition 3.2.4 for the pair $(X'_z, Y'_z) \sim P_{X,Y|g(Y)=z}$.
(⇒) Assume that $g$ and $P_{X,Y}$ satisfy the “pairwise shared side information” condition. It directly follows that $P_{X|g(Y)=z}$ is full-support for all $z \in \mathcal{Z}$. Let $z \in \mathcal{Z}$, and let $(x, z), (x', z)$ be any two vertices of $G_z$. By construction, there exists $y \in g^{-1}(z)$ such that $P_{X,Y}(x, y)P_{X,Y}(x', y) > 0$; hence $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z) > 0$, and $(x, z), (x', z)$ are adjacent in $G_z$. Each graph $G_z$ is therefore complete, and perfect; the graph $G = \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z$ is a disjoint union of perfect graphs and is also perfect by Lemma B.5.2. We have:

$$R^* = \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) \qquad (C.3)$$

$$= H_{\kappa} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) \qquad (C.4)$$

$$= \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z) \qquad (C.5)$$

$$= \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H(P_{X|g(Y)=z}) \qquad (C.6)$$

$$= H(X|g(Y)); \qquad (C.7)$$

where (C.3) comes from (C.2); (C.4) and (C.5) follow from Theorem 5.5.8 used on the perfect graph $\bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z$; and (C.6) holds as the independent subsets of the complete graph $G_z$ are singletons containing one of its vertices.

( ⇐ ) Conversely, assume that $P_{X|g(Y)=z}$ is full-support for all $z \in \mathcal{Z}$, and $R^* = H(X|g(Y))$.

Assume, *ad absurdum*, that at least one of the $(G_z)_{z \in \mathcal{Z}}$ is not complete; then there exists a coloring of that graph that maps two different vertices to the same color. Thus, there exists $z \in \mathcal{Z}$ such that

$$\overline{H}(G_z) < H(P_{X|g(Y)=z}), \qquad (C.8)$$

as $P_{X|g(Y)=z}$ is full-support. We have

$$H(X|g(Y)) = R^* \qquad (C.9)$$

$$= \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) \qquad (C.10)$$

$$\leq \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) \overline{H}(G_z) \qquad (C.11)$$

$$< H(X|g(Y)); \qquad (C.12)$$
where (C.10) comes from (C.2), (C.11) results from [71, Theorem 2], and (C.12) follows from (C.8). We arrive at a contradiction, hence all the graphs $(G_z)_{z \in \mathcal{Z}}$ are complete: for all $z \in \mathcal{Z}$ and $x, x' \in \mathcal{X}$, there exists a side information symbol $y \in \mathcal{Y}$ such that $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z) > 0$; hence $y \in g^{-1}(z)$, and satisfies $P_{X,Y}(x, y)P_{X,Y}(x', y) > 0$. The condition “pairwise shared side information” is satisfied by $P_{X,Y}, g$.

## C.2 Proof of Theorem 6.3.6

Let us specify the adjacency condition in $G_{[n]}$ under the assumption (6.14). Two vertices are adjacent if they satisfy (6.9) and (6.10); however (6.9) is always satisfied under (6.14). Thus $(x^n, z^n)(x'^n, z'^n)$ are adjacent if $z^n = z'^n$ and

$$ \exists y^n \in g^{-1}(z^n), \exists t \le n, f(x_t, y_t) \ne f(x'_t, y_t). \quad (C.13) $$

It can be observed that the condition (C.13) is the adjacency condition of an OR product of adequate graphs; more precisely,

$$ G_{[n]} = \bigsqcup_{z^n \in \mathcal{Z}^n} \bigvee_{t \le n} G_{zt}^f. \quad (C.14) $$

Although $G_{[n]}$ cannot be expressed as an $n$-th OR power, we will show that its chromatic entropy asymptotically coincide with that of an appropriate OR power: we now search for an asymptotic equivalent of $H_\chi(G_{[n]})$.

**Definition C.2.1** $S_n$ is the set of colorings of $G_{[n]}$ that can be written as $(x^n, z^n) \mapsto (T_{z^n}, \tilde{c}(x^n, z^n))$ for some mapping $\tilde{c}: \mathcal{X}^n \times \mathcal{Z}^n \to \tilde{\mathcal{C}}$; where $T_{z^n}$ denotes the type of $z^n$.

In the following, we define $Z^n \doteq (g(Y_t))_{t \le n}$. Now we need several Lemmas. Lemma C.2.2 states that the optimal coloring $c(x^n, z^n)$ of $G_{[n]}$ has the type of $z^n$ as a prefix at a negligible rate cost. Lemma C.2.3 gives an asymptotic formula for the minimal entropy of the colorings from $S_n$.

**Lemma C.2.2** The following asymptotic comparison holds:

$$ H_{\chi}(G_{[n]}) = \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) + O(\log n). \quad (C.15) $$
**Lemma C.2.3** The following asymptotic comparison holds:

$$ \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) = n \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f) + o(n). \quad (C.16) $$

The proof of Lemma C.2.2 is given in Appendix C.3, its keypoint is the asymptotically negligible entropy of the prefix $T_{Z^n}$ of the colorings of $S_n$.

The proof of Lemma C.2.3 is given in Appendix C.4, and relies on the decomposition $G_{[n]} = \bigsqcup_{Q_n \in \Delta_n(\mathcal{Z})} G_{[n]}^{Q_n}$, where $G_{[n]}^{Q_n}$ is the subgraph induced by the vertices $(x^n, z^n)$ such that the type of $z^n$ is $Q_n$. We show that $G_{[n]}^{Q_n}$ is a disjoint union of isomorphic graphs whose chromatic entropy is given by Lemma B.2.7 and (6.16): $|H_{\chi}(G_{[n]}^{Q_n}) - n \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f)| \le n\epsilon_n$. Finally, uniform convergence arguments enable us to conclude.

Now let us combine these results together:

$$ R^* = \frac{1}{n} H_{\chi}(G_{[n]}) + o(1) \quad (C.17) $$

$$ = \frac{1}{n} \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) + o(1) \quad (C.18) $$

$$ = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f) + o(1), \quad (C.19) $$

where (C.17) comes from Theorem 6.2.2, (C.18) comes from Lemma C.2.2, and (C.19) comes from Lemma C.2.3. The proof of Theorem 6.3.6 is complete.

## C.3 Proof of Lemma C.2.2

Let $c_n^*$ be the coloring of $G_{[n]}$ with minimal entropy. Then we have:

$$ H_{\chi}(G_{[n]}) = \inf_{c \text{ coloring of } G_{[n]}} H(c(X^n, Z^n)) \quad (C.20) $$

$$ \le \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) \quad (C.21) $$

$$ = \inf_{\substack{c:(x^n,z^n) \\ \mapsto (T_{z^n}, \tilde{c}(x^n,z^n))}} H(T_{Z^n}, \tilde{c}(X^n, Z^n)) \quad (C.22) $$

$$ \le H(T_{Z^n}) + H(c_n^*(X^n, Z^n)) \quad (C.23) $$

$$ = H_{\chi}(G_{[n]}) + O(\log n), \quad (C.24) $$
where (C.22) comes from Definition C.2.1; (C.23) comes from the subadditivity of the entropy, and the fact that $(x^n, z^n) \mapsto (T_{z^n}, c_n^*(x^n, z^n))$ is a coloring of $G_{[n]}$ that belongs to $S_n$; and (C.24) comes from $H(T_{Z^n}) = O(\log n)$, as $\log|\Delta_n(\mathcal{Z})| = O(\log n)$. The desired equality comes from the bounds $H_\chi(G_{[n]})$ and $H_\chi(G_{[n]}) + O(\log n)$ on (C.21).

## C.4 Proof of Lemma C.2.3

For all $Q_n \in \Delta_n(\mathcal{Z})$, let

$$G_{[n]}^{Q_n} = \bigcup_{\substack{z^n \in \mathcal{Z}^n \\ T_{z^n} = Q_n}} \bigvee_{t \le n} G_{z_t}^f, \qquad (C.25)$$

with the probability distribution induced by $P_{X,Z}^n$. This graph is formed of the connected components of $G_{[n]}$ whose corresponding $z^n$ has type $Q_n$. We need to find an equivalent for $H_\chi(G_{[n]}^{Q_n})$. Since $G_{[n]}^{Q_n}$ is a disjoint union of isomorphic graphs, we can use Lemma B.2.7:

$$H_{\chi}(G_{[n]}^{Q_n}) = H_{\chi}\left(\bigvee_{z \in \mathcal{Z}} (G_z^f)^{\vee n Q_n(z)}\right). \qquad (C.26)$$

On one hand,

$$H_{\chi}\left(\bigvee_{z \in \mathcal{Z}} (G_z^f)^{\vee n Q_n(z)}\right) \geq H_{\kappa}\left(\bigvee_{z \in \mathcal{Z}} (G_z^f)^{\vee n Q_n(z)}\right) \qquad (C.27)$$

$$= n \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f), \qquad (C.28)$$

where (C.27) comes from $H_\kappa \le H_\chi$ [5, Lemma 14], (C.28) comes from (6.16). On the other hand,

$$H_{\chi}\left(\bigvee_{z \in \mathcal{Z}} (G_z^f)^{\vee n Q_n(z)}\right) \le \sum_{z \in \mathcal{Z}} Q_n(z) H_{\chi}((G_z^f)^{\vee n}) \qquad (C.29)$$

$$= n \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f) + n \epsilon_n, \qquad (C.30)$$

where $\epsilon_n \doteq \max_z \frac{1}{n} H_\chi((G_z^f)^{\vee n}) - H_\kappa(G_z^f)$ is a quantity that does not depend on $Q_n$ and satisfies $\lim_{n \to \infty} \epsilon_n = 0$; (C.29) comes from the subadditivity of $H_\chi$. Combining equations
(C.26), (C.28) and (C.30) yields

$$ \left| H_{\chi}(G_{[n]}^{Q_n}) - n \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f) \right| \le n \epsilon_n. \qquad (C.31) $$

Now, we have an equivalent for $H_{\chi}(G_{[n]}^{Q_n})$.

$$ \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in \mathcal{S}_n}} H(c(X^n, Z^n)) \qquad (C.32) $$

$$ = \inf_{\substack{c:(x^n,z^n) \\ \mapsto (T_{Z^n}, \tilde{c}(x^n,z^n))}} H(\tilde{c}(X^n, Z^n)|T_{Z^n}) + H(T_{Z^n}) \qquad (C.33) $$

$$ = \inf_{\substack{c:(x^n,z^n) \\ \mapsto (T_{Z^n}, \tilde{c}(x^n,z^n))}} \sum_{Q_n \in \Delta_n(\mathcal{Z})} P_{T_{Z^n}}(Q_n) H(\tilde{c}(X^n, Z^n)|T_{Z^n} = Q_n) + O(\log n) \qquad (C.34) $$

$$ = \sum_{Q_n \in \Delta_n(\mathcal{Z})} P_{T_{Z^n}}(Q_n) \inf_{c_{Q_n} \text{ coloring of } G_{[n]}^{Q_n}} H(c_{Q_n}(X^n, Z^n)|T_{Z^n} = Q_n) + O(\log n) \qquad (C.35) $$

$$ = \sum_{Q_n \in \Delta_n(\mathcal{Z})} P_{T_{Z^n}}(Q_n) H_{\chi}(G_{[n]}^{Q_n}) + O(\log n) \qquad (C.36) $$

$$ = \sum_{Q_n \in \Delta_n(\mathcal{Z})} P_{T_{Z^n}}(Q_n) \left( n \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f) \pm n \epsilon_n \right) + O(\log n) \qquad (C.37) $$

$$ = n \sum_{Q_n \in \Delta_n(\mathcal{Z})} 2^{-nD(Q_n \| P_{g(Y)}) + o(n)} \left( \sum_{z \in \mathcal{Z}} Q_n(z) H_{\kappa}(G_z^f) \right) \pm n \epsilon_n + O(\log n) \qquad (C.38) $$

$$ = n \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f) + o(n), \qquad (C.39) $$

where (C.34) comes from $H(T_{Z^n}) = O(\log n)$, as $\log|\Delta_n(\mathcal{Z})| = O(\log n)$; (C.35) follows from the fact that the entropy of $\tilde{c}$ can be minimized independently on each $G_{[n]}^{Q_n}$; (C.36) follows from the definition of $G_{[n]}^{Q_n}$; (C.37) comes from (C.31); (C.38) comes from [20, Lemma 2.6] and the fact that $\epsilon_n$ does not depend on $Q_n$.
BIBLIOGRAPHY

[1] Rudolf Ahlswede, Ning Cai, and Zhen Zhang, « Zero-error capacity for models with memory and the enlightened dictator channel », in: *IEEE Transactions on Information Theory* 44.3 (1998), pp. 1250–1252.

[2] Emrah Akyol et al., « On scalable coding in the presence of decoder side information », in: *2014 IEEE International Symposium on Information Theory (ISIT)*.

[3] Noga Alon, « On the capacity of digraphs », in: *European Journal of Combinatorics* 19.1 (1998), pp. 1–5.

[4] Noga Alon, « The Shannon capacity of a union », in: *Combinatorica* 18.3 (1998), pp. 301–310.

[5] Noga Alon and Alon Orlitsky, « Source coding and graph entropies », in: *IEEE Transactions on Information Theory* 42.5 (1996), pp. 1329–1339.

[6] Sourya Basu, Daewon Seo, and Lav R Varshney, « Hypergraph-based Coding Schemes for Two Source Coding Problems under Maximal Distortion », in: *IEEE International Symposium on Information Theory (ISIT)*, 2020.

[7] Meryem Benammar and Abdellatif Zaidi, « Rate-Distortion Region of a Gray–Wyner Model with Side Information », in: *Entropy* 20.1 (2018), p. 2.

[8] Navid Mahmoudian Bidgoli, Thomas Maugey, and Aline Roumy, « Fine granularity access in interactive compression of 360-degree images based on rate-adaptive channel codes », in: *IEEE Transactions on Multimedia* 23 (2020), pp. 2868–2882.

[9] Holger Boche and Christian Deppe, « Computability of the zero-error capacity of noisy channels », in: *2021 IEEE Information Theory Workshop (ITW)*, IEEE, 2021, pp. 1–6.

[10] Boris Bukh and Christopher Cox, « On a fractional version of Haemers’ bound », in: *IEEE Transactions on Information Theory* 65.6 (2018), pp. 3340–3348.

[11] Peter J Cameron, « 6-transitive graphs », in: *Journal of Combinatorial Theory, Series B* 28.2 (1980), pp. 168–179.
[12] Qi Cao et al., « On zero-error capacity of binary channels with one memory », in: *IEEE Transactions on Information Theory* 64.10 (2018), pp. 6771–6778.

[13] Jun Chen, Da-Ke He, and Ashish Jagmohan, « The equivalence between Slepian-Wolf coding and channel coding under density evolution », in: *IEEE Transactions on Communications* 57.9 (2009), pp. 2534–2540.

[14] Jun Chen et al., « On the linear codebook-level duality between Slepian-Wolf coding and channel coding », in: *IEEE Transactions on Information Theory* 55.12 (2009), pp. 5575–5590.

[15] Maria Chudnovsky and Paul D Seymour, « The structure of claw-free graphs. », in: *BCC*, 2005, pp. 153–171.

[16] Maria Chudnovsky et al., « The strong perfect graph theorem », in: *Annals of mathematics* (2006), pp. 51–229.

[17] Gérard Cohen, Emanuela Fachini, and János Körner, « Zero-error capacity of binary channels with memory », in: *arXiv preprint arXiv:1402.0349* (2014).

[18] Thomas M Cover, *Elements of information theory*, John Wiley & Sons, 1999.

[19] Imre Csiszar, « Linear codes for sources and source networks: Error exponents, universal coding », in: *IEEE Transactions on Information Theory* 28.4 (1982), pp. 585–592.

[20] Imre Csiszár and János Körner, *Information theory: coding theorems for discrete memoryless systems*, Cambridge University Press, 2011.

[21] Imre Csiszár and János Körner, « On the capacity of the arbitrarily varying channel for maximum probability of error », in: *Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete* 57.1 (1981), pp. 87–101.

[22] Imre Csiszár et al., « Entropy splitting for antiblocking corners and perfect graphs », in: *Combinatorica* 10.1 (1990), pp. 27–40.

[23] Lingyu Duan et al., « Video coding for machines: A paradigm of collaborative compression and intelligent analytics », in: *IEEE Transactions on Image Processing* 29 (2020), pp. 8680–8695.

[24] Soheil Feizi and Muriel Médard, « On network functional compression », in: *IEEE transactions on information theory* 60.9 (2014), pp. 5387–5401.
[25] Michael Fekete, «Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten», in: *Mathematische Zeitschrift* 17.1 (1923), pp. 228–249.

[26] Li Gao, Sander Gribling, and Yinan Li, «On a tracial version of Haemers bound», in: *IEEE Transactions on Information Theory* (2022).

[27] Wen Gao et al., «Recent standard development activities on video coding for machines», in: *arXiv preprint arXiv:2105.12653* (2021).

[28] L Gargano, J Körner, and U Vaccaro, «Sperner theorems on directed graphs and qualitative independence», in: *J. Combin. Theory Ser. A* 61 (1992), pp. 173–192.

[29] Luisa Gargano, János Körner, and Ugo Vaccaro, «Capacities: from information theory to extremal set theory», in: *Journal of Combinatorial Theory, Series A* 68.2 (1994), pp. 296–316.

[30] RM Gray and AD Wyner, «Source coding for a simple network», in: *Bell System Technical Journal* 53.9 (1974), pp. 1681–1721.

[31] Yujie Gu and Ofer Shayevitz, «On the non-adaptive zero-error capacity of the discrete memoryless two-way channel», in: *Entropy* 23.11 (2021), p. 1518.

[32] Xuan Guang et al., «Improved upper bound on the network function computing capacity», in: *IEEE Transactions on Information Theory* 65.6 (2019), pp. 3790–3811.

[33] Willem Haemers et al., «On some problems of Lovász concerning the Shannon capacity of a graph», in: *IEEE Transactions on Information Theory* 25.2 (1979), pp. 231–232.

[34] David A Huffman, «A method for the construction of minimum-redundancy codes», in: *Proceedings of the IRE* 40.9 (1952), pp. 1098–1101.

[35] Amiram H. Kaspi, «Rate-distortion function when side-information may be present at the decoder», in: *IEEE Transactions on Information Theory* 40.6 (1994), pp. 2031–2034.

[36] Peter Keevash and Eoin Long, «On the normalized Shannon capacity of a union», in: *Combinatorics, Probability and Computing* 25.5 (2016), pp. 766–767.

[37] J Korner and Giuseppe Longo, «Two-step encoding for finite sources», in: *IEEE Transactions on Information Theory* 19.6 (1973), pp. 778–782.
[38] Janos Korner and Alon Orlitsky, « Zero-error information theory », in: *IEEE Transactions on Information Theory* 44.6 (1998), pp. 2207–2229.

[39] János Körner, « Coding of an information source having ambiguous alphabet and the entropy of graphs », in: *6th Prague conference on information theory*, 1973, pp. 411–425.

[40] János Körner, Concetta Pilotto, and Gábor Simonyi, « Local chromatic number and Sperner capacity », in: *Journal of Combinatorial Theory, Series B* 95.1 (2005), pp. 101–117.

[41] Prashant Koulgi et al., « On zero-error source coding with decoder side information », in: *IEEE Transactions on Information Theory* 49.1 (2003), pp. 99–111.

[42] Dinesh Krithivasan and S Sandeep Pradhan, « Distributed source coding using abelian group codes: A new achievable rate-distortion region », in: *IEEE Transactions on Information Theory* 57.3 (2011).

[43] Thomas Laich and Michèle Wigger, « Utility of encoder side information for the lossless kaspi/heegard-b erger problem », in: *2013 IEEE International Symposium on Information Theory*, IEEE, 2013, pp. 3065–3069.

[44] László Lovász, « On the Shannon capacity of a graph », in: *IEEE Transactions on Information theory* 25.1 (1979), pp. 1–7.

[45] Rick Ma and Samuel Cheng, « Zero-error Slepian–Wolf coding of confined-correlated sources with deviation symmetry », in: *IEEE Transactions on Information Theory* 59.12 (2013), pp. 8195–8209.

[46] Derya Malak and Muriel Médard, « Hyper Binning for Distributed Function Coding », in: *2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)*, IEEE, 2020, pp. 1–5.

[47] Katalin Marton, « On the Shannon capacity of probabilistic graphs », in: *Journal of Combinatorial Theory, Series B* 57.2 (1993), pp. 183–195.

[48] K Ashik Mathew and Patric RJ Östergård, « New lower bounds for the Shannon capacity of odd cycles », in: *Designs, Codes and Cryptography* 84 (2017), pp. 13–22.

[49] Thomas Maugey et al., « Incremental coding for extractable compression in the context of massive random access », in: *IEEE transactions on Signal and Information Processing over Networks* 6 (2020), pp. 251–260.
[50] Alon Orlitsky and James R Roche, « Coding for computing », in: *Proceedings of IEEE 36th Annual Foundations of Computer Science*, IEEE, 1995, pp. 502–511.

[51] Sven C Polak and Alexander Schrijver, « New lower bound on the Shannon capacity of C7 from circular graphs », in: *Information Processing Letters* 143 (2019), pp. 37–40.

[52] Jithin Ravi and Bikash Kumar Dey, « Function Computation Through a Bidirectional Relay », in: *IEEE Transactions on Information Theory* 65.2 (2018), pp. 902–916.

[53] Aline Roumy and Thomas Maugey, « Universal lossless coding with random user access: the cost of interactivity », in: *2015 IEEE International Conference on Image Processing (ICIP)*, IEEE, 2015, pp. 1870–1874.

[54] Igal Sason, « Observations on the Lovász $\theta$-Function, Graph Capacity, Eigenvalues, and Strong Products », in: *Entropy* 25.1 (2023), p. 104.

[55] Alexander Schrijver, « On the Shannon capacity of sums and products of graphs », in: *Indagationes Mathematicae* 34.1 (2023), pp. 37–41.

[56] Milad Sefidgaran and Aslan Tchamkerten, « Distributed function computation over a rooted directed tree », in: *IEEE Transactions on Information Theory* 62.12 (2016), pp. 7135–7152.

[57] Andrea Sgarro, « Source coding with side information at several decoders », in: *IEEE Transactions on Information Theory* 23.2 (1977), pp. 179–182.

[58] Claude Shannon, « The zero error capacity of a noisy channel », in: *IRE Transactions on Information Theory* 2.3 (1956), pp. 8–19.

[59] Claude Elwood Shannon, « A mathematical theory of communication », in: *The Bell system technical journal* 27.3 (1948), pp. 379–423.

[60] Ofer Shayevitz, « Distributed computing and the graph entropy region », in: *IEEE transactions on information theory* 60.6 (2014), pp. 3435–3449.

[61] Gábor Simonyi, « Graph entropy: a survey », in: *Combinatorial Optimization* 20 (1995), pp. 399–441.

[62] Gábor Simonyi, « On Witsenhausen's zero-error rate for multiple sources », in: *IEEE Transactions on Information Theory* 49.12 (2003), pp. 3258–3260.
[63] Gábor Simonyi, « Perfect graphs and graph entropy. An updated survey », in: *Perfect graphs* (2001), pp. 293–328.

[64] David Slepian and Jack Wolf, « Noiseless coding of correlated information sources », in: *IEEE Transactions on information Theory* 19.4 (1973), pp. 471–480.

[65] Yossef Steinberg and Neri Merhav, « On successive refinement for the Wyner–Ziv problem », in: *IEEE Transactions on Information Theory* 50.8 (2004), pp. 1636–1654.

[66] Chao Tian and Suhas N Diggavi, « Side-information scalable source coding », in: *IEEE Transactions on Information Theory* 54.12 (2008), pp. 5591–5608.

[67] Roy Timo, Terence Chan, and Alex Grant, « Rate distortion with side-information at many decoders », in: *IEEE Transactions on Information Theory* 57.8 (2011), pp. 5240–5257.

[68] Roy Timo et al., « Source coding for a simple network with receiver side information », in: *2008 IEEE International Symposium on Information Theory*, IEEE, 2008, pp. 2307–2311.

[69] Hugo Touchette, « Legendre-Fenchel transforms in a nutshell », in: URL http://www.maths.qmul.ac.uk/~ht/archive/lfth2.pdf (2005).

[70] Ertem Tuncel and Kenneth Rose, « On variable-length coding of sources with side information at multiple decoders », in: *IEEE International Symposium on Information Theory, 2003. Proceedings*. IEEE, 2003, p. 140.

[71] Ertem Tuncel et al., « On complementary graph entropy », in: *IEEE transactions on information theory* 55.6 (2009), pp. 2537–2546.

[72] Aleksander Vesel and Janez Žerovnik, « Improved lower bound on the Shannon capacity of C7 », in: *Information processing letters* 81.5 (2002), pp. 277–282.

[73] Lele Wang and Young-Han Kim, « Linear code duality between channel coding and Slepian-Wolf coding », in: *2015 53rd IEEE Annual Allerton Conference on Communication, Control, and Computing (Allerton)*.

[74] Moritz Wiese et al., « Secure estimation and zero-error secrecy capacity », in: *IEEE Transactions on Automatic Control* 64.3 (2018), pp. 1047–1062.
[75] Hans Witsenhausen, « The zero-error side information problem and chromatic numbers (corresp.) », in: *IEEE Transactions on Information Theory* 22.5 (1976), pp. 592–593.

[76] Hirosuke Yamamoto, « Wyner-ziv theory for a general function of the correlated sources (corresp.) », in: *IEEE Transactions on Information Theory* 28.5 (1982), pp. 803–807.

[77] Guofen Zhang et al., « The zero-error capacity of binary channels with 2-memories », in: *Advances in Mathematics of Communications* (2022).

[78] Jeroen Zuiddam et al., *Algebraic complexity, asymptotic spectra and entanglement polytopes*, Institute for Logic, Language and Computation, 2018.
<figure><img src="image_30.png" /></figure>
<figure><img src="image_31.png" /></figure>
**Titre :** Théorie de l'information zéro-erreur dans les réseaux : graphes, codage pour le calcul de fonctions et dualité source-canal

**Mot clés :** Théorie de l'information zéro-erreur, codage de source, dualité source-canal

**Résumé :** Cette thèse de doctorat porte sur la théorie de l'information zéro-erreur, notamment sur le codage de source avec information adjacente, le codage de canal et la dualité source-canal. Ces travaux s'articulent autour de trois axes : 1. les problèmes de codage zéro-erreur basés sur la correction, 2. les problèmes de codage zéro-erreur basés sur les graphes de confusion, 3. les problèmes de codage zéro-erreur pour le calcul d'une fonction. Une contribution importante de ce travail concerne le problème de la linéarisation

du débit optimal, lorsque l'encodeur traite plusieurs tâches conjointement. Nous démontrons l'équivalence de la linéarisation pour les produits de graphes et pour leurs unions disjointes. Cette observation permet de caractériser les débits optimaux pour une classe de problèmes irrésolus depuis les années 1950. Les contributions de cette thèse ont donné lieu à des publications dans les actes des meilleurs conférences internationales de théorie de l'information et deux articles de revues sont en cours de préparation.

**Title:** Zero-error network information theory: graphs, coding for computing and source-channel duality

**Keywords:** Zero-error Information Theory, Source coding, Source-channel duality

**Abstract:** This doctoral thesis focuses on zero-error information theory, particularly on source coding with side information, channel coding and source-channel duality. These works revolve around three axes: 1. zero-error coding problems based on correction, 2. zero-error coding problems based on confusion graphs, 3. zero-error coding problems for calculating a function. An important contribution of this work concerns the problem of linearizing the optimal bitrate, when the encoder

cesses several tasks jointly. We demonstrate the equivalence of linearization for graph products and for their disjoint unions. This observation makes it possible to characterize the optimal rates for a class of unsolved problems since the 1950s. The contributions of this thesis have given rise to publications in the proceedings of the best international Information Theory conferences and two journal articles are in preparation.