Event: Cayley Graphs in Networks, Bioinformatics, Coding Theory, and Levenshtein鈥檚 Problem
Date: Wednesday 28 February 2024
Time: 17:00
Venue: MP401, Maths & Physics Building, University of Malta, Msida Campus
Speaker
Elena V. Konstantinova, Three Gorges Mathematical Research Center, China Three Gorges University
Abstract
Cayley graphs are commonly used in combinatorial and geometric group theory to encode the abstract structure of a group. Since 1986, after the SIAM International Conference on Parallel Processing, these graphs started to appear in computer science. There are many advantages in using Cayley graphs as models of interconnection networks such as vertex-transitivity (the same routing algorithm is used for each vertex), edge-transitivity (the edges in the graph all look the same), hierarchical structure (allows recursive constructions), high fault tolerance (graph remains connected after removing the maximum possible number of vertices), small degree and diameter.
The same properties of these graphs are used in Biological Cayley Networks. Cayley graphs appear in coding theory as error graphs and as a tool to solve the sequence reconstruction, a problem proposed by Levenshtein in 2001 as a reconstruction of sequences in the model where the same sequence is transmitted over multiple channels, and the decoder receives all the distinct outputs. In this model, vertices correspond to sequences and edges connect vertices under error transmissions.
From a graph-theoretical point of view, this is the problem of reconstructing a vertex from those vertices which are at a given distance from it. In this talk, we show using Cayley graphs as networks in computer science and bioinformatics and present some old and new results in the sequence reconstruction problem.
