Error graphs and the reconstruction of elements in groups

DOI10.1016/J.JCTA.2008.11.005zbMATH Open1219.05095arXiv1110.5045OpenAlexW2086720637MaRDI QIDQ1024341FDOQ1024341

Vladimir Levenshtein, Johannes Siemons

Publication date: 17 June 2009

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Combinatorics of Coxeter Groups
• Title not available (Why is that?)
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient reconstruction of sequences from their subsequences of supersequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• A combinatorial Laplacian with vertex weights
• Efficient reconstruction of sequences
• Reconstruction of objects from a minimum number of distorted patterns
• Title not available (Why is that?)
• Efficient reconstruction of partitions
• Reconstruction of partitions

Cited In (6)

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

   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 👍 👎

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)