Coding of structurally ordered information and embeddings of discrete spaces (Q2713982)

The author considers a relation between coding of structurally ordered information and embedding into discrete spaces preserving some metric properties. Let \(X\), \(Y\) be finite sets and let \(\rho_X\), \(\rho_Y\) be integer-valued metrics. A function \(f\:X\to Y\) is called a \(\langle p, q\rangle\)-embedding if the following two conditions are satisfied: \(\rho_Y\bigl(f(x_1),f(x_2)\bigr) \leq p\) whenever \(\rho_X(x_1,x_2) \leq p\) and \(\rho_Y\bigl(f(x_1),f(x_2)\bigr) \geq q\) whenever \(\rho_X(x_1,x_2) \geq q\). Some combinatorial problems (constructions of the snake-in-the-box codes, distance-preserving \(\langle t,n\rangle\)-codes, Gray codes) are studied in terms of \(\langle p, q\rangle\)-embeddings. A survey of the main results in this field is also presented. In addition, the author considers \(\langle p, q\rangle\)-embeddings of graphs with ordinary metrics. Some theorems are discussed which connect the metric extension property and \(\langle p, q\rangle\)-embeddings of graphs.