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
    Commented Jan 26, 2015 at 1:55
  • 2
    $\begingroup$ Presumably this is referring to finite graphs. $\endgroup$
    – Robert Israel
    Commented 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
    Commented Jan 26, 2015 at 8:25
  • 1
    $\begingroup$ @Dima: The 6th degree roots of unity are algebraic integers. $\endgroup$
    – Ilya Bogdanov
    Commented Jan 26, 2015 at 16:37
  • 1
    $\begingroup$ @Dima: Not much difference. A hexagonal lattice maps to $K_3$... $\endgroup$
    – Ilya Bogdanov
    Commented 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
    Commented Jan 27, 2015 at 8:12
  • $\begingroup$ @David: Do you know the exact reference? $\endgroup$
    – Ilya Bogdanov
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jan 26, 2015 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .