<figure><img src="image_1.png" /></figure>

HAL
open science

# Drawing Diestel-Leader graphs in 3D

Amandine Escalier

► To cite this version:

Amandine Escalier. Drawing Diestel-Leader graphs in 3D. 2023. hal-03955883

HAL Id: hal-03955883

https://hal.science/hal-03955883

Preprint submitted on 25 Jan 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Drawing Diestel-Leader graphs in 3D

Amandine Escalier

January 25, 2023

## Abstract

In this short note we give some code to represent Diestel-Leader graphs in 3D. The code is written in TikZ.

<figure><img src="image_3.png" /><figcaption>Figure 1: Two views of the Diestel-Leader graph DL(3, 2)</figcaption></figure>

The history of Diestel-Leader graphs takes its root in the following question asked by Woess [Woe91]: is every connected locally finite vertex-transitive graph quasi-isometric to some Cayley graph? In the hope of answering no to this question, Diestel and Leader [DL01] defined what we now call *Diestel-Leader graphs*. However it was only later, in the famous papers of Eskin, Fisher and Whyte [EFW07, EFW12] that it was showed that some of the aforementioned graphs are not quasi-isometric to any Cayley graph.

In this note we give a code to draw these graphs in 3D, using TikZ. Readers only interested by producing an illustration of some DL(p, q) can jump to the last pages of this article (or the end of the .tex file on arXiv) and copy-paste the code given in Section 2.2, write the wanted values of p and q (line 29) and then compile. Readers wishing to change the code can rely on the description made in Section 2.1. We start this note with a short reminder of the definition of Diestel-Leader graphs.
# 1 Diestel-Leader graphs

We recall here the definition of Diestel-Leader graphs. We refer to [Woe91, Section 2] for more details.

## 1.1 Tree and horocycles

Let $q \ge 2$ and denote by $T = T_q$ the homogeneous tree of degree $q+1$. Denote by $d$ the usual graph distance on $T$ fixing to 1 the length of an edge.

A geodesic ray is an infinite sequence $(v_n)_{n \in \mathbb{N}}$ of vertices of $T$ such that $d(v_i, v_j) = |i - j|$, for all $i, j \in \mathbb{N}$. We say that two rays are equivalent if their symmetric difference<fnref n="1" /> is finite. We call end of $T_q$ an equivalence class of rays in $T$ and denote by $\partial T$ the space of ends of $T$.

Let $\hat{T} := \partial T \cup T$. For any elements $x, y \in \hat{T}$ there is a unique geodesic in $\hat{T}$, denoted by $\overline{xy}$, that connects $x$ and $y$.

Now fix an end $w \in \partial T$, the confluent of two elements $x, y \in \hat{T} \setminus w$ with respect to $w$, denoted by $x \wedge y$, is defined as the element $c = x \wedge y$ such that $\overline{xw} \cap \overline{yw} = \overline{cw}$, that is to say: the confluent is the point where the two geodesics $\overline{xw}$ and $\overline{yw}$ towards $w$ meet (see Figure 2).

<figure><img src="image_4.png" /><figcaption>Figure 2: Example of the confluent of two points in $T_2$</figcaption></figure>

Now, fix a root vertex $o \in T$. We define below a Busemann function, which will allow us to endow our tree with some height notion.

**Definition 1.1.** Let $w \in \partial T_q$. The Busemann function with respect to $w$ is the map $\mathfrak{h} : T \to \mathbb{Z}$ defined by

$$ \mathfrak{h}(x) = d(x, x \wedge o) - d(o, x \wedge o). $$

**Example 1.2.** Let's turn back to Figure 2 and let $o = y$ be the root. Then for $x$ represented in the figure, we have $x \wedge o = c$ and thus $d(x, x \wedge o) = 2$ and $d(o, x \wedge o) = 1$. Therefore $\mathfrak{h}(x) = 1$.

**Definition 1.3.** Let $w \in \partial T_q$ and $k \in \mathbb{N}$. The horocycle with respect to $w$, denoted by $H_k$, is the set $H_k = \{x \in T : \mathfrak{h}(x) = k\}$.

<footnote n="1">¹Recall that the symmetric difference of two sets A and B is defined by $|A \Delta B| = (A \setminus B) \cup (B \setminus A)$</footnote>
We refer to Figure 3 for an illustration. Note that every horocycle in $\hat{T}$ is infinite. Every vertex $x$ in a horocycle $H_k$ has exactly one neighbour $x^-$ (called the **predecessor**) in $H_{k-1}$ and exactly $q$ neighbours (called **successors**) in $H_{k+1}$ (see Figure 3 for an illustration).

