{"id":"arxiv:2405.20368","kind":"preprint","title":"Sphere packing proper colorings of an expander graph","authors":["Honglin Zhu"],"author_count":1,"year":2024,"published":"2024-05-30","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2405.20368","nct_id":null,"source_url":"https://arxiv.org/abs/2405.20368","archive_url":"https://space-kitty.com/papers/arxiv:2405.20368","updated":"2025-01-27","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2405.20368","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["math.CO","cs.IT"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}