Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Abstract
We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for K3,3 and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most 2δ+C strings lie between any two strings with total distance exceeding their mutual distance by at most δ, where C is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for (ℝm,|·|1) for every m≥1.
Related
- Almost Homogeneity Characterizes Almost Bi-Lipschitz Euclidean Embeddability
- Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
- A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction
- Negative edge correlation in complete bipartite graphs
- The domination number of the 2-token graph of the complete bipartite graph
BibTeX
@misc{hou2026complete,
title = {{Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance}},
author = {Fengqi Hou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38919},
eprint = {2609.38919},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38919},
}
RIS
TY - UNPB
TI - Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
AU - Fengqi Hou
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38919
UR - https://arxiv.org/abs/2609.38919
AB - We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for K_3,3 and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most 2^δ+C strings lie between any two strings with total distance exceeding their mutual distance by at most δ, where C is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for (ℝ^m,|·|_1) for every m≥1.
ER -