Combinatorial Bounds for Codes over Metric Spaces: Ramsey-Sidorenko Thresholds and Subgraph Counts
arXiv:2607.27098
The paper studies codes in finite metric spaces by modeling them as independent sets in proximity graphs, extending the Gilbert‑Varshamov bound and showing that local subgraph counts cannot improve this bound for Hamming spaces.
Abstract
This paper investigates the relationship between coding theory and extremal combinatorics by representing codes in general metric spaces as independent sets in proximity graphs. We provide a generalized framework for the Gilbert-Varshamov (GV) bound applicable to codes over any finite metric space and explore the conditions under which global combinatorial parameters can force the existence of codes exceeding this bound. Central to our analysis is the introduction of Ramsey-Sidorenko and independence-forcing graphs. We establish density thresholds for various graph families and utilize the Karush--Kuhn--Tucker conditions to analyze entropy optimization in the Hamming case. Furthermore, we derive upper bounds on code sizes using fractional packings in vertex-transitive and nonedge-transitive graphs. Our findings demonstrate that local subgraph statistics alone are insufficient to surpass the GV bound in the Hamming case, suggesting that improvements must stem from large-scale structural properties of the space.
23 pages, no figures