Resolvability of Hamming Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2019
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913416517517312 |
|---|---|
| author | Laird, Lucas Tillquist, Richard C. Becker, Stephen Lladser, Manuel E. |
| author_facet | Laird, Lucas Tillquist, Richard C. Becker, Stephen Lladser, Manuel E. |
| contents | 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öbner 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1907_05974 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Resolvability of Hamming Graphs Laird, Lucas Tillquist, Richard C. Becker, Stephen Lladser, Manuel E. Discrete Mathematics Combinatorics Optimization and Control 05C12, 05C50, 05C62, 68R10, 90C35, 92C40 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öbner 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. |
| title | Resolvability of Hamming Graphs |
| topic | Discrete Mathematics Combinatorics Optimization and Control 05C12, 05C50, 05C62, 68R10, 90C35, 92C40 |
| url | https://arxiv.org/abs/1907.05974 |