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

Nicolas Charpenay, Maël Le Treust, Aline Roumy

► To cite this version:

Nicolas Charpenay, Maël Le Treust, Aline Roumy. Complementary Graph Entropy, AND Product, and Disjoint Union of Graphs. ISIT 2023 - International Symposium on Information Theory, Jun 2023, Taipei (Taiwan), Taiwan. pp.1-6. hal-04133013

HAL Id: hal-04133013

https://hal.science/hal-04133013

Submitted on 19 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complementary Graph Entropy, AND Product, and Disjoint Union of Graphs

Nicolas Charpenay

Maël le Treust

Aline Roumy

Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)

Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)

Institut National de Recherche

Rennes, FRANCE

Rennes, FRANCE

Rennes, FRANCE

nicolas.charpenay@irisa.fr

mael.le-treust@irisa.fr

aline.roumy@inria.fr

**Abstract**—In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\bar{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 $\bar{H}(\wedge \cdot)$ and $\bar{H}(\sqcup \cdot)$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\bar{H}(\wedge \cdot)$ and $\bar{H}(\sqcup \cdot)$ can be linearized coincide. Second, we determine $\bar{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 $\bar{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 $\hat{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].

### A. Characteristic graphs and optimal rate $\bar{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'$ are adjacent if they are “confusable”, i.e. $P_{X,Y}(x,y)P_{X,Y}(x',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

$$H_X(G) = \inf\{H(c(V)) \mid c \text{ is a coloring of } G\}. \quad (1)$$

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

$$\bar{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_X(G^{\wedge n}), \quad (2)$$

$$X^n \to \boxed{\text{Encoder}} \xrightarrow{R} \boxed{\text{Decoder}} \xrightarrow{\substack{\uparrow \\ Y^n}} \hat{X}^n = X^n$$

<caption>Fig. 1. Zero-error Slepian-Wolf source coding problem.</caption>

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 $\bar{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.

### B. Characteristic graph structure in particular instances

Since determining $\bar{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 \mathbb{Z}}$; and in Figure 2.b the characteristic graph is the AND product ($\wedge$) of the $(G_z)_{z \in \mathbb{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 $\bar{H}(G_z)$ for all $z \in \mathbb{Z}$? With the subadditivity results in [6, Theorem 2], we know that $\bar{H}(\bigcup_{z \in \mathbb{Z}}^{P_{g(Y)}} G_z) \le \sum_{z \in \mathbb{Z}} P_{g(Y)} \bar{H}(G_z)$ and $\bar{H}(\bigwedge_{z \in \mathbb{Z}} G_z) \le \sum_{z \in \mathbb{Z}} \bar{H}(G_z)$ holds in general, however characterizing the cases where equality holds is an open problem.

### 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.
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Two particular instances of zero-error Slepian-Wolf source coding problem, where $g: \mathcal{Y} \to \mathcal{Z}$ is deterministic, $(X_z^n, Y_z^n) \sim P_{X,Y|g(Y)=z}^n$ for all $z \in \mathcal{Z}$, and the pairs $((X_z^n, Y_z^n))_{z \in \mathcal{Z}}$ are mutually independent. For all $z \in \mathcal{Z}$, the auxiliary graph $\tilde{G}_z$ is Witsenhausen's characteristic graph for the pair $(X'_z, Y'_z)$.</figcaption></figure>

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 $\bar{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'$ do we have $\Theta(G \wedge G') = \Theta(G)\Theta(G')$? 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') = \Theta(G)\Theta(G')$ is equivalent to $\Theta(G \sqcup G') = \Theta(G) + \Theta(G')$. 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.

## 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. $\bar{H}(\sqcup \cdot)$ and $\bar{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 $\bar{H}(\sqcup \cdot)$ and $\bar{H}(\wedge \cdot)$ up to a multiplicative constant. This formula has several consequences.

Firstly, we can derive with it a single-letter formula $\bar{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 $\bar{H}(\sqcup \cdot)$ and $\bar{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

$$ 
\begin{aligned}
G_1 &= \begin{smallmatrix} 1/4 \\ 1/2 \\ 1/4 \end{smallmatrix} & G_2 &= \begin{smallmatrix} 1/3 \\ 2/3 \end{smallmatrix} \\
G_1 \wedge G_2 &= \begin{smallmatrix} 1/12 \\ 1/6 \\ 1/12 \end{smallmatrix} & G_1 \sqcup G_2 &= \begin{smallmatrix} 1/16 \\ 1/8 \\ 1/16 \end{smallmatrix} \\
& \begin{smallmatrix} 1/6 \\ 1/3 \\ 1/6 \end{smallmatrix} & & \begin{smallmatrix} 1/4 \\ 1/2 \end{smallmatrix}
\end{aligned}
$$

<caption>Fig. 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})$.</caption>

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 $S \subseteq \mathcal{V}$ is independent in $G$ if for all $x, x' \in S$, $xx' \notin \mathcal{E}$. A mapping $c: \mathcal{V} \to \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'_1, (v'_1 v'_2))$ are adjacent if $v_1 v'_1 \in \mathcal{E}_1$ AND $v_2 v'_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 \dots \wedge G_1$.

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

Let $A$ be a finite set, and let $P_A \in \Delta(A)$. For all $a \in 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 $\sqcup_{a \in A} G_a$ and defined by:

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

- For all $v, v' \in \mathcal{V}$, $vv' \in \mathcal{E}$ iff they both belong to the same $\mathcal{V}_a$ and $vv' \in \mathcal{E}_a$;

- $P_V = \sum_{a \in A} P_A(a) P_{V_a}$; note that the $(P_{V_a})_{a \in 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 = \text{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}^*$ then

$$ \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) = \frac{1}{k} \overline{H}\left(\bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)}\right). \quad (3) $$

**Corollary III.3** $\overline{H}(\bigcup_{a \in \mathcal{A}}^{\text{Unif}(\mathcal{A})} G_a) = \frac{1}{|\mathcal{A}|} \overline{H}(\bigwedge_{a \in \mathcal{A}} G_a)$.

#### 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 $(\bar{a}_n)_{n \in \mathbb{N}^*} \in \mathcal{A}^{\mathbb{N}^*}$ be any sequence such that $T_{\bar{a}^n} \to P_A$ when $n \to \infty$. Then we have

$$ \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) = \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 (4) $$

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

$$ \begin{aligned} \overline{H}(\bigcup_{a \in \mathcal{A}}^{P_A} G_a) &= \lim_{n \to \infty} \frac{1}{kn} H_{\chi}(\bigwedge_{a \in \mathcal{A}} G_a^{\wedge kn T_{\bar{a}^k}(a)}) \\ &= \lim_{n \to \infty} \frac{1}{kn} H_{\chi}((\bigwedge_{a \in \mathcal{A}} G_a^{\wedge k T_{\bar{a}^k}(a)})^{\wedge n}) \\ &= \frac{1}{k} \overline{H}(\bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)}). \quad \square \end{aligned} $$

### IV. CONSEQUENCES

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

With the exceptions of $G_5 = (C_5, \text{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.

**Definition IV.1 (Induced subgraph)** The subgraph induced in a graph $G$ by a subset of vertices $S$ is the graph obtained from $G$ by keeping only the vertices in $S$ and the edges between them, and is denoted by $G[S]$. When $G$ is a probabilistic graph, we give it the underlying probability distribution $P_V/P_V(S)$.

**Definition IV.2 (Perfect graph)** A graph $G = (\mathcal{V}, \mathcal{E})$ is perfect if $\forall S \subset \mathcal{V}$, $\chi(G[S]) = \omega(G[S])$; where $\omega$ is the size of the largest clique (i.e. complete induced subgraph); and $\chi(G[S])$ is the smallest $|C|$ such that there exists a coloring $c: S \to C$ of $G[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

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

where the minimum is taken over all distributions $P_{W|V} \in \Delta(W)^\mathcal{V}$, with $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:

$$ \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), \quad (6) $$

<figure><img src="image_4.png" /><figcaption>Fig. 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).</figcaption></figure>
VI. PROOF OF LEMMA 1

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.

**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

$$ \left( \bigcup_{a \in \mathcal{A}}^{P_A} G_a \right) \wedge \left( \bigcup_{b \in \mathcal{B}}^{P_B} G_b \right) = \bigcup_{(a,b) \in \mathcal{A} \times \mathcal{B}} G_a \wedge G_b. \quad (18) $$

**Lemma 3** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$, and $(S^n)_{n \in \mathbb{N}^*}$ be a sequence of sets such that for all $n \in \mathbb{N}^*$, $S^n \subset \mathcal{V}^n$, and $P_V^n(S^n) \to 1$ when $n \to \infty$. Then $\overline{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_X(G^{\wedge n}[S^n])$.

**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 \to \mathcal{V}_2$ such that:

- For all $v_1, v'_1 \in \mathcal{V}_1$, $v_1v'_1 \in \mathcal{E}_1 \iff \psi(v_1)\psi(v'_1) \in \mathcal{E}_2$,

- For all $v_1 \in \mathcal{V}_1$, $P_{V_1}(v_1) = P_{V_2}(\psi(v_1))$.

**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_X(\bigcup_{b' \in \mathcal{B}}^{P_B} G_{b'}) = H_X(G_b)$ for all $b \in \mathcal{B}$.

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 = \bigcup_{a \in \mathcal{A}}^{P_A} G_a$. Let $P_A \in \Delta(\mathcal{A})$, and 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$ when $n \to \infty$. Let $\epsilon > 0$, and for all $n \in \mathbb{N}^*$ let

$$ \begin{align} \mathcal{T}_{\epsilon}^{n}(P_A) &\doteq \{a^n \in \mathcal{A}^n \mid \|T_{a^n} - P_A\|_{\infty} \le \epsilon\}, \tag{19} \\ P'^n &\doteq \frac{P_A^n}{P_A^n(\mathcal{T}_{\epsilon}^n(P_A))}, \quad \mathcal{S}_{\epsilon}^n \doteq \bigcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)} \prod_{t \le n} \mathcal{V}_{a_t}. \nonumber \end{align} $$

By Lemma 3 we have

$$ \overline{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_X \left( G^{\wedge n} [S_{\epsilon}^n] \right), \quad (20) $$

as $P_V^n(S_\epsilon^n) \to 1$ when $n \to \infty$. Let us study the limit in (20). For all $n$ large enough, $\bar{a}^n \in \mathcal{T}_\epsilon^n(P_A)$ as $T_{\bar{a}^n} \to P_A$. Therefore, for all $a^n \in \mathcal{T}_\epsilon^n(P_A)$ and $a' \in \mathcal{A}$,

$$ |T_{\bar{a}^n}(a') - T_{a^n}(a')| \le 2\epsilon. \quad (21) $$

We have on one hand

$$ \begin{align} & H_X\left(\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right)^{\wedge n} [S_\epsilon^n]\right) \nonumber \\ &= H_X\left(\left(\bigcup_{a^n \in \mathcal{A}^n}^{P_A} \bigwedge_{t \le n} G_{a_t}\right) [S_\epsilon^n]\right) \tag{22} \\ &= H_X\left(\bigcup_{a^n \in \mathcal{T}_\epsilon^n(P_A)}^{P'^n} \bigwedge_{t \le n} G_{a_t}\right) \tag{23} \end{align} $$

$$ \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) = \sum_{a \in \mathcal{A}} P_A(a) H_\kappa(G_a). \quad (7) $$

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)$,

$$ \overline{H}(G_1 \sqcup G_2) \le \alpha \overline{H}(G_1) + (1 - \alpha) \overline{H}(G_2), \quad (8) $$

$$ \overline{H}(G_1 \wedge G_2) \le \overline{H}(G_1) + \overline{H}(G_2). \quad (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:

$$ \overline{H}(G_1 \stackrel{(\alpha, 1-\alpha)}{\sqcup} G_2) = \alpha \overline{H}(G_1) + (1-\alpha) \overline{H}(G_2) \quad (10) $$

$$ \iff \overline{H}(G_1 \wedge G_2) = \overline{H}(G_1) + \overline{H}(G_2). \quad (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

$$ \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 (12) $$

$$ \iff \overline{H}\left(\bigwedge_{a \in \mathcal{A}} G_a\right) = \sum_{a \in \mathcal{A}} \overline{H}(G_a). \quad (13) $$

A case where equality holds in (12) is developed by Tuncel et al. in [6, Lemma 3]: $G_5 \doteq (C_5, \text{Unif}(\{1, \dots, 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).

Corollary IV.9 For all perfect probabilistic graph G,

$$ \overline{H}(G \wedge G_5) = \overline{H}(G) + \overline{H}(G_5) = H_\kappa(G) + \frac{1}{2} \log 5. \quad (14) $$

V. EXAMPLE

In this section, for all $i \in \mathbb{N}^*$, $G_i$ denotes the cycle graph with $i$ vertices uniform distribution, i.e. $G_i = (C_i, \text{Unif}(\{0, \dots, i-1\}))$. 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:

$$ \begin{align} H_\kappa(G_6) &= H(V_6) - \max_{V_6 \in W_6 \in \Gamma(G_6)} H(V_6|W_6) \tag{15} \\ &= 1 + \log 3 - \log 3 = 1 \tag{16} \end{align} $$

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)$:

$$ \overline{H}(G_6 \wedge G_8) = H_\kappa(G_6) + H_\kappa(G_8) = 2. \quad (17) $$

We can build an optimal coloring of $G_6 \wedge G_8$, $c^* : (v_6, v_8) \mapsto (\mathbb{1}_{v_6 \text{ is even}}, \mathbb{1}_{v_8 \text{ is even}})$.
$$= H_{\chi}(\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} \Lambda_{a' \in A} G_{a'}^{\wedge n T_{a^n}(a')}) \quad (24)$$

$$\le H_{\chi}(\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} \Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a') + [2n\epsilon]}) \quad (25)$$

$$= H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a') + [2n\epsilon]}) \quad (26)$$

$$\le H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} + H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge [2n\epsilon]})) \quad (27)$$

$$\le H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} + [2n\epsilon] |A| \log |V|; \quad (28)$$

where (22) comes from Lemma 2; (23) comes from the definition of $S_{\epsilon}^n$ and $P^n$ in (19); (24) is a rearrangement of the terms inside the product; (25) comes from (21); (26) follows from Lemma 4, the graphs $(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} + [2n\epsilon])_{a^n \in \mathcal{T}_{\epsilon}^n(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

$$H_{\chi}((\bigsqcup_{a \in A}^{P_A} G_a)^{\wedge n} [S_{\epsilon}^n]) \\ \ge H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} - [2n\epsilon]) \quad (29)$$

$$\ge H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} - H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge [2n\epsilon]})), \quad (30)$$

$$\ge H_{\chi}(\Lambda_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} - [2n\epsilon] |A| \log |V|; \quad (31)$$

Note that (30) also comes from the subadditivity of $H_{\chi}$: $H_{\chi}(G_2) \ge H_{\chi}(G_1 \wedge G_2) - H_{\chi}(G_1)$ for all $G_1, G_2$.

By combining (28) and (31) we obtain

$$\left| \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\wedge n}[S_{\epsilon}^n]) - \lim_{n \to \infty} \frac{1}{n} H_{\chi} \left( \bigwedge_{a' \in A} G_{a'}^{\wedge n T_{\bar{a}^n}(a')} \right) \right| \le 2\epsilon |A| \log |V|. \quad (32)$$

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

## VII. PROOF OF THEOREM IV.8

### A. Preliminary results

In Lemma 5 we give regularity properties of $P_A \mapsto \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a)$. Lemma 6 states that if a convex function $\gamma$ of $\Delta(\mathcal{A})$ meets the linear interpolation of the $(\gamma(\mathbb{1}_a))_{a \in 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 \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a)$.

**Lemma 5** The function $P_A \mapsto \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a)$ is convex and $(\log \max_a |V_a|)$-Lipschitz.

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

$$\exists P_A \in \text{int}(\Delta(\mathcal{A})), \gamma(P_A) = \sum_{a \in A} P_A(a) \gamma(\mathbb{1}_a) \quad (33)$$

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

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

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

$$(\implies) \text{ Assume that } \bar{H}(\Lambda_{a \in A} G_a) = \sum_{a \in A} \bar{H}(G_a).$$

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

$$\forall P_A \in \Delta(\mathcal{A}), \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a) = \sum_{a \in A} P_A(a) \bar{H}(G_a). \quad (35)$$

