On the distance between linear codes (Q268498): Difference between revisions

Let \(V\) be an \(n\)-dimensional vector space and let \(\Gamma_k(V)\) be the Grassmann graph, i.e., the graph with as vertices the set of \(k\)-dimensional subspaces of \(V\) whose vertices are adjacent if and only if the corresponding subspaces intersect in a \((k-1)\)-dimensional space. Let \(\Gamma(n,k)_q\) denote the restriction of \(\Gamma_k(V)\), where \(V=\mathbb{F}_q^n\), to the set of all linear codes of length \(n\), dimension \(k\) over the alphabet \(\mathbb{F}_q\) that are non-degenerate. Equivalently, these codes are \(k\)-dimensional subspaces of an \(n\)-dimensional vector space over \(\mathbb{F}_q\) that are not contained in one of the coordinate hyperplanes. In many cases such e.g. for dual polar graphs, the distance between two vertices in the restriction of the Grassmann graph is the same as the distance between these two vertices in the original graph. In this paper, the authors show that for the restriction of the Grassmann graph to \(\Gamma(n,k)_q\), this is not always the case. More precisely, they show that (1) if \(n<(q+1)^2+k-2\), then the distance in \(\Gamma(n,k)_q\) and \(\Gamma_k(V)\) coincides (2) if \(m\) is a number satisfying \(k-\min\{k,n-k\}\leq m\leq k-2\) and \(n\geq \frac{q^{k-m}-1}{q-1}.(q+1)+m\), then there exist two non-degenerate linear codes \(X\), \(Y\) of length \(n\) and dimension \(k\) for which the distance in \(\Gamma(n,k)_q\) and \(\Gamma_k(V)\) differs exactly \(1\).