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?

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

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\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, 2015 at 8:12
  • $\begingroup$ @David: Do you know the exact reference? $\endgroup$
    – Ilya Bogdanov
    Jan 27, 2015 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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
1
  • 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$
    – Geoffrey Exoo
    Jan 26, 2015 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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