报告学者：Elena Konstantinova

报告者单位：Sobolev Institute of Mathematics, Novosibirsk State University, Three Gorges University

报告时间：2024年6月25日（周二）下午4:30-5:30

报告地点：学生活动中心10层会议室

报告摘要：Cayley graphs are commonly used in combinatorial and geometric group theory to encode the abstract structure of a group. Since 1986 after SIAM International Conference on Parallel Processing these graphs appear in computer science. There are many advantages in using Cayley graphs as model of interconnection networks such as vertex-transitivity (the same routing algorithm is used for each vertex), edge-transitivity (every edge in the graph looks 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 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 by its neighbours being at a given distance from the vertex. 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.