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, , ₃ (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.