Resolvability of Hamming Graphs
| Autor: | Manuel E. Lladser, Lucas Laird, Richard C. Tillquist, Stephen Becker |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Geodesic Discrete Mathematics (cs.DM) Graph embedding General Mathematics 0102 computer and information sciences 01 natural sciences Combinatorics FOS: Mathematics Mathematics - Combinatorics 0101 mathematics Mathematics - Optimization and Control Mathematics Discrete mathematics 010102 general mathematics Hamming distance Metric dimension Vertex (geometry) Hamming graph 010201 computation theory & mathematics Optimization and Control (math.OC) Hypercube Combinatorics (math.CO) 05C12 05C50 05C62 68R10 90C35 92C40 Hamming code Computer Science - Discrete Mathematics |
| Popis: | A subset of vertices in a graph is called resolving when the geodesic distances to those vertices uniquely distinguish every vertex in the graph. Here, we characterize the resolvability of Hamming graphs in terms of a constrained linear system and deduce a novel but straightforward characterization of resolvability for hypercubes. We propose an integer linear programming method to assess resolvability rapidly, and provide a more costly but definite method based on Gr\"obner bases to determine whether or not a set of vertices resolves an arbitrary Hamming graph. As proof of concept, we identify a resolving set of size 77 in the metric space of all octapeptides (i.e., proteins composed of eight amino acids) with respect to the Hamming distance; in particular, any octamer may be readily represented as a 77-dimensional real-vector. Representing k-mers as low-dimensional numerical vectors may enable new applications of machine learning algorithms to symbolic sequences. Comment: 19 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|