Error graphs and the reconstruction of elements in groups

DOI10.1016/J.JCTA.2008.11.005MaRDI QIDQ1024341zbMATH OpenOpenAlexFDO

Authors Vladimir Levenshtein, Johannes Siemons

Publication date 17 June 2009

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.5045

zbMATH Keywords

computational biologyreconstructionStirling numberscoding theorybiological sequence analysiserror graphsmetric balls of verticesundirected Cayley graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Coding theorems (Shannon theory) (94A24) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new problem in graph theory which is also based on the consideration of metric balls of vertices, but which is distinct from the traditional packing and covering problems. This problem is motivated by applications in information transmission when redundancy of messages is not sufficient for their exact reconstruction, and applications in computational biology when one wishes to restore an evolutionary process. It can be defined as the reconstruction, or identification, of an unknown vertex in a given graph from a minimal number of vertices (erroneous or distorted patterns) in a metric ball of a given radius r around the unknown vertex. For this problem it is required to find minimum restrictions for such a reconstruction to be possible and also to find efficient reconstruction algorithms under such minimal restrictions. In this paper we define error graphs and investigate their basic properties. A particular class of error graphs occurs when the vertices of the graph are the elements of a group, and when the path metric is determined by a suitable set of group elements. These are the undirected Cayley graphs. Of particular interest is the transposition Cayley graph on the symmetric group which occurs in connection with the analysis of transpositional mutations in molecular biology. We obtain a complete solution of the above problems for the transposition Cayley graph on the symmetric group.

Recommendations

• Vertex reconstruction in Cayley graphs
• Reconstruction of permutations distorted by reversal errors
• Some problems on Cayley graphs
• On reconstruction of signed permutations distorted by reversal errors
• Metric intersection problems in Cayley graphs and the Stirling recursion

Cites work

• scientific article; zbMATH DE number 2185633 (Why is no real title available?)
• scientific article; zbMATH DE number 3149991 (Why is no real title available?)
• scientific article; zbMATH DE number 3927214 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 3641625 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 2123603 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A combinatorial Laplacian with vertex weights
• Combinatorics of Coxeter Groups
• Efficient reconstruction of partitions
• Efficient reconstruction of sequences
• Efficient reconstruction of sequences from their subsequences of supersequences
• On bounds for the incidentor chromatic number of a directed weighted multigraph
• Reconstruction of objects from a minimum number of distorted patterns
• Reconstruction of partitions
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey

Cited in

(9)

• Balanced reconstruction codes for single edits
• Some problems on Cayley graphs
• Reconstruction of permutations distorted by single Kendall \(\tau\)-errors
• Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
• Vertex reconstruction in Cayley graphs
• The `Butterfly effect' in Cayley graphs with applications to genomics.
• The sequence reconstruction problem for permutations with the Hamming distance
• Nice error frames, canonical abstract error groups and the construction of SICs
• Metric intersection problems in Cayley graphs and the Stirling recursion

This page was built for publication: Error graphs and the reconstruction of elements in groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024341)