# Sphere packing proper colorings of an expander graph

Preprint · Honglin Zhu

- Archive id: arxiv:2405.20368
- Published: 2024-05-30
- arXiv: https://arxiv.org/abs/2405.20368
- Source URL: https://arxiv.org/abs/2405.20368
- PDF: https://arxiv.org/pdf/2405.20368
- Provenance: arxiv

## Abstract

We introduce graphical error-correcting codes, a new notion of error-correcting codes on $\[q\]^n$, where a code is a set of proper $q$-colorings of some fixed $n$-vertex graph $G$. We then say that a set of $M$ proper $q$-colorings of $G$ form a $(G, M, d)$ code if any pair of colorings in the set have Hamming distance at least $d$. This directly generalizes typical $(n, M, d)$ codes of $q$-ary strings of length $n$ since we can take $G$ as the empty graph on $n$ vertices. We investigate how one-sided spectral expansion relates to the largest possible set of error-correcting colorings on a graph. For fixed $(δ, λ) \\in \[0, 1\] \\times \[-1, 1\]$ and positive integer $d$, let $f\_{δ, λ, d}(n)$ denote the maximum $M$ such that there exists some $d$-regular graph $G$ on at most $n$ vertices with normalized second eigenvalue at most $λ$ that has a $(G, M, d)$ code. We study the growth of $f$ as $n$ goes to infinity. We partially characterize the regimes of $(δ, λ)$ where $f$ grows exponentially or is bounded by a constant, respectively. We also prove several sharp phase transitions between these regimes.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.