Ferkans — Interactive Telecom Tutor

Why a Graph?

The key to making index coding tractable is to reframe it as a graph problem. Two receivers are "compatible" — can be served by a single transmission — when their demands are covered by each other's side information in a sense we will make precise. Non-compatibility is an edge; compatibility is an anti-edge. The resulting graph encodes the combinatorial structure of the instance.

Colorings, cliques, and independent sets of this graph directly give us upper and lower bounds on the broadcast rate. For the MAN family, the bounds coincide and yield the rate formula of Chapter 2.

Definition:
The Conflict Graph of an Index Coding Instance

Given an index coding instance $\mathcal{I}$ with single-demand receivers, the conflict graph $G(\mathcal{I}) = (V, E)$ is defined by:

$V = \{1, 2, \ldots, K\}$ — one vertex per receiver.
$\{i, j\} \in E$ (an edge) iff $d_i \notin \mathcal{S}_j$ and $d_j \notin \mathcal{S}_i$ . That is, receivers $i$ and $j$ conflict when neither has the other's desired message as side information.

Equivalently, $\{i, j\}$ is a non-edge (anti-edge) iff $d_i \in \mathcal{S}_j$ or $d_j \in \mathcal{S}_i$ — at least one of them already knows the other's demand.

Some references use the side-information graph (directed) instead: directed edge $i \to j$ iff $d_j \in \mathcal{S}_i$ . The undirected conflict graph here is the "symmetric complement" and is what governs the clique-cover upper bound.

Theorem: Chromatic Number Upper-Bounds Index Coding Rate

For any single-demand index coding instance with conflict graph $G$ , the optimal broadcast rate is upper-bounded by the fractional chromatic number: $\beta(G) \;\leq\; \chi_f(G) \;\leq\; \chi(G).$

Partition the receivers into independent sets (color classes) of $G$ . Each color class is a group of receivers whose demands are pairwise satisfiable by a single XOR-coded transmission — because within an independent set, every pair of receivers has the desired message of the other in its side information.

Proof

Color the graph

Let $c: V \to \{1, \ldots, \chi(G)\}$ be a proper coloring. For each color $k$ , let $V_k = c^{-1}(k)$ — an independent set in $G$ .

One XOR per color class

Within $V_k$ , every pair $i, j \in V_k$ has $d_i \in \mathcal{S}_j$ or $d_j \in \mathcal{S}_i$ (non-adjacent in $G$ ). The server transmits $X_k = \bigoplus_{i \in V_k} W_{d_i}$ . Each receiver $i \in V_k$ recovers $W_{d_i}$ by XORing out the other summands (all in its side information — this requires a small additional argument handled by the MAN structure; see Lemma 4.1 of Bar-Yossef et al.).

Count transmissions

Total rate: $\chi(G)$ file units. Fractional chromatic number $\chi_f(G) \leq \chi(G)$ is achievable by time-sharing fractional colorings. $\blacksquare$

Tightness question

The bound $\beta(G) \leq \chi_f(G)$ is not always tight. For general graphs, $\beta(G) < \chi_f(G)$ is possible (gaps have been constructed). For MAN conflict graphs, however, $\beta = \chi_f$ (§4.4).

Conflict Graph of a MAN Instance

Visualize the MAN conflict graph for small $K$ and $t$ . Each node is a (user, missing-subfile) pair; edges connect node pairs that cannot share a single delivery message. The number of independent sets needed to cover the graph equals the index-coding rate.

Parameters

Number of users K4

Gain parameter t2

Definition:
Broadcast Rate and Minrank

The broadcast rate $\beta(\mathcal{I})$ of an index coding instance is the optimal rate over all (possibly non-linear) codes. The linear broadcast rate $\lambda(\mathcal{I})$ restricts to linear codes over a fixed finite field. A foundational result (Bar-Yossef et al. 2011) shows $\lambda(\mathcal{I}) \;=\; \text{minrk}_{\mathbb{F}}(G(\mathcal{I})),$ where minrk is the minimum rank of a matrix $M$ with $M_{ii} = 1$ and $M_{ij} = 0$ whenever $\{i, j\} \notin E(G)$ , free otherwise.

In general, $\beta \leq \lambda$ , and the gap can be nonzero — there are index coding instances where non-linear codes strictly outperform linear codes.

Theorem: Independence Number Lower-Bounds Index Coding Rate

