An Algebraic Interplay between Graphs, Codes, and Groups

Algebraic methods have proven efficient in solving various combinatorial problems, exemplified by spectral graph theory. Here, a graph, typically finite and simple, is associated with a defining algebraic structure; the adjacency matrix is often used. The eigenvalues of the matrix form the spectrum of the graph, and the core idea is to derive properties and obtain information about the original combinatorial structure from the spectrum. Several decades of studies have repeatedly shown that, while the spectrum lacks the complete detail of the adjacency matrix, it can be used to gain insight on various structural properties of the graph. This thesis is composed of two parts. The first part of the thesis is devoted to cospectrality of two different yet both widely used generalizations of graphs, namely hypergraphs and gain graphs. Hypergraphs extend flexibility by allowing edges to connect any number of vertices, while gain graphs assign edges elements from a group to convey relational information between the vertices. A prominent example of gain graphs is signed graphs, where all edges are labeled either positive or negative. Similarly to ordinary graphs, one can connect a hypergraph or a gain graph to an algebraic structure, for which a spectrum can be defined: namely, adjacency tensors are used for hypergraphs, while matrices for gain graphs are defined either over the respective group algebra or over the complex field using representation theory. As in graphs, one can ask the question whether certain structural properties of the combinatorial object can be deduced from it. A useful direction of research in approaching this question is introducing ways to construct combinatorial objects with different structural properties, but the same spectrum (the objects are then called cospectral): that way one can deduce which properties cannot be determined by the spectrum. In this thesis, new methods are introduced to construct cospectral hypergraphs and cospectral gain graphs. The second part of the thesis applies algebraic graph theory to error-correcting codes. The objective is to find the maximal size of a code, which is a subset of elements, or codewords, in a metric space, while maintaining a minimum distance between them. Such codes let us control the number of errors that are possible to correct after the encoded message is sent through a noisy channel, and maximizing the cardinality of the code allows for more information to be transmitted. In the thesis, the main focus is on the sum-rank metric, a generalization of widely used Hamming and rank metrics; the metric has attracted research interest due to its applications, for example in multi-shot network coding. In the thesis, the sum-rank-metric graph is introduced to model the respective space, its properties are investigated, and the spectrum is described. Key results include new upper bounds on the maximal size of a sum-rank-metric code with a given minimum distance. One bound exploits a connection between the code and the independent set in the graph, and is based on the eigenvalues of the graph in its definition, following the methods established by Abiad, Coutinho, and Fiol in 2019. Another bound is based on Delsarte’s theory, first introduced for Hamming metric in 1973 and later applied to rank metric in 1978; the approach is based on defining an association scheme on the metric space. In the thesis, a new sum-rank association scheme is proposed, solving the general case.