<figure><img src="image_5.png" /><figcaption>Figure 3: Horocycles, predecessor, successors</figcaption></figure>

## 1.2 Diestel-Leader graphs

Now fix $p, q \ge 2$ and consider $T_p$ and $T_q$ with respective roots $o_p$ and $o_q$, and respective reference ends $w_p$ and $w_q$.

**Definition 1.4.** The Diestel-Leader graph $DL(p, q)$ is the graph with set of vertices

$$V(DL(p, q)) = \{(x, y) \in T_p \times T_q : h(x) = -h(y)\}.$$

and where there is an edge between two elements $(x_1, y_1)$ and $(x_2, y_2)$, if and only if $(x_1, x_2)$ is an edge in $T_p$ and $(y_1, y_2)$ is an edge in $T_q$.

If there is an edge between two vertices $(x_1, y_1)$ and $(x_2, y_2)$ in $DL(p, q)$, then remark that either

* $x_2$ is one of the $p$-children of $x_1$ in $T_p$ and in this case $y_2$ is the only predecessor of $y_1$ in $T_q$, namely $y_2 = y_1^-$ (see Figure 4a);

* or $x_2 = x_1^-$ is the unique predecessor of $x_1$ in $T_p$ and in this case $y_2$ is one of the $q$-children of $y_1$ in $T_q$ (see Figure 4b).

We represent these two cases in Figure 4. The edge is drawn in blue, the $p$-regular tree in orange and the $q$-regular tree in brown. In light blue is represented the Diestel-Leader graph, we refer to Figure 5 for a drawing of $DL(p, q)$ itself. Note that in Figure 5, the corresponding $T_p$ and $T_q$ are drawn on the planes $x = 0$ and $y = 0$ respectively.

**Remark 1.5.** When $p = q$ the graph $DL(p, q)$ is a Cayley graph of the Lamplighter group $Z/pZ \wr Z$.

## 2 The code

The complete code is given in page 6, and written in TikZ. We start by some comments on how the coordinates were computed and how the loops work.
<figure><img src="image_6.png" /><figcaption>Figure 4: Drawing an edge in DL(p, q): two cases</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: Two different Diestel-Leader graphs, represented at the same scale</figcaption></figure>
## 2.1 Comments on the code

**Variables** The main variables are \p, \q (line 29) and \layers (line 35). The first two variables correspond to the number of children in the first and the second tree respectively, that is to say the p and q in DL(p, q). Finally, the height of the graph is parametrized by \layers: there are \layers+1 different heights of vertices appearing on the graph.

With the values given in the example in Section 2.2, we produce the left image in Figure 1.

Finally changing the values in view={165}{10} (line 17) will change the point of view (see for example Figure 1). For more details on how to parametrize the view, see the pgfplots manual [Feu21, Section 4.11.1, page 311].

**Structure of the code** The code is composed of one main loop cut in two parts: the first one that draws the tree on the plane y = 0, and the second one that draws simultaneously the tree located on the plane x = 0 and the Diestel-Leader graph.

In this description “height” will stand for the z-coordinates in the picture.

**Lines 58 to 72** We start by drawing the regular tree of degree p represented on the plane y = 0, in orange in the pictures. This tree grows from the bottom to the top.

At height h there are $p^h$ vertices to draw and the space between two consecutive nodes at this height is $pspace = p^{\text{layers}-h}$ (in particular at the top, when h = layers, the space between two nodes is equal to 1).

Moreover the first horizontal node at height h has for horizontal coordinates the middle of $[0, p^{\text{layers}-h} - 1]$ that is to say

$$p^{\text{layers}-h}/2 - 0.5 = \text{pspace}/2 - 0.5,$$

and therefore, if h ≠ layers, the first of its child (at height n = h+1) has coordinates the middle of $[0, p^{\text{layers}-n} - 1]$, namely $p^{\text{layers}-h}/(2p) - 0.5 = \text{pspace}/(2p) - 0.5$.

<figure><img src="image_8.png" /><figcaption>Figure 6: Ranges of the different loop variables for the first tree</figcaption></figure>

