Expander Graphs: Deep Dive

What Are Expander Graphs?

A family of sparse graphs with strong connectivity properties — they "expand" rapidly as you traverse outward from any starting point.

Sparse
O(d)
Constant degree (few edges per vertex)
High Connectivity
λ₂ < d
Large spectral gap (hard to partition)
Rapid Mixing
O(log n)
Fast convergence to uniform distribution
Expansion
|∂S| ≥ α|S|
Neighbors grow proportionally

Encoding Path Example

Imagine encoding the byte sequence: 0x41 0x42 0x43 (ABC) by traversing the expander graph

S₀ START S₂ A₀ 0x41 A₂ A₃ B₀ 0x42 B₂ B₃ C₀ 0x43 C₂ E₀ END E₂ Layer 0 Layer 1 Layer 2 Layer 3 Layer 4
Step 1: 0x41 ('A')
START → A
Choose edge based on byte value modulo degree
Step 2: 0x42 ('B')
A → B
Current state + symbol → next state
Step 3: 0x43 ('C')
B → C
Path uniquely determined by input sequence
Step 4: Terminate
C → END
Final state encodes compressed representation

How Encoding Works

  1. Initialize: Start at designated initial vertex
  2. For each symbol:
    • Compute hash or modulo operation on symbol value
    • Select outgoing edge based on result
    • Traverse to next vertex
    • Record transition choice (edge index)
  3. Output: Sequence of edge choices encodes original data
  4. Compression: If graph has good mixing, fewer bits needed to specify path than original data

Key Properties for Compression

Expansion Property:
For any subset S of vertices:
|Neighbors(S)| ≥ α × |S|

α = expansion constant (e.g., 0.8)

Spectral Gap:
λ₁ - λ₂ ≥ gap

Larger gap → faster mixing
→ better entropy coding efficiency

Intuition: Expansion ensures many possible next states, giving encoder flexibility to match symbol probabilities efficiently.

Trade-offs vs Arithmetic Coding

✓ Potential Advantages

  • Constant-time edge lookup (no interval subdivision)
  • Parallelizable state transitions
  • Natural error correction properties
  • Deterministic construction (reproducible graphs)

✗ Challenges

  • Graph construction overhead
  • State space explosion for large alphabets
  • Proving optimality harder than arithmetic coding
  • Decades less optimization than ANS/arithmetic
18 / 22