Exercises

$d_1 = 1$, $\mathcal{S}_2 = \{1\}$ so $d_1 \in \mathcal{S}_2$ — non-edge. Similarly for $(2, 1)$. Graph has no edges. $\chi(G) = 1$, $\beta(G) = 1$. One XOR message suffices.

Each color class in a proper coloring is an independent set of the conflict graph — meaning the corresponding receivers are pairwise compatible for XOR delivery. Hence $\chi(G)$ coded messages suffice. But non-linear codes (e.g., using algebraic structure beyond XOR) can combine information more efficiently in certain graphs, beating the chromatic bound. Known examples: Kneser-graph instances with $\beta = O(1)$ and $\chi = \Omega(\log n)$.

For $k = 1$: $\mathcal{T} \in \{\{2\}, \{3\}\}$ → vertices $(1, \{2\})$, $(1, \{3\})$. Similarly for $k = 2, 3$. Total: 6 vertices.

$(t+1) = 2$-subsets: $\{1,2\}, \{1,3\}, \{2,3\}$. Each corresponds to one color class. $\{1,2\}$: $\{(1, \{2\}), (2, \{1\})\}$, size 2. $\{1,3\}$: $\{(1, \{3\}), (3, \{1\})\}$, size 2. $\{2,3\}$: $\{(2, \{3\}), (3, \{2\})\}$, size 2.

$\alpha(G) = 2$, $\chi(G) = 3$. Rate: $3 \cdot 1/\binom{3}{1} = 1$ file, matching the MAN formula $R = (3-1)/2 = 1$. ✓

$K_3$ (complete graph on 3 vertices) has $\chi = 3$ and $\alpha = 1$. Corresponds to 3 receivers with no useful side information about each other's demands: three distinct files, three distinct demands, empty side information. Index coding rate: $\beta = 3$ (pure unicast).

No coding helps when side information is empty — every file must be transmitted once.

$\alpha(G) \leq \beta(G) \leq \lambda(G) \leq \chi_f(G) \leq \chi(G)$. Linear codes are a restriction, so $\beta \leq \lambda$. XOR coloring realizes $\chi$ colors, so $\lambda \leq \chi$. LP relaxation gives $\chi_f \leq \chi$. For MAN graphs, all values between $\alpha$ and $\chi_f$ collapse to a single number.

$|V| = 5 \cdot \binom{4}{2} = 30$. Each 3-subset of $[5]$ gives one color class of size 3. $\binom{5}{3} = 10$ color classes.

10 messages of size $1/\binom{5}{2} = 1/10$ each. Total: 10 · 1/10 = 1 file. MAN formula: $R = (K-t)/(t+1) = 3/3 = 1$. ✓

$R_{\text{cont}} = 10 \cdot 0.85/2.5 = 3.4$.

$R(t=1) = 9/2 = 4.5$, $R(t=2) = 8/3 \approx 2.667$. Average: 3.58.

Memory-shared rate exceeds continuous by about 5%. The gap is the rounding error from integer-$t$ constraint. In practice, $K \to \infty$ closes this gap.

$P_4 = v_1 - v_2 - v_3 - v_4$. $\chi(P_4) = 2$.

Ordering $v_1, v_3, v_2, v_4$: $c(v_1) = 0$, $c(v_3) = 0$ (no neighbors colored), $c(v_2) = 1$ (neighbors $v_1, v_3$ use 0), $c(v_4) = 1$ (neighbor $v_3$ uses 0). Uses 2 colors. ✓

Ordering $v_1, v_2, v_3, v_4$: $c(v_1) = 0$, $c(v_2) = 1$, $c(v_3) = 0$, $c(v_4) = 1$. Uses 2 colors. Also optimal.

Pathological ordering for general graphs: consider a graph where an adversarial ordering can force greedy to use many more colors than $\chi$. See Welsh-Powell analysis.

The Welsh-Powell heuristic (vertices by decreasing degree) is often close to optimal. For MAN graphs, the natural "lex-subset" ordering is always optimal — an artifact of the transitivity.

