18
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Jan 26 '15 at 1:55
  • 2
    $\begingroup$ Presumably this is referring to finite graphs. $\endgroup$ – Robert Israel Jan 26 '15 at 1:59
  • $\begingroup$ 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. $\endgroup$ – Adam P. Goucher Jan 26 '15 at 8:25
  • 1
    $\begingroup$ @Dima: The 6th degree roots of unity are algebraic integers. $\endgroup$ – Ilya Bogdanov Jan 26 '15 at 16:37
  • 1
    $\begingroup$ @Dima: Not much difference. A hexagonal lattice maps to $K_3$... $\endgroup$ – Ilya Bogdanov Jan 26 '15 at 18:00
13
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ More generally it is known that one can force any algebraic number to be the distance between some two vertices. $\endgroup$ – David Eppstein Jan 27 '15 at 8:12
  • $\begingroup$ @David: Do you know the exact reference? $\endgroup$ – Ilya Bogdanov Jan 27 '15 at 18:25
  • $\begingroup$ 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 $\endgroup$ – David Eppstein Jan 28 '15 at 5:43
  • $\begingroup$ 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 $\endgroup$ – David Eppstein Jan 28 '15 at 5:43
  • $\begingroup$ Thanks! The link to the first one was in my answer, but I did not know about the second. $\endgroup$ – Ilya Bogdanov Jan 28 '15 at 9:09
6
$\begingroup$

Not an answer to your (interesting!) question. But this quote from

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:


      Brassetal


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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – user39684 Jan 26 '15 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.