Stars of graphs of projective codes

Edyta Bartnicka · 2024

Read Stars of graphs of projective codes by Edyta Bartnicka (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00842.txt.

Introduction

Edyta Bartnicka published this mathematics paper in 2024. It studies a graph built from the subspaces of a finite vector space, where each node is a subspace of a fixed size and edges join overlapping ones. Inside that graph sits a smaller one whose nodes are projective codes, an error-correcting code concept dressed in geometry.

The paper sorts the largest tight-knit groups, called maximal cliques, inside the code graph. There turn out to be exactly two kinds: stars and tops. Bartnicka gives a complete description of the stars. A star gathers every code of the chosen size that contains one fixed subspace a step smaller. Such clean classifications are rare in this area. The result helps map how these code graphs are put together, which matters for both coding theory and finite geometry.

Catalog record

CREATOREdyta Bartnicka
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-00842

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stars of graphs of projective codes Edyta Bartnicka Abstract Let Γ k ​ ( V ) \Gamma_{k}(V) be the Grassmann graph whose vertex set is formed by all k k -dimensional subspaces of an n n -dimensional vector space V V over the finite field F q F_{q} consisting of q q elements. We discuss its subgraph Π ​ ( n , k ) q \Pi(n,k)_{q} formed by projective codes. We show that there are precisely two types of maximal cliques in Π ​ ( n , k ) q \Pi(n,k)_{q} : stars and tops. We give a complete description of stars, i.e., maximal cliques consisting of all k k -dimensional projective codes containing a certain ( k − 1 ) (k-1) -dimensional subspace of V V . Keywords: Projective codes, Grassmann graphs, Stars of Grassmann graphs Mathematics Subject Classification: 51E20, 51E22 1 Introduction Grassmann graphs, which have already been discussed in a number of books and papers (see, e.g. [ 8 , 9 ] ), are important for many reasons, for instance, they are classical examples of distance regular graphs (for more details see [ 2 ] ). The Grassmann graph \Gamma_{k}(V) is the simple graph whose vertex set {\mathcal{G}}_{k}(V) is formed by k -dimensional subspaces of an n -dimensional vector space V over the q -element field F_{q} . It can be identified with the graph of all linear codes [n,k]_{q} . Two distinct codes are connected by an edge if they have the maximal possible number of common codewords, i.e. their intersection is (k-1) -dimensional. We only deal with the case 1<k<n-1 since the Grassmann graph is complete for k=1 and k=n-1 . This paper concerns the restriction of the Grassmann graph to the set \Pi(n,k)_{q} of all projective codes [n,k]_{q} , i.e., linear codes such that columns in their generator matrices are non-zero and mutually non-proportional. They form the subgraph of the Grassmann graph denoted by \Pi[n,k]_{q} . We refer to [ 6 ] for the description of some properties of graphs of projective codes. The subgraphs of the Grassmann graph formed by various types of linear codes are considered, e.g. in [ 3 , 4 , 5 , 10 ] . Maximal cliques in these graphs are investigated in [ 1 , 7 ] for example. We direct our attention to maximal cliques of \Pi[n,k]_{q} . They are intersections of maximal cliques of \Gamma_{k}(V) with the set \Pi(n,k)_{q} . There are exactly two types of maximal cliques in \Gamma_{k}(V) : stars [S\rangle_{k} (made up by all k -dimensional subspaces of V containing a fixed (k-1) -dimensional subspace S ) or tops (consisting of all k -dimensional subspaces of V contained in a fixed (k+1) -dimensional subspace). Any non-empty intersection of a star or a top with the set \Pi(n,k)_{q} is a clique, but it need not be a maximal clique. If this intersection is a maximal clique of \Pi(n,k)_{q} , then we call it a star or a top of \Pi[n,k]_{q} , respectively. Here we provide the thorough description of stars of \Pi[n,k]_{q} . We consider two cases of S separately. First we assume that a generator matrix for a (k-1) -dimensional code S does not contain zero columns (Section 4 ), and secondly, we study the opposite case (Section 5 ). The starting point of both investigations is showing that if a generator matrix for S does not contain proportional columns, then the intersection of a star [S\rangle_{k} with the set \Pi(n,k)_{q} is a star of \Pi[n,k]_{q} . Next we study intersections of stars [S\rangle_{k} with the set \Pi(n,k)_{q} such that generator matrices for S contain proportional columns. We specify the number of projective codes in such intersections. Finally, we indicate all parameters for generator matrix for S to [S\rangle_{k}\cap\Pi(n,k)_{q} be a maximal clique of \Pi(n,k)_{q} (Theorems 1 and 3 ). Also, we show that there are maximal cliques of \Pi(n,k)_{q} which are stars and tops of \Pi[n,k]_{q} simultaneously. Examples of maximal cliques of \Pi(n,k)_{q} for different cases of S are also given. 2 Graph of projective codes Let F_{q} be the finite field consisting of q elements and let V=F_{q}^{n} be the n -dimensional vector space over F_{q} . Consider the Grassmannian {\mathcal{G}}_{k}(V) consisting of all k -dimensional subspaces of V . The Grassmann graph \Gamma_{k}(V) is the simple and connected graph whose vertex set is {\mathcal{G}}_{k}(V) . Its two vertices comprise an edge if, and only if, their intersection is (k-1) -dimensional. The Grassmann graph is complete if k=1 or k=n-1 , and that is why we suppose that 1<k<n-1 throughout the paper. One of the basic ideas of graph theory is that of a clique. A clique in an undirected graph is a subset of the set of its vertices such that any two distinct elements from this subset are joined by an edge. If a clique is not properly contained in any clique, then it is said to be maximal . Any maximal clique of \Gamma_{k}(V) is one of the following types: the star [S\rangle_{k} consisting of all k -dimensional subspaces of V containing a fixed subspace S\in{\mathcal{G}}_{k-1}(V) , or the top \langle U]_{k} consisting of all k -dimensional subspaces of V contained in a fixed subspace U\in{\mathcal{G}}_{k+1}(V) . Recall that V contains precisely \genfrac{[}{]}{0.0pt}{}{n}{1}_{q}=\genfrac{[}{]}{0.0pt}{}{n}{n-1}_{q}=[n]_{q}=\frac{q^{n}-1}{q-1} 1 -dimensional subspaces and the total number of elements of \langle S]_{k} is equal [n-k+1]_{q} . The intersection of two distinct maximal cliques of the form \langle S]_{k} contains at most one vertex. The intersection of [S\rangle_{k} and \langle U]_{k} is either empty or it contains precisely q+1 elements. The latter is realized exactly if the corresponding (k-1) -dimensional and (k+1) -dimensional subspaces S,U are incident. Any element of {\mathcal{G}}_{k}(V) is interpreted as a linear code [n,k]_{q} and it is called non-degenerate if its generator matrix does not contain zero columns. If columns in a generator matrix for a linear code are non-zero and mutually non-proportional, then this code is said to be projective . Write \Pi[n,k]_{q} for the restriction of the Grassmann graph to the set \Pi(n,k)_{q} of all projective codes. This is the simple graph whose set of vertices is \Pi(n,k)_{q} . It was shown in [ 6 , Theorem 1] that in the case when q\geq\binom{n}{2} , the graph \Pi[n,k]_{q} is connected. Any clique of \Pi(n,k)_{q} is a clique of \Gamma_{k}(V) since \Pi[n,k]_{q} is a subgraph of \Gamma_{k}(V) . And so any maximal clique of \Pi(n,k)_{q} is the intersection of \Pi(n,k)_{q} with a maximal clique of \Gamma_{k}(V) . We denote intersections [S\rangle_{k}\cap{\Pi}(n,k)_{q} and \langle U]_{k}\cap{\Pi}(n,k)_{q} by [S\rangle^{\Pi}_{k} and \langle U]^{\Pi}_{k} , respectively. They both can be empty or non-maximal cliques of \Pi(n,k)_{q} , otherwise they are called a star or a top of \Pi[n,k]_{q} , respectively. 3 Basic results Consider a (k-1) -dimensional linear code S . The set [S\rangle^{\Pi}_{k} is formed by all k -dimensional projective codes Q_{i} containing S . A generator matrix M_{i} for any code Q_{i} can be obtained from a generator matrix M=\left[\begin{matrix}v_{1}\\ v_{2}\\ \vdots\\ v_{k-1}\end{matrix}\right] for S by adding a certain n -dimensional row vector w_{i} which is not a linear combination of the rows from M . We can assume without loss of generality that M=\left[I_{k-1}\ \ A\right] , where I_{k-1} means the identity (

Read the complete text