# Can all unit-distance graphs have their vertices at algebraic integers?

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.

Obviously, we can necessarily find an embedding into the algebraic numbers $\bar{\mathbb{Q}}$. In other words, if $G$ is a unit-distance graph, we can find $g:G \rightarrow \bar{\mathbb{Q}}$ such that for all $(u,v) \in E(G)$, we have $|g(u) - g(v)| = 1$.

But what about if we further restrict ourselves to the algebraic integers $\mathcal O(\bar{\mathbb{Q}})$? Can all unit-distance graphs be embedded in such a way?

• What are you assuming about the graph $G$? Suppose I take the graph whose vertices are all the complex numbers, with an edge between two vertices at unit distance: $E = \{(z,w) : |z-w| = 1\}$. That seems to be unit distance by your definition (let $f$ be the identity function), but since it has uncountably many vertices we can't embed it in the algebraic numbers. – Nate Eldredge Jan 26 '15 at 1:55
• Presumably this is referring to finite graphs. – Robert Israel Jan 26 '15 at 1:59
• I didn't say that $f$ had to be injective. The finite case is equivalent to the infinite case by using Tychonoff compactness: Wlog $G$ is connected, and your favourite vertex $v$ is at the origin; then a vertex $u$ of distance $n$ from $v$ must lie in the compact ball of radius $n$. So the space of possible functions is a product of compact sets, and constraints of the form $|f(x) - f(y)| = 1$ define closed sets. By the finite case, any finite intersection of these sets is non-empty, so we are done by compactness. – Adam P. Goucher Jan 26 '15 at 8:25
• @Dima: The 6th degree roots of unity are algebraic integers. – Ilya Bogdanov Jan 26 '15 at 16:37
• @Dima: Not much difference. A hexagonal lattice maps to $K_3$... – Ilya Bogdanov Jan 26 '15 at 18:00

$\let\eps\varepsilon$No. I will present a graph whose realization necessarily contains a pair of vertices at distance $1/2$. THis cannot happen if the vertices are algebraic integers.

Firstly, we note that we may force a graph to contain a given piece of triangular lattice. It will be clear after we understand how to enforce the two opposite vertices of a $60^\circ-120^\circ$ unit-sided rhombus to be distinct. This is made by augmenting this rhombus to a Mosers' spindle: the vertices of its realization cannot coincide.

Thus we may enforce two vertices $A$ and $B$ to have any distance realized in the triangular lattice.

Now consider five points $A$, $B$, $C$, $D$, $E$ such that $AB=AC=AD=2$, $BC=DC=BE=DE=1$. If $B\neq D$ and $C\neq E$ then we have $CE=1/2$ as required. Thus it remains to enforce these relations.

To enforce $B\neq D$ it suffices to introduce a point $X$ with $BX=2$ and $DX=1$. To enforce $C\neq E$ it suffices to introduce $Y$ with $CY=2$ and $EY=\sqrt 3$.

REMARK (expanded). Maehara showed that any algebraic number can be realized as a distance between two vertices of a rigid unit-distance framework. This inspired the answer; I just needed to make the graph "more rigid". A similar reinforcing may be applied to any rigid framework to make it "absolutely rigid".

To perform this, for every two points $A$, $B$ at distance $d$ in the fixed rigid realization, one needs to ensure that $d-\eps<AB<d+\eps$ in each realization.

To ensure $AB>d-\eps$, find in the triangular lattice two distances $\ell_1$ and $\ell_2$ with $d-\eps <\ell_1-\ell_2<d$ and introduce a point with $AX=\ell_1$, $BX=\ell_2$.

Now, similarly to the construction above, one may realize the distance $1/n$ for every $n\in\mathbb N$. Finally, connecting $A$ and $B$ by an appropriate chain of segments of length $1/n$ one ensures that $AB<d+\eps$.

• More generally it is known that one can force any algebraic number to be the distance between some two vertices. – David Eppstein Jan 27 '15 at 8:12
• @David: Do you know the exact reference? – Ilya Bogdanov Jan 27 '15 at 18:25
• A slightly weaker version is that for any algebraic number there is a rigid framework and a configuration of that framework such that the number is a distance between two points in the framework. It's from Maehara, Hiroshi (1991), "Distances in a rigid unit-distance graph in the plane", Discrete Applied Mathematics 31 (2): 193–200, doi:10.1016/0166-218X(91)90070-D – David Eppstein Jan 28 '15 at 5:43
• The full version is in Tyszka, Apoloniusz (2000), "Discrete versions of the Beckman-Quarles theorem", Aequationes Mathematicae 59 (1-2): 124–133, doi:10.1007/PL00000119, MR 1741475 – David Eppstein Jan 28 '15 at 5:43
• Thanks! The link to the first one was in my answer, but I did not know about the second. – Ilya Bogdanov Jan 28 '15 at 9:09

Peter Brass, William O. J. Moser, János Pach. Research Problems in Discrete Geometry. Vol. 18. New York: Springer, 2005, p.238:

seems tangentially relevant:

in particular,

all unit-distance graphs in rational $2$- and $3$-dimensional spaces are bipartite.

So at least restricting to rationals limits the realizable unit-distance graphs.

• Or one could simply ask for the minimum degree of a field extension (over the rationals) that can be used for the coordinates of a specific graph, e.g., the Moser graph. What is the minimum such value for any 4-chromatic plane graph? – user39684 Jan 26 '15 at 4:27