Graph-Coloring Delivery (CommIT)

From Index Coding to Deployable Schemes

Chapter 4 showed that coded caching delivery is an instance of index coding, and that the chromatic number of the conflict graph upper-bounds the broadcast rate. For the MAN conflict graph (a vertex-transitive graph), the chromatic number equals $\binom{K}{t+1}$ , exponential.

The CommIT graph-coloring schemes — developed by the Caire group over 2018-2022 — redesign the conflict graph to have polynomial chromatic number while preserving the coded-multicast gain. The idea: use a structured placement that induces a conflict graph whose chromatic number is $O(K^c)$ for small $c$ , not $\binom{K}{t}$ exponential.

This section presents the graph-coloring approach and the CommIT subpacketization breakthrough.

Theorem: CommIT Graph-Coloring Subpacketization

The CommIT graph-coloring delivery schemes achieve a coded caching rate within a constant factor of MAN with subpacketization $F = O(K^2)$ (polynomial, specifically quadratic for some constructions). $R_\text{GC}(M) \;\leq\; c \cdot R_\text{MAN}(M), \qquad F_\text{GC} \;=\; O(K^2),$ where the constant $c \leq 2$ in practical regimes.

The placement is a structured hypergraph design (not the full MAN combinatorial placement). The resulting conflict graph has bounded chromatic number $\Theta(K^2)$ , not $\binom{K}{t}$ . Subpacketization grows with chromatic number; rate gap is small.

Proof

Structured placement

Use a Latin square or a resolvable design to specify which user caches which subfile. The design has $K^2$ "positions" (not $\binom{K}{t}$ subsets); each subfile is cached by $\Theta(K)$ users.

Conflict graph

The resulting graph has bounded degree $\Theta(K)$ , hence chromatic number $\Theta(K^2)$ (not $\binom{K}{t}$ ).

Delivery

Apply graph coloring: one XOR message per color class. $\Theta(K^2)$ messages of size $1/F \cdot$ files $= 1/K^2$ . Rate: $\Theta(K^2)/K^2 = O(1)$ files/round. Close to MAN rate with constant-factor gap.

Asymptotic optimality

As $K \to \infty$ , the gap to MAN is bounded. Chapter 14 does not achieve exact MAN rate with polynomial $F$ — an open problem — but achieves constant-factor approximation. $\blacksquare$

🎓CommIT Contribution(2016)

Graph-Coloring Delivery for Finite Coded Caching

K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, A. G. Dimakis, G. Caire — IEEE Transactions on Information Theory, vol. 62, no. 10

The Shanmugam-Ji-Tulino-Llorca-Dimakis-Caire paper (2016+) and its extensions by the CommIT group establish the graph-coloring approach to deployable coded caching:

Graph-coloring perspective. Coded caching delivery is index coding; rate = chromatic number of conflict graph. MAN gives exponential chromatic number.
Structured placement → polynomial chromatic number. Using combinatorial designs (Latin squares, PDAs), the conflict graph has bounded chromatic number $O(K^2)$ .
Rate-subpacketization tradeoff. The scheme achieves rate within factor 2 of MAN with $F = O(K^2)$ — polynomial.

The CommIT group has produced numerous follow-ups exploring the design space: Shariatpanahi-Caire schemes, Kaji-Caire polynomial constructions, etc. Together these constitute a major research program making coded caching practically deployable at large $K$ .

The significance: before this line of work, coded caching was considered theoretically elegant but practically infeasible for $K \gg 50$ . With polynomial-subpacketization schemes, $K$ can reach thousands. This opens the door to 6G-scale deployments.

coded-cachingsubpacketizationcommitgraph-coloringView Paper →

Graph-Coloring Delivery

Complexity: Coloring: polynomial in

|V| = KF

. Delivery:

\chi(G)

XOR messages. Total rate:

\chi(G)/F

file units.

Input: Structured placement; demand vector

\mathbf{d}

; conflict graph

G

Output: Delivery schedule.

1. Construct conflict graph

G

from placement and

\mathbf{d}

vertex = (user, missing subfile) pair; edge = delivery conflict.

2. Color

G

via greedy coloring (Chapter 4, Algorithm).

3. for each color class

\mathcal{C}

\quad

Form XOR message

X_\mathcal{C} = \bigoplus_{v \in \mathcal{C}} W_{d_{k(v)}, \mathcal{T}(v)}

where

v = (k(v), \mathcal{T}(v))

\quad

Broadcast

X_\mathcal{C}

6. end for

The coloring is the expensive step but happens in the placement design phase (offline). Delivery is a simple lookup.

Subpacketization Feasibility Across Schemes

Summary plot of MAN (exponential), PDA (polynomial, mid), and graph-coloring ( $K^2$ ). For $K > 50$ , MAN explodes; PDA and graph-coloring remain practical. For $K > 1000$ even PDA can grow; graph-coloring $K^2$ remains controlled.

Parameters

Target gain t3

Max K200

Key Takeaway

CommIT graph-coloring schemes achieve coded caching with polynomial subpacketization. $F = O(K^2)$ vs MAN's $\binom{K}{t}$ exponential. Rate within factor 2 of MAN. This makes coded caching deployable at realistic scale ( $K \sim 1000$ ). The theoretical-practical gap, the biggest obstacle to coded caching adoption, is largely closed by these schemes.

Open: Exact Polynomial-Subpacketization Optimality

Current graph-coloring schemes achieve rate within factor 2 of MAN with polynomial subpacketization. Whether the exact MAN rate (no gap) is achievable with polynomial subpacketization is open.

Known:

Rate gap $\geq 1$ inherent to any polynomial- $F$ scheme (Kaji-Caire 2020 lower bound).
Upper bound: factor 2 achievable with explicit constructions.
Conjecture: factor $\approx 1 + O(1/K)$ asymptotic gap; closing this is an active research area.

For practical deployment, a factor-2 rate gap is often acceptable — it still delivers substantial gains over uncoded delivery. Exact optimality is a mathematical refinement, not an operational blocker.

Graph Coloring for Coded Delivery

Conflict graph with 6 nodes, colored with 3 colors. Each color class corresponds to one XOR-coded transmission. Chromatic number = delivery rate; polynomial (

K^2

) chromatic number via structured placement gives practical subpacketization

F = O(K^2)

Placement Delivery Arrays (PDAs)Deployment at Finite Scale