112 Kikuchi LDC — Decomposition

112.1 Overview

This module covers §6 of the Alrabiah–Guruswami–Kothari–Manohar argument: the hypergraph decomposition step. Given \(3\)-uniform hypergraphs \(H_1, \dots , H_k\) on \(\mathrm{Fin}\, n\) and a threshold \(d\), one isolates the heavy pairs, i.e. the vertex pairs of degree more than \(d\), bounds their number by \(3m/d\), and splits each \(H_i\) into a residual part whose pair-degrees are at most \(d\) and a part carried by the heavy pairs.

112.2 Declarations

Definition 112.1 Heavy pairs of a hypergraph

✓

For a hypergraph \(H\) on \(\mathrm{Fin}\, n\) and a threshold \(d\), the set of heavy pairs

\[ P \; =\; \{ \, Q \subseteq \mathrm{Fin}\, n \; :\; \left\lvert Q\right\rvert = 2, \ \deg _H(Q) \gt d \, \} , \]

realised as the collection of two-element sets \(\{ u,v\} \) whose degree in \(H\) exceeds \(d\).

Theorem 112.2 Counting heavy pairs in a 3-uniform hypergraph

✓

Let \(H\) be a \(3\)-uniform hypergraph on the vertex set \(\mathrm{Fin}\, n\), so that every edge of \(H\) has exactly three vertices, and let \(d\) be a positive integer. Call a two-element set \(Q = \{ u,v\} \) of vertices *heavy* if its degree exceeds \(d\), that is, if more than \(d\) edges of \(H\) contain \(Q\), and let \(P\) denote the collection of all heavy pairs. Then

\[ \left\lvert P\right\rvert \cdot d \; \le \; 3\, \left\lvert H\right\rvert . \]

Theorem 112.3 Refining matchings to a bounded-pair-degree decomposition

✓

Let \(L\) be a normal form locally decodable code with message length \(k\) and block length \(n\), whose message indices \(i : \mathrm{Fin}\, k\) carry the \(3\)-uniform matchings \(H_i\) on \(\mathrm{Fin}\, n\), and let \(d \ge 1\) be a natural number. Then there is a family of hypergraphs \(H'_i\) on \(\mathrm{Fin}\, n\), one for each \(i\), such that every \(H'_i\) consists of edges of \(H_i\) (that is, \(H'_i \subseteq H_i\)) and is again \(3\)-uniform and a matching, while the union \(\bigcup _{i} H'_i\) satisfies the pair-degree bound \(d\): every pair of distinct vertices \(u \neq v\) is contained in at most \(d\) of its edges.