For any single-demand index coding instance with conflict graph $G$ , $\beta(G) \;\geq\; \alpha(G),$ where $\alpha(G)$ is the independence number of $G$ .

Let $I$ be a maximum independent set of $G$ . Any two receivers in $I$ are non-conflicting — their demands can in principle share transmissions. But crucially, the information delivered to each receiver in $I$ still has entropy $F$ , so the broadcast must contain at least $|I| \cdot F$ distinct bits worth of information from the server's side. Rate $\geq |I| = \alpha(G)$ .

Proof

Choose an independent set

Let $I = \{i_1, \ldots, i_\alpha\}$ be a maximum independent set. By definition of conflict graph, for each pair $i_a, i_b \in I$ , $d_{i_a} \in \mathcal{S}_{i_b}$ or $d_{i_b} \in \mathcal{S}_{i_a}$ .

Information bottleneck

Consider a genie receiver that combines the side information of all receivers in $I$ except receiver $i_a$ . The genie wants to recover $W_{d_{i_a}}$ . By receiver $i_a$ 's decoder, this requires receiving at least $F$ bits worth of information about $W_{d_{i_a}}$ .

Union bound

Summing over the $\alpha$ receivers in $I$ : the broadcast contains at least $\alpha F$ bits of distinct demanded-message entropy. Hence rate $\geq \alpha(G)$ . $\blacksquare$

Key Takeaway

The broadcast rate is sandwiched between $\alpha(G)$ and $\chi_f(G)$ : $\alpha(G) \leq \beta(G) \leq \chi_f(G) \leq \chi(G).$ For MAN conflict graphs, the sandwich closes: $\alpha = \beta = \chi_f = (K-t)/(t+1)$ . For general index coding, both the upper and lower bounds can be loose, and the gap is what makes the problem NP-hard.

Example: An Index Coding Instance with $\chi > \beta$

Consider 4 receivers with the following side information: $\mathcal{S}_1 = \{2, 4\}$ , $\mathcal{S}_2 = \{1, 3\}$ , $\mathcal{S}_3 = \{2, 4\}$ , $\mathcal{S}_4 = \{1, 3\}$ . Each wants file $W_{d_k}$ with $d_k = k$ . Compute the conflict graph, its chromatic number, and the optimal broadcast rate.

Solution

Conflict graph edges

Check each pair: $\{1,2\}$ : $d_1 = 1 \in \mathcal{S}_2$ , so non-edge. $\{1,3\}$ : $d_1 = 1 \notin \mathcal{S}_3 = \{2,4\}$ ; $d_3 = 3 \notin \mathcal{S}_1 = \{2,4\}$ . Edge. $\{1,4\}$ : $d_1 = 1 \in \mathcal{S}_4$ , non-edge. $\{2,3\}$ : $d_2 = 2 \in \mathcal{S}_3$ , non-edge. $\{2,4\}$ : $d_2 = 2 \notin \mathcal{S}_4 = \{1,3\}$ ; $d_4 = 4 \notin \mathcal{S}_2 = \{1,3\}$ . Edge. $\{3,4\}$ : $d_3 = 3 \in \mathcal{S}_4$ , non-edge.

Conflict graph: two edges $\{1,3\}$ and $\{2,4\}$ , forming two disjoint pairs.

Chromatic number

Two disjoint edges $\Rightarrow$ graph is bipartite. $\chi(G) = 2$ .

Optimal broadcast

With $\chi(G) = 2$ , transmit two XORs: $X_1 = W_1 \oplus W_3$ and $X_2 = W_2 \oplus W_4$ . Each receiver recovers its demand using its side information. Rate: $\beta = 2$ .

Comparison with uncoded

Uncoded: $R = 4$ . Coded: $\beta = 2$ . Gain: factor 2. This instance exemplifies why coding beats unicasting even for simple graphs.

Common Mistake: The Chromatic Number Is Not Always Tight

Mistake:

Assuming the index coding rate always equals the chromatic number.

Correction:

$\chi(G)$ is an upper bound on $\beta(G)$ ; it is not always tight. Lubetzky and Stav (2009) constructed index coding instances with $\beta = O(1)$ but $\chi = \Omega(\log n)$ . The gap is due to non-linear codes outperforming any linear (XOR-based) scheme.

For MAN conflict graphs, linear XOR codes are optimal and the chromatic / fractional chromatic / independence numbers coincide — hence the clean rate formula of Chapter 2.

Graph-Theoretic Formulations