Now fix n ∈ {1, ..., layers}, the loop starting at line 58 goes over all the nodes at height h = n − 1 and draws the edges between a node at height n − 1 and its q children at height n. To do so, it fixes the horizontal position k ∈ {1, ..., p^{n−1} − 1} of the chosen node at height n − 1. This node thus has to be shifted to the right by pshift = k * pspace and hence drawn at the coordinates
$$ (\text{pspace} - 0.5 + k * \text{pspace}, 0, n - 1) = (\text{pspace} - 0.5 + \text{pshift}, 0, n - 1). $$

The children are then located at height $n$. Similarly as above, the first child to be drawn has for horizontal coordinates the middle of $[0, q^{\text{layers}-n-1} - 1]$ and the “\child-th” is shifted to right by child * pspace. Hence the coordinates of the “\child-th” child is given by

$$ (\text{pspace}/q - 0.5 + \text{pshift} + \text{child} * \text{pspace}, 0, n - 1). $$

**Lines 79 to 116** This loop draws the brown tree on the plane $x = 0$ and the Diestel-Leader graph at the same time.

**Lines 79 to 95** The variable $k$ at line 79 goes through the $q^{\text{rev}} = q^{\text{layers}-n}$ vertices at height $n$. Denote by $v$ the $k$-th vertex at this height. The loop for \child in $\{0, \dots, \text{q}-1\}$ goes through the $q$ childrens of $v$ and draw the edge between $v$ and the \child-th child at height $n-1$. The coordinates of the nodes are computed in the same way as in the previous loop. (Remark that the heights in the current loop are swapped: the parent is at height $n$ and the children are at height $n-1$ whereas in the previous one, the childrens were at height $n$ and the parent at height $n-1$.)

**Lines 99 to 114** Inside the loop for \child in $\{0, \dots, \text{q}-1\}$ (starting line 81) lies also the part that draws the Diestel-Leader. Remember that $v$ is the current vertex at height $n$ in the $q$-regular tree $T_q$.

The loop for \kk in $\{0, \dots, \text{pnm}-1\}$ goes through all the vertices in the orange tree, drawn at height $n$. It will correspond to all the couple $(u, v)$ such that $u \in T_p$ is drawn at the same height (the $z$-coordinates) than $v$. To a given child $c$ of $v$ in $T_p$, corresponds then the edge in the Diestel-Leader linking $(u, v)$ to $(u, c)$, where we recall that $u$ is the unique predecessor of $u$ in $T_p$ (see page 3). Hence the point $(u, v)$ will be drawn at height $n$ and will have the same $x$-coordinates than $u$ and same $y$-coordinates than $v$, namely

$$ \begin{cases} x = \text{pspace}/(2p) - 0.5 + \text{pshiftprime} + \text{childprime} * \text{pspace}/p, \\ y = q^n/2 - 0.5 + \text{qshift}, \\ z = n \end{cases} $$

Similarly, the node $(u, c)$ will be drawn at height $n-1$ and will have the same $x$-coordinates than $u$ and same $y$-coordinates than $c$, namely

$$ \begin{cases} x = \text{pspace}/2 - 0.5 + \text{pshiftprime}, \\ y = q^n/2 - 0.5 + \text{qshift} + \text{child} * q^n/q, \\ z = n - 1 \end{cases} $$

## 2.2 The code

1. \documentclass[border=0mm]{standalone}

2. \usepackage[x11names]{xcolor}

3. \usepackage{tikz}
\usetikzlibrary{calc,math,backgrounds}

4

\usepackage{ifthen}

5

\usepackage{pgfplots}

6

\pgfplotsset{compat=1.18}

7

%

8

%

9

%

10

\definecolor{MFCB}{cmyk}{0,0.06,0.20,0.6}

11

\colorlet{Orange}{DarkOrange3!85}

12

% + DeepSkyBlue4

13

%

14

\begin{document}

15

\begin{tikzpicture}%[scale=0.5] %Uncomment to change the scale

16

\begin{axis}[

17

view={165}{10}, % Change the point of view.

18

% view={150}{10}, % Change the point of view.

19

xlabel=$x$,

20

ylabel=$z$,

21

ylabel=$y$,

22

]

23