$$(\iff) \text{ Conversely, assume (35), then } P_A \mapsto \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a) \text{ is linear. We can use Corollary III.3, and we have } \bar{H}(\Lambda_{a \in A} G_a) = |A| \bar{H}(\bigsqcup_{a \in A}^{\text{Unif}(\mathcal{A})} G_a) = \sum_{a \in A} \bar{H}(G_a).$$

## VIII. PROOF OF THEOREM IV.6

### A. Preliminary results

Lemma 7 comes from [23, Corollary 3.4], and states that the function $P_A \mapsto H_{\kappa}(\bigsqcup_{a \in A}^{P_A} G_a)$, defined analogously to $P_A \mapsto \bar{H}(\bigsqcup_{a \in A}^{P_A} G_a)$, is always linear.

**Lemma 7** For all probabilistic graphs $(G_a)_{a \in A}$ and $P_A \in \Delta(\mathcal{A})$, we have $H_{\kappa}(\bigsqcup_{a \in A}^{P_A} G_a) = \sum_{a \in A} P_A(a) H_{\kappa}(G_a)$.

**Lemma 8** The probabilistic graph $\bigsqcup_{a \in A}^{P_A} G_a$ is perfect if and only if $G_a$ is perfect for all $a \in A$.

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

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

Therefore (12) is satisfied by the graphs $(G_a)_{a \in A}$ and $P_A$: by Theorem IV.8, it follows that $\bar{H}(\Lambda_{a \in A} G_a) = \sum_{a \in A} \bar{H}(G_a) = \sum_{a \in A} H_{\kappa}(G_a)$, where the last equality comes from Theorem IV.5.

## IX. CONCLUSION

Theorem III.2 shows that $\bar{H}(\bigsqcup_{a \in A}^{P_A} G_a) = \frac{1}{k} \bar{H}(\Lambda_{a \in A} G_a^{\wedge k P_A(a)})$ 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 $\bar{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 $\bar{H}(\bigsqcup_{z \in \mathcal{Z}}^{P_{g(\mathcal{Y})}} G_z)$ and $\bar{H}(\Lambda_{z \in \mathcal{Z}} G_z)$.
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. I. 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.