6.3 The Ahlswede Cai Theorem

The full power of compression only emerges when every product of graphs taken from some basic set, { H ₁ , H ₂ , } with arbitrary mulitiplicities, has nested solutions . We may then prove that has nested solutions by induction on d. For large d there are many factorizations of G, each giving us the opportunity to apply the inductive hypothesis and strengthen the compressibility order. Such arguments fall naturally into three cases:

• d = 1: Compression does not apply.

• d = 2: Compression applies, giving the product order on as compressibility order .

• d ? 3: Compression applies and the compressibility order is generally much stronger than product order on .

Paradoxically, the cases d = 1 , 2 are often the most difficult. The next theorem, by Ahlswede and Cai [3], gives some indication of why this is.

Recall (Chapter 1, Section 1.2.3) that if is a sequence of totally ordered sets, then lexicographic order on their product, _{1 2 n} , is the total order defined by x < y if ? m such that x ₁ = y ₁ , x ₂ = y ₂ , , x _{m ?1} = y _{m ? 1} and x _m < y _m (see also Chapter 3, Section 3.5) .