It is demonstrated 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.
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.
We study upper bounds on the length of $\mathbb F_q$-linear QMDS codes in the folded Hamming distance relative to their other parameters, especially the field size $q$. Via a correspondence between such codes and families of subspaces, we relate the length problem to that of upper bounding $1$-subspace packings with re...
The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit colo...
Stefano Coniglio, Fabio Furini, I. Ljubić et al.· 0 citations
We study Schubert subspace codes, which are constant-dimension subspace codes with prescribed intersection conditions with a fixed subspace. Our goal is to construct codes of maximum possible size in the extremal distance cases where a natural counting upper bound applies. We give two families of constructions. The fir...
Gianira N. Alfarano, Alessandro Neri, Beatrice Toesca· arXiv.org· 0 citations
Gupta and Iosevich introduced the edge complexity of a graph as the minimum Fourier ratio of its adjacency matrix over all vertex labelings and bounded it below by graph energy divided by the square root of twice the number of edges. We characterize equality for a fixed labeling: the Fourier transform of the adjacency...
Vishal Gupta, A. Iosevich, J. Iosevich et al.· 0 citations
Torquato and Stillinger conjectured an exponential improvement of Minkowski's classical lower bound on the maximal density of sphere packings in high-dimensional Euclidean space $\mathbb{R}^d$ using a pair-correlation-function optimization framework. Conditional on their realizability conjecture, we show that a simple...
We investigate metric dimension and the localization game for several families of directed analogues of strongly regular graphs and their generalizations, adapting a probabilistic method of Babai (1980) for bounding the size of resolving sets in undirected strongly regular graphs. We derive upper bounds on the localiza...
R. Bailey, Brittany Pittman· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