Lubetzky-Stav construct an index coding instance on $n$ receivers with $\beta = O(1)$ non-linear rate and $\lambda = \Omega(\log n)$ linear rate. The instance is based on the Kneser graph $K(m, r)$ where non-linear (algebraic) codes exploit the intersection structure of $r$-subsets.

This shows that restricting to XOR-based delivery (the natural choice for MAN-style schemes) is not sufficient to achieve the optimal index coding rate in general. For the structured MAN family, fortunately, linear suffices.

$\beta(G) \geq \alpha(G)$. The clique number of the complement graph $\bar{G}$ equals $\alpha(G)$: a clique in $\bar{G}$ is an independent set in $G$.

Let $I$ be a max independent set. Any two receivers in $I$ have mutually compatible demands (non-edge in $G$). But each receiver still needs $F$ fresh bits. A lower bound is hence $|I| F = \alpha F$ bits transmitted.

$\alpha(G_{\text{MAN}}) = t + 1$, giving a per-color-class lower bound of $t+1$ bits. Multiplied by the $\binom{K}{t+1}/(t+1)$ color classes... this actually is the MAN rate. Full equality: $\beta = \chi = \alpha \cdot \chi_f/\alpha$. Chapter 4 formalism closes.

A receiver with $\mathcal{S}_k = \emptyset$ cannot XOR-decode; it must receive $W_{d_k}$ in full (via a separate transmission slot). Total broadcast rate: $1 + \beta(\mathcal{I}')$ where $\mathcal{I}'$ is the reduced instance with this receiver (and maybe $W_{d_k}$) removed.

In MAN, every user has $\binom{K-1}{t-1}$ subfiles of its demand — non-empty side information. The reduction does not apply, which is consistent with the compact rate formula.

We showed in §4.4 that $G_{\text{MAN}}$ is vertex-transitive. For vertex-transitive graphs, the LP relaxation optimum equals $|V|/\alpha$ (a classical result).

$|V| = K \binom{K-1}{t}$, $\alpha = t+1$. $\chi_f = |V|/\alpha = K\binom{K-1}{t}/(t+1) = \binom{K}{t+1}$. ✓

Since $\chi_f$ equals the integer $\chi$, the LP relaxation is tight. The MAN coloring (one color per $(t+1)$-subset) realizes the optimum.

$\mathrm{H}(W_{d_1} | \mathcal{S}_1) = F - F \rho = F(1-\rho)$, where $\rho$ is the mutual information normalized by file size. Similarly for $W_{d_2}$.

The server must send enough to decrease $\mathrm{H}(W_{d_1}, W_{d_2} | X, \mathcal{S}_1, \mathcal{S}_2) = 0$. Rate lower bound: $R \geq F(1-\rho)$ per receiver, totalling via joint encoding potentially $F(1-\rho)$ combined. An XOR over partial-information bits suffices.

Correlated side information reduces the effective index coding rate by a factor $(1-\rho)$. This is the precursor to the correlated-files coded caching of Chapter 3's CommIT result.

If receiver $k$ demands $m_k$ distinct messages, the effective contribution to the lower bound is $m_k F$ bits per round.

In coded caching, a user sometimes requests several files per delivery round (e.g., in bundled streaming). The MAN rate generalizes: $R = m \cdot K(1-\mu)/(1+K\mu)$ where $m$ is the per-user demand multiplicity. Each additional demand adds independently to the rate.

Exact characterization of multi-demand coded caching is an open problem for certain parameter regimes. See Wan-Caire-Molisch 2017 for partial results.

$\alpha(C_3) = 1$, $\chi(C_3) = 3$. $\beta(C_3) = 3$ (LP is tight for this graph: each message needs its own slot).

$\alpha(C_5) = 2$, $\chi_f(C_5) = 5/2$, $\chi(C_5) = 3$. The linear broadcast rate is $\lambda(C_5) = 5/2$ (achieved by fractional coloring + time sharing). Non-linear rate: $\beta(C_5) = 5/2$ as well (tight LP).

Bipartite: $\alpha = \max(2, 3) = 3$, $\chi = 2$. $\beta = 2$.

Even for small graphs, computing the exact broadcast rate is non-trivial, especially in the non-linear regime. For MAN-type instances the LP bound is always tight, which is the structural gift.