\tikzmath{

24

%

25

%

26

% ---- PARAMETERS p AND q OF DL(p,q)

27

%

28

%

29

\p=2; \q=3;

30

%

31

%

32

% ---- HEIGHT PARAMETER

33

%

34

%

35

\layers=3;% If layer=3 then there are

36

%4 heights appearing, numbered 0 1 2 3

37

%

38

%

39

for \n in {1,...,\layers}{% Vertical, \n stands for the height

40

%

41

% Stored variables

42

%

43

% % For the q regular tree

44

\qrev=pow(\q,\layers-\n);% Stores the value 2^(L-n)

45

\qn=pow(\q,\n);%Stores the value q^n

46

% For the p regular tree drawn from bottom to top

47

\pspace=pow(\p,\layers+1-\n); % (space between two nodes

48
% at height layers-(n-1))
\pnm=pow(\p,\n-1);% Stores p^(layers-nprime)=p^(n-1)
% ----------------------------------------------------------------------
% Regular tree of degree p drawn on the plane y=0
% Drawn starting from the bottom to the top
% ----------------------------------------------------------------------
for \k in {0,...,\pnm-1}{%Horizontal
\pshift=\k*\pspace;% Horizontal shift: k*p^n
for \child in {0,...,\p-1}{% Child of the considered node
{ % draw an edge
\addplot3[Orange!20,thick] coordinates%
{%(The vertex at the top (ie. the child) at height n
(\pspace/(2*\p)-0.5+\pshift+\child*\pspace/\p,0,\n)
% The vertex below (ie. the parent) at height n-1
(\pspace/2-0.5+\pshift,0,\n-1)};
}; % End of edges drawing
}; % End of the loop "for \child in"
};% End of the loop "for \k in "
% =====================================================================
% Regular tree of degree q drawn on the plane x=0
% ----------------- AND -----------------------------
% The Diestel-Leader graph
% =====================================================================
for \k in {0,...,\qrev-1}{%Horizontal
\qshift=\k*\qn;% Horizontal shift: k*q^n
for \child in {0,...,\q-1}{%Goes through the q children
% in the q-regular tree
%
% The Tree drawn on the plane x=0 (the light brown one)
%
{ %Drawing the edge
\begin{scope}[on background layer]
\addplot3[MFCB!20,thick] coordinates%
{((0,\qn/2-0.5+\qshift,\n)
% child at height n-1
(0,\qn/(2*\q)-0.5+\qshift+\child*\qn/\q,\n-1)};
\end{scope}
};%End of drawing for the edge of the tree
%
% The Diestel-Leader
%
for \kk in {0,...,\pnm-1}{
\pshiftprime=\kk*\pspace;% horizontal shift
for \childprime in {0,...,\p-1}{%Goes through the p
    % kids in the p-regular tree
    %
    % draw a blue edge of the Diest-Leader
    \addplot3[DeepSkyBlue4,thick] coordinates %
    (%The vertex at the top
        (\pspace/(2*\p)-0.5+\pshiftprime%
        +\childprime*\pspace/\p,
        \qn/2-0.5+\qshift,\n)
    % The vertex at height n-1
        (\pspace/2-0.5+\pshiftprime,\qn/(2*\q)%
        -0.5+\qshift+\child*\qn/\q,\n-1)};
    %End drawing
    % End if the loop "for childprime in"
    %; End if the loop "for kk in"
    %; % End of the loop "for \child in"
    %; End of the loop "for k in"
    %; End of the loop "for n in"
}%End Tikzmath
\end{axis}
\end{tikzpicture}
\end{document}
## References

[DL01] R. Diestel and I. Leader. A conjecture concerning a limit of non-cayley graphs. *Journal of Algebraic Combinatorics*, 14:17–25, 2001.

[EFW07] A Eskin, D Fisher, and K. Whyte. Quasi-isometries and rigidity of solvable groups. *Pure and Applied Mathematics Quarterly*, 3(4):927–947, 2007.

[EFW12] A Eskin, D Fisher, and K. Whyte. Coarse differentiation of quasi-isometries i: Spaces not quasi-isometric to cayley graphs. *Annals of Mathematics*, 176(1):221–260, 2012.

[Feu21] C. Feuersänger. Manual for package pgfplots, 2021. https://ctan.org/pkg/pgfplots.

[Woe91] Wolfgang Woess. Topological groups and infinite graphs. *Discrete Mathematics*, 95(1):373–384, 1991.

**Acknowledgments** We thank Tom Ferragut, Giles Gardam and Théo Laurent for their useful remarks and comments.

**Fundings** The author is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 427320536 – SFB 1442, as well as under Germany’s Excellence Strategy EXC 2044–390685587, Mathematics Münster: Dynamics–Geometry–Structure.

## Amandine Escalier

Mathematisches Institut,
Fachbereich Mathematik und Informatik der Universität Münster,
Orléans-Ring 12,
48149 Münster,
Germany