turkmath.org

Cayley graphs are commonly used in combinatorial and geometric group theory to encode the abstract structure of a group. These graphs also appear in coding theory as error graphs and as a tool to solve the sequence reconstruction problem. This problem was proposed by Vladimir Levenshtein in 2001 as a local 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. This problem was completely solved for the Hamming graph and the Johnson graph. The main advantage in getting exact values of the minimum number of transmission channels required to recover the transmitted sequence exactly is that both graphs are distance-regular. This structural property allows to apply general approaches to solve the problem for any vertex in a graph. The situation is completely changed whenever a graph is not a distance-regular. In this talk, we discuss the main difficulties in solving this problem for Cayley graphs over the symmetric group that are not distance-regular graphs. In particular, the problem is discussed for reversal and transposition graphs. For example, transpositions of two adjacent elements of a permutation lead to a Cayley graph over the symmetric group known as the bubble-sort graph. The distance in this graph is called the bubble-sort distance in computer science or Kendall’s τ-metric in statistics. We also consider the sequence reconstruction problem of permutations by the single Hamming errors.