Pisot-Graph

In der Graphentheorie ist ein Pisot-Graph ein selbstähnlicher Graph, der mit Hilfe einer Pisot-Zahl definiert wird.

Definition

Gegeben sei eine Pisot-Zahl $\alpha >1$. Auf dem Folgenraum $\{0,1{\}}^n$ wird eine Äquivalenzrelation mittels

$s\sim t⟺\sum _{k=0}^{n-1}{s}_k{\alpha }^{-k}=\sum _{k=0}^{n-1}{t}_k{\alpha }^{-k}$

definiert.

Die Eckenmenge $V$ des Pisot-Graphen ist durch $V=\bigcup _{n=1}^{\mathrm{\infty }}{V}_n$ gegeben, wobei $V_n=\{0,1{\}}^n/\sim$ die Äquivalenzklassen der Relation $\sim$ bezeichnet. Es gibt also maximal $2^n$ Ecken in $V_n$, durch die Identifizierungen können es aber auch weniger Ecken sein.

Die Ecke $[s_1,\dots ,s_n]$ wird mit $[s_1,\dots ,s_n,0]$ und $[s_1,\dots ,s_n,1]$ durch eine Kante verbunden, hierdurch ist die Kantenmenge $E$ gegeben.

Beispiele

Fibonacci-Graph

Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den goldenen Schnitt $\alpha =\frac{1+\sqrt{5}}{2}$ bestimmt, der die Gleichung $1={\alpha }^{-1}+{\alpha }^{-2}$ erfüllt. Aus dieser Gleichung ergibt sich, dass $(1,0,0)$ mit $(0,1,1)$ identifiziert wird, weshalb $V_3$ in diesem Fall nur 7 Ecken hat.

Ähnlich wird (1,0,0,0) mit (0,1,1,0), (1,0,0,1) mit (0,1,1,1), (0,1,0,0) mit (0,0,1,1) und (1,1,0,0) mit (1,0,1,1) identifiziert, weshalb $V_4$ in diesem Fall nur 12 Ecken hat.

Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe $G=⟨L,R|LRR=RLL⟩$ beschrieben werden.

Weitere Pisot-Graphen erhält man durch andere Pisot-Zahlen. Insbesondere ist der durch die Nullstelle von $x^3+x-1=0$ bestimmte Graph nicht planar, siehe Abbildung.

Ein nicht planarer Pisot-Graph

Wachstumsrate

Die Wachstumsrate des Pisot-Graphen ist durch $W(\alpha )=\log \alpha$ gegeben. Dies ist eine Konsequenz des klassischen Garsia-Lemmas.

Literatur

• J. Neunhäuserer: Random walks on infinite self-similar graphs. In: Electronic Journal of Probability, Band 12 (2007), Artikel 46, S. 1258–1275, Vorlage:DOI.

Weblinks

• Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs (PDF-Datei; 854 kB)
• J. Neunhäuserer: Random walks on infinite self-similar graphs.