Sphere packing proper colorings of an expander graph

We introduce a new notion of error-correcting codes on [q]ⁿ where a code is a set of proper q-colorings of some fixed n-vertex graph G. For a pair of proper q-colorings $X, Y$ of G, we define their distance as the minimum Hamming distance between X and σ(Y) over all σ ∈ Sq. We then say that a set of proper q-colorings of G is δ-distinct if any pair of colorings in the set have distance at least δ n. We investigate how one-sided spectral expansion relates to the largest possible set of δ-distinct colorings on a graph. For fixed (δ, λ) ∈ [0, 1] × [-1, 1] and positive integer d, let fδ, λ, d(n) denote the maximal size of a set of δ-distinct colorings of any d-regular graph on at most n vertices with normalized second eigenvalue at most λ. We study the growth of f as n goes to infinity. We partially characterize regimes of (δ, λ) where f grows exponentially, is finite, and is at most $1$, respectively. We also prove several sharp phase transitions between these